%0 Conference Proceedings
%T Evaluating the complexity of deriving adaptive homing, synchronizing and distinguishing sequences for nondeterministic FSMs
%+ Institute for System Programming of the Russian Academy of Sciences [Moscow] (ISPRAS)
%+ Département Réseaux et Services Multimédia Mobiles (TSP - RS2M)
%+ Institut Polytechnique de Paris (IP Paris)
%+ Méthodes et modèles pour les réseaux (METHODES-SAMOVAR)
%+ Centre National de la Recherche Scientifique (CNRS)
%A Yevtushenko, Nina
%A Kuliamin, Victor
%A Kushik, Natalia
%Z Part 2: Test Case Generation
%< avec comité de lecture
%( Lecture Notes in Computer Science
%B ICTSS 2019: 31st IFIP International Conference on Testing Software and Systems
%C Paris, France
%Y Christophe Gaston
%Y Nikolai Kosmatov
%Y Pascale Le Gall
%I Springer International Publishing
%3 Testing Software and Systems
%V LNCS-11812
%P 86-103
%8 2019-10-15
%D 2019
%R 10.1007/978-3-030-31280-0_6
%K Nondeterministic Finite State Machine (FSM)
%K Adaptive homing sequence
%K Adaptive synchronizing sequence
%K Adaptive distinguishing sequence
%Z Computer Science [cs]/Computational Complexity [cs.CC]
%Z Computer Science [cs]/Discrete Mathematics [cs.DM]
%Z Computer Science [cs]/Formal Languages and Automata Theory [cs.FL]Conference papers
%X 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.
%G English
%Z TC 6
%Z WG 6.1
%2 https://hal.science/hal-02448916/document
%2 https://hal.science/hal-02448916/file/482770_1_En_6_Chapter.pdf
%L hal-02448916
%U https://hal.science/hal-02448916
%~ INSTITUT-TELECOM
%~ CNRS
%~ TELECOM-SUDPARIS
%~ IFIP-LNCS
%~ IFIP
%~ IFIP-TC
%~ IFIP-WG
%~ IFIP-TC6
%~ IFIP-WG6-1
%~ TDS-MACS
%~ IFIP-ICTSS
%~ UNIV-PARIS-SACLAY
%~ TELECOM-SUDPARIS-SACLAY
%~ IP_PARIS
%~ INSTITUTS-TELECOM
%~ IFIP-LNCS-11812