Decreasing the length of adaptive distinguishing experiments for nondeterministic merging-free finite state machines

Adaptive distinguishing experiments with nondeterministic Finite State Machines (FSMs) are widely used for deriving tests with the guaranteed fault coverage for reactive discrete event systems. For test minimization, adaptive distinguishing sequences of minimal length that distinguish as many states as possible are most interesting. However, it is known that in general, the length of an (adaptive) input sequence distinguishing states of a nondeterministic FSM can be exponential with respect to the number of FSM states. This paper is devoted to deriving adaptive distinguishing sequences for a nondeterministic FSM of a special class with the length that is polynomial with respect to the number of FSM states.