Distinguishing experiments with nondeterministic non-initialized finite state machines

Nowadays nondeterministic Finite State Machines (FSMs) are used in many application areas,in particular, in the area of discrete event system synthesis and analysis. In most publications, binarycompatibility and distinguishability relations are studied on the set of states or on the set ofinitialized FSMs and in this case, the necessary and sufficient conditions for the existence of presetand adaptive distinguishing experiments are known. However, when deriving checking sequencesagainst a nondeterministic FSM sometimes it is required to distinguish more than twostates of the same FSM or several FSMs by a preset or an adaptive distinguishing experiment. Inthis paper, we establish such conditions for non-initialized FSMs with more than two initial statesand thus, the corresponding conditions can be established for more than two initialized FSMs. Inparticular, we show that a preset distinguishing experiment exists if and only if the set of initialstates is separable, i.e., if and only if there exists an input sequence such that the sets of output sequencesto this input sequence at each two initial states do not intersect. A technique for derivingan adaptive distinguishing experiment for a FSM with several initial states is also proposed.

Keywords

Authors

References