TY - GEN
T1 - Adaptive homing and distinguishing experiments for nondeterministic finite state machines
AU - Kushik, Natalia
AU - El-Fakih, Khaled
AU - Yevtushenko, Nina
PY - 2013/12/1
Y1 - 2013/12/1
N2 - 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 in test derivation. In this paper, we define and propose algorithms for deriving adaptive homing and distinguishing experiments for non-initialized nondeterministic finite state machines (NFSM). 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 rather a collection of intersecting subsets, and thus, the refinement of such subsets is more difficult than the refinement of a partition. Given a complete non-initialized observable NFSM, we establish necessary and sufficient conditions for having adaptive homing and distinguishing experiments and evaluate the upper bound on the height of these experiments. Simple application examples demonstrating a proposed approach are provided.
AB - 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 in test derivation. In this paper, we define and propose algorithms for deriving adaptive homing and distinguishing experiments for non-initialized nondeterministic finite state machines (NFSM). 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 rather a collection of intersecting subsets, and thus, the refinement of such subsets is more difficult than the refinement of a partition. Given a complete non-initialized observable NFSM, we establish necessary and sufficient conditions for having adaptive homing and distinguishing experiments and evaluate the upper bound on the height of these experiments. Simple application examples demonstrating a proposed approach are provided.
KW - Adaptive homing and distinguishing experiments
KW - Conformance testing
KW - Nondeterministic finite state machine
UR - https://www.scopus.com/pages/publications/84893424051
U2 - 10.1007/978-3-642-41707-8_3
DO - 10.1007/978-3-642-41707-8_3
M3 - Conference contribution
AN - SCOPUS:84893424051
SN - 9783642417061
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 33
EP - 48
BT - Testing Software and Systems - 25th IFIPWG 6.1 International Conference, ICTSS 2013, Proceedings
T2 - 25th IFIPWG 6.1 International Conference on Testing Software and Systems, ICTSS 2013
Y2 - 13 November 2013 through 15 November 2013
ER -