On adaptive experiments for nondeterministic finite state machines

Adaptive experiments are well defined in the context of finite state machine (FSM) based analysis, in particular, in FSM based testing where homing and distinguishing experiments with FSMs are used for test derivation. In this paper, we define and propose algorithms for deriving adaptive homing and distinguishing experiments for non-initialized nondeterministic finite state machines (NFSMs). For NFSMs, the construction of adaptive experiments is rather complex as the partition over produced outputs does not define a partition over the set of states but a collection of intersecting subsets, and thus, the refinement of such set system is more difficult than the refinement of a partition. Given a complete non-initialized possibly non-observable NFSM, we establish necessary and sufficient conditions for having adaptive homing and distinguishing experiments and evaluate the height of these experiments.