TY - GEN
T1 - Heuristics for deriving adaptive homing and distinguishing sequences for nondeterministic finite state machines
AU - Kushik, Natalia
AU - Yenigün, Hüsnü
N1 - Publisher Copyright:
© IFIP International Federation for Information Processing 2015.
PY - 2015/1/1
Y1 - 2015/1/1
N2 - Distinguishing Sequences (DS) and Homing Sequences (HS) are used for state identification purposes in Finite State Machine (FSM) based testing. For deterministic FSMs, DS and HS related problems are well studied, for both preset and adaptive cases. There are also recent algorithms for checking the existence and constructing Adaptive DS and Adaptive HS for nondeterministic FSMs. However, most of the related problems are proven to be PSPACE-complete, while the worst case height of Adaptive DS and HS is known to be exponential. Therefore, novel heuristics and FSM classes where they can be applied need to be provided for effective derivation of such sequences. In this paper, we present a work in progress on the minimization of Adaptive DS and Adaptive HS for nondeterministic FSMs.
AB - Distinguishing Sequences (DS) and Homing Sequences (HS) are used for state identification purposes in Finite State Machine (FSM) based testing. For deterministic FSMs, DS and HS related problems are well studied, for both preset and adaptive cases. There are also recent algorithms for checking the existence and constructing Adaptive DS and Adaptive HS for nondeterministic FSMs. However, most of the related problems are proven to be PSPACE-complete, while the worst case height of Adaptive DS and HS is known to be exponential. Therefore, novel heuristics and FSM classes where they can be applied need to be provided for effective derivation of such sequences. In this paper, we present a work in progress on the minimization of Adaptive DS and Adaptive HS for nondeterministic FSMs.
KW - Adaptive distinguishing sequence
KW - Adaptive homing sequence
KW - Nondeterministic finite state machines
KW - Novel heuristics
UR - https://www.scopus.com/pages/publications/84952765551
U2 - 10.1007/978-3-319-25945-1_15
DO - 10.1007/978-3-319-25945-1_15
M3 - Conference contribution
AN - SCOPUS:84952765551
SN - 9783319259444
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 243
EP - 248
BT - Testing Software and Systems - 27th IFIP WG 6.1 International Conference, ICTSS 2015, Proceedings
A2 - Yevtushenko, Nina
A2 - El-Fakih, Khaled
A2 - Barlas, Gerassimos
PB - Springer Verlag
T2 - 27th IFIP WG 6.1 International Conference on Testing Software and Systems, ICTSS 2015
Y2 - 23 November 2015 through 25 November 2015
ER -