On length of an adaptive distinguishing sequence for a family of observable finite state machines

I. B. Burdonov^a, N. V. Evtushenko^ab, A. S. Kosachev<sup>a

a</sup> Ivannikov Institute for System Programming of the RAS
^b National Research University Higher School of Economics

Abstract: In the paper, the length of an adaptive distinguishing sequence for a family of initialized complete observable, possibly nondeterministic Finite State Machines (FSM) is studied. The upper bound for the length of such a sequence is established and its reachability is shown. It is also discussed how the obtained results can be applied for constructing adaptive diagnostic test suites based on a FSM model.

Keywords: nondeterministic FSMs, adaptive distinguishing sequence, diagnostic test suites

DOI: 10.15514/ISPRAS-2025-37(6)-1