TY - GEN
T1 - Evaluating the Complexity of Deriving Adaptive Homing, Synchronizing and Distinguishing Sequences for Nondeterministic FSMs
AU - Yevtushenko, Nina
AU - Kuliamin, Victor
AU - Kushik, Natalia
N1 - Publisher Copyright:
© 2019, IFIP International Federation for Information Processing.
PY - 2019/1/1
Y1 - 2019/1/1
N2 - Homing, synchronizing and distinguishing sequences (HSs, SSs, and DSs) are used in FSM (Finite State Machine) based testing for state identification and can significantly reduce the size of a returned test suite with guaranteed fault coverage. However, such preset sequences not always exist for nondeterministic FSMs and are rather long when existing. Adaptive HSs, SSs and DSs are known to exist more often and be much shorter that makes them attractive for deriving test suites and adaptive checking sequences. As nowadays, a number of specifications are represented by nondeterministic FSMs, the deeper study of such sequences, their derivation strategies, and related complexity estimations/reductions is in great demand. In this paper, we evaluate the complexity of deriving adaptive HSs and SSs for noninitialized FSMs, the complexity of deriving DSs for noninitialized merging-free FSMs.
AB - Homing, synchronizing and distinguishing sequences (HSs, SSs, and DSs) are used in FSM (Finite State Machine) based testing for state identification and can significantly reduce the size of a returned test suite with guaranteed fault coverage. However, such preset sequences not always exist for nondeterministic FSMs and are rather long when existing. Adaptive HSs, SSs and DSs are known to exist more often and be much shorter that makes them attractive for deriving test suites and adaptive checking sequences. As nowadays, a number of specifications are represented by nondeterministic FSMs, the deeper study of such sequences, their derivation strategies, and related complexity estimations/reductions is in great demand. In this paper, we evaluate the complexity of deriving adaptive HSs and SSs for noninitialized FSMs, the complexity of deriving DSs for noninitialized merging-free FSMs.
KW - Adaptive distinguishing sequence
KW - Adaptive homing sequence
KW - Adaptive synchronizing sequence
KW - Nondeterministic Finite State Machine (FSM)
UR - https://www.scopus.com/pages/publications/85075657116
U2 - 10.1007/978-3-030-31280-0_6
DO - 10.1007/978-3-030-31280-0_6
M3 - Conference contribution
AN - SCOPUS:85075657116
SN - 9783030312794
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 86
EP - 103
BT - Testing Software and Systems - 31st IFIP WG 6.1 International Conference, ICTSS 2019, Proceedings
A2 - Gaston, Christophe
A2 - Kosmatov, Nikolai
A2 - Le Gall, Pascale
PB - Springer
T2 - 31st IFIP International Conference on Testing Software and Systems, ICTSS 2019
Y2 - 15 October 2019 through 17 October 2019
ER -