Evaluating the Complexity of Deriving Adaptive Homing, Synchronizing and Distinguishing Sequences for Nondeterministic FSMs

Nina Yevtushenko; Victor Kuliamin; Natalia Kushik

doi:10.1007/978-3-030-31280-0_6

Evaluating the Complexity of Deriving Adaptive Homing, Synchronizing and Distinguishing Sequences for Nondeterministic FSMs

Nina Yevtushenko
, Victor Kuliamin
, Natalia Kushik

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Abstract

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.

Original language	English
Title of host publication	Testing Software and Systems - 31st IFIP WG 6.1 International Conference, ICTSS 2019, Proceedings
Editors	Christophe Gaston, Nikolai Kosmatov, Pascale Le Gall
Publisher	Springer
Pages	86-103
Number of pages	18
ISBN (Print)	9783030312794
DOIs	https://doi.org/10.1007/978-3-030-31280-0_6
Publication status	Published - 1 Jan 2019
Externally published	Yes
Event	31st IFIP International Conference on Testing Software and Systems, ICTSS 2019 - Paris, France Duration: 15 Oct 2019 → 17 Oct 2019

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	11812 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	31st IFIP International Conference on Testing Software and Systems, ICTSS 2019
Country/Territory	France
City	Paris
Period	15/10/19 → 17/10/19

Keywords

Adaptive distinguishing sequence
Adaptive homing sequence
Adaptive synchronizing sequence
Nondeterministic Finite State Machine (FSM)

Access to Document

10.1007/978-3-030-31280-0_6

Cite this

Yevtushenko, N., Kuliamin, V., & Kushik, N. (2019). Evaluating the Complexity of Deriving Adaptive Homing, Synchronizing and Distinguishing Sequences for Nondeterministic FSMs. In C. Gaston, N. Kosmatov, & P. Le Gall (Eds.), Testing Software and Systems - 31st IFIP WG 6.1 International Conference, ICTSS 2019, Proceedings (pp. 86-103). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11812 LNCS). Springer. https://doi.org/10.1007/978-3-030-31280-0_6

Yevtushenko, Nina ; Kuliamin, Victor ; Kushik, Natalia. / Evaluating the Complexity of Deriving Adaptive Homing, Synchronizing and Distinguishing Sequences for Nondeterministic FSMs. Testing Software and Systems - 31st IFIP WG 6.1 International Conference, ICTSS 2019, Proceedings. editor / Christophe Gaston ; Nikolai Kosmatov ; Pascale Le Gall. Springer, 2019. pp. 86-103 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{da2cbb959efd45bd9b7fe38d771f5f70,

title = "Evaluating the Complexity of Deriving Adaptive Homing, Synchronizing and Distinguishing Sequences for Nondeterministic FSMs",

abstract = "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.",

keywords = "Adaptive distinguishing sequence, Adaptive homing sequence, Adaptive synchronizing sequence, Nondeterministic Finite State Machine (FSM)",

author = "Nina Yevtushenko and Victor Kuliamin and Natalia Kushik",

note = "Publisher Copyright: {\textcopyright} 2019, IFIP International Federation for Information Processing.; 31st IFIP International Conference on Testing Software and Systems, ICTSS 2019 ; Conference date: 15-10-2019 Through 17-10-2019",

year = "2019",

month = jan,

day = "1",

doi = "10.1007/978-3-030-31280-0\_6",

language = "English",

isbn = "9783030312794",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "86--103",

editor = "Christophe Gaston and Nikolai Kosmatov and \{Le Gall\}, Pascale",

booktitle = "Testing Software and Systems - 31st IFIP WG 6.1 International Conference, ICTSS 2019, Proceedings",

}

Yevtushenko, N, Kuliamin, V & Kushik, N 2019, Evaluating the Complexity of Deriving Adaptive Homing, Synchronizing and Distinguishing Sequences for Nondeterministic FSMs. in C Gaston, N Kosmatov & P Le Gall (eds), Testing Software and Systems - 31st IFIP WG 6.1 International Conference, ICTSS 2019, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 11812 LNCS, Springer, pp. 86-103, 31st IFIP International Conference on Testing Software and Systems, ICTSS 2019, Paris, France, 15/10/19. https://doi.org/10.1007/978-3-030-31280-0_6

Evaluating the Complexity of Deriving Adaptive Homing, Synchronizing and Distinguishing Sequences for Nondeterministic FSMs. / Yevtushenko, Nina; Kuliamin, Victor; Kushik, Natalia.
Testing Software and Systems - 31st IFIP WG 6.1 International Conference, ICTSS 2019, Proceedings. ed. / Christophe Gaston; Nikolai Kosmatov; Pascale Le Gall. Springer, 2019. p. 86-103 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11812 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

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

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 -

Yevtushenko N, Kuliamin V, Kushik N. Evaluating the Complexity of Deriving Adaptive Homing, Synchronizing and Distinguishing Sequences for Nondeterministic FSMs. In Gaston C, Kosmatov N, Le Gall P, editors, Testing Software and Systems - 31st IFIP WG 6.1 International Conference, ICTSS 2019, Proceedings. Springer. 2019. p. 86-103. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-31280-0_6

Evaluating the Complexity of Deriving Adaptive Homing, Synchronizing and Distinguishing Sequences for Nondeterministic FSMs

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this