Hardness of deriving invertible sequences from finite state machines

Robert M. Hierons; Mohammad Reza Mousavi; Michael Kirkedal Thomsen; Uraz Cengiz Türker

doi:10.1007/978-3-319-51963-0_12

Hardness of deriving invertible sequences from finite state machines

Robert M. Hierons, Mohammad Reza Mousavi, Michael Kirkedal Thomsen, Uraz Cengiz Türker^*

^*Corresponding author for this work

Department of Computer Science

Abstract

Many test generation algorithms use unique input/output sequences (UIOs) that identify states of the finite state machine specification M. However, it is known that UIO checking the existence of UIO sequences is PSPACE-complete. As a result, some UIO generation algorithms utilise what are called invertible sequences; these allow one to construct additional UIOs once a UIO has been found. We consider three optimisation problems associated with invertible sequences: deciding whether there is a (proper) invertible sequence of length at least K; deciding whether there is a set of invertible sequences for state set S′ that contains at most K input sequences; and deciding whether there is a single input sequence that defines invertible sequences that take state set S″ to state set S′. We prove that the first two problems are NP-complete and the third is PSPACE-complete. These results imply that we should investigate heuristics for these problems.

Original language	English
Title of host publication	SOFSEM 2017: Theory and Practice of Computer Science : 43rd International Conference on Current Trends in Theory and Practice of Computer Science, Limerick, Ireland, January 16-20, 2017, Proceedings
Editors	Bernhard Steffen, Christel Baier, Mark van den Brand, Johann Eder, Mike Hinchey, Tiziana Margaria
Number of pages	14
Publisher	Springer
Publication date	2017
Pages	147-160
ISBN (Print)	978-3-319-51962-3
ISBN (Electronic)	978-3-319-51963-0
DOIs	https://doi.org/10.1007/978-3-319-51963-0_12
Publication status	Published - 2017
Event	43rd International Conference on Current Trends in Theory and Practice of Computer Science - Limerick, Ireland Duration: 16 Jan 2017 → 20 Jan 2017 Conference number: 43

Conference

Conference	43rd International Conference on Current Trends in Theory and Practice of Computer Science
Number	43
Country/Territory	Ireland
City	Limerick
Period	16/01/2017 → 20/01/2017

Series	Lecture notes in computer science
Volume	10139
ISSN	0302-9743

Access to Document

10.1007/978-3-319-51963-0_12

Cite this

Hierons, R. M., Mousavi, M. R., Thomsen, M. K., & Türker, U. C. (2017). Hardness of deriving invertible sequences from finite state machines. In B. Steffen, C. Baier, M. van den Brand, J. Eder, M. Hinchey, & T. Margaria (Eds.), SOFSEM 2017: Theory and Practice of Computer Science: 43rd International Conference on Current Trends in Theory and Practice of Computer Science, Limerick, Ireland, January 16-20, 2017, Proceedings (pp. 147-160). Springer. https://doi.org/10.1007/978-3-319-51963-0_12

Hardness of deriving invertible sequences from finite state machines. / Hierons, Robert M.; Mousavi, Mohammad Reza; Thomsen, Michael Kirkedal et al.
SOFSEM 2017: Theory and Practice of Computer Science: 43rd International Conference on Current Trends in Theory and Practice of Computer Science, Limerick, Ireland, January 16-20, 2017, Proceedings. ed. / Bernhard Steffen; Christel Baier; Mark van den Brand; Johann Eder; Mike Hinchey; Tiziana Margaria. Springer, 2017. p. 147-160 (Lecture notes in computer science, Vol. 10139).

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

Hierons, RM, Mousavi, MR, Thomsen, MK & Türker, UC 2017, Hardness of deriving invertible sequences from finite state machines. in B Steffen, C Baier, M van den Brand, J Eder, M Hinchey & T Margaria (eds), SOFSEM 2017: Theory and Practice of Computer Science: 43rd International Conference on Current Trends in Theory and Practice of Computer Science, Limerick, Ireland, January 16-20, 2017, Proceedings. Springer, Lecture notes in computer science, vol. 10139, pp. 147-160, 43rd International Conference on Current Trends in Theory and Practice of Computer Science, Limerick, Ireland, 16/01/2017. https://doi.org/10.1007/978-3-319-51963-0_12

Hierons RM, Mousavi MR, Thomsen MK, Türker UC. Hardness of deriving invertible sequences from finite state machines. In Steffen B, Baier C, van den Brand M, Eder J, Hinchey M, Margaria T, editors, SOFSEM 2017: Theory and Practice of Computer Science: 43rd International Conference on Current Trends in Theory and Practice of Computer Science, Limerick, Ireland, January 16-20, 2017, Proceedings. Springer. 2017. p. 147-160. (Lecture notes in computer science, Vol. 10139). doi: 10.1007/978-3-319-51963-0_12

Hierons, Robert M. ; Mousavi, Mohammad Reza ; Thomsen, Michael Kirkedal et al. / Hardness of deriving invertible sequences from finite state machines. SOFSEM 2017: Theory and Practice of Computer Science: 43rd International Conference on Current Trends in Theory and Practice of Computer Science, Limerick, Ireland, January 16-20, 2017, Proceedings. editor / Bernhard Steffen ; Christel Baier ; Mark van den Brand ; Johann Eder ; Mike Hinchey ; Tiziana Margaria. Springer, 2017. pp. 147-160 (Lecture notes in computer science, Vol. 10139).

@inproceedings{cb6ef97e14f44f0693e0a756213b2dd5,

title = "Hardness of deriving invertible sequences from finite state machines",

abstract = "Many test generation algorithms use unique input/output sequences (UIOs) that identify states of the finite state machine specification M. However, it is known that UIO checking the existence of UIO sequences is PSPACE-complete. As a result, some UIO generation algorithms utilise what are called invertible sequences; these allow one to construct additional UIOs once a UIO has been found. We consider three optimisation problems associated with invertible sequences: deciding whether there is a (proper) invertible sequence of length at least K; deciding whether there is a set of invertible sequences for state set S′ that contains at most K input sequences; and deciding whether there is a single input sequence that defines invertible sequences that take state set S″ to state set S′. We prove that the first two problems are NP-complete and the third is PSPACE-complete. These results imply that we should investigate heuristics for these problems.",

author = "Hierons, {Robert M.} and Mousavi, {Mohammad Reza} and Thomsen, {Michael Kirkedal} and T{\"u}rker, {Uraz Cengiz}",

year = "2017",

doi = "10.1007/978-3-319-51963-0_12",

language = "English",

isbn = "978-3-319-51962-3",

series = "Lecture notes in computer science",

publisher = "Springer",

pages = "147--160",

editor = "Bernhard Steffen and Christel Baier and {van den Brand}, Mark and Johann Eder and Mike Hinchey and Tiziana Margaria",

booktitle = "SOFSEM 2017: Theory and Practice of Computer Science",

note = "43rd International Conference on Current Trends in Theory and Practice of Computer Science ; Conference date: 16-01-2017 Through 20-01-2017",

}

TY - GEN

T1 - Hardness of deriving invertible sequences from finite state machines

AU - Hierons, Robert M.

AU - Mousavi, Mohammad Reza

AU - Thomsen, Michael Kirkedal

AU - Türker, Uraz Cengiz

N1 - Conference code: 43

PY - 2017

Y1 - 2017

N2 - Many test generation algorithms use unique input/output sequences (UIOs) that identify states of the finite state machine specification M. However, it is known that UIO checking the existence of UIO sequences is PSPACE-complete. As a result, some UIO generation algorithms utilise what are called invertible sequences; these allow one to construct additional UIOs once a UIO has been found. We consider three optimisation problems associated with invertible sequences: deciding whether there is a (proper) invertible sequence of length at least K; deciding whether there is a set of invertible sequences for state set S′ that contains at most K input sequences; and deciding whether there is a single input sequence that defines invertible sequences that take state set S″ to state set S′. We prove that the first two problems are NP-complete and the third is PSPACE-complete. These results imply that we should investigate heuristics for these problems.

AB - Many test generation algorithms use unique input/output sequences (UIOs) that identify states of the finite state machine specification M. However, it is known that UIO checking the existence of UIO sequences is PSPACE-complete. As a result, some UIO generation algorithms utilise what are called invertible sequences; these allow one to construct additional UIOs once a UIO has been found. We consider three optimisation problems associated with invertible sequences: deciding whether there is a (proper) invertible sequence of length at least K; deciding whether there is a set of invertible sequences for state set S′ that contains at most K input sequences; and deciding whether there is a single input sequence that defines invertible sequences that take state set S″ to state set S′. We prove that the first two problems are NP-complete and the third is PSPACE-complete. These results imply that we should investigate heuristics for these problems.

UR - http://www.scopus.com/inward/record.url?scp=85010657662&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-51963-0_12

DO - 10.1007/978-3-319-51963-0_12

M3 - Article in proceedings

AN - SCOPUS:85010657662

SN - 978-3-319-51962-3

T3 - Lecture notes in computer science

SP - 147

EP - 160

BT - SOFSEM 2017: Theory and Practice of Computer Science

A2 - Steffen, Bernhard

A2 - Baier, Christel

A2 - van den Brand, Mark

A2 - Eder, Johann

A2 - Hinchey, Mike

A2 - Margaria, Tiziana

PB - Springer

T2 - 43rd International Conference on Current Trends in Theory and Practice of Computer Science

Y2 - 16 January 2017 through 20 January 2017

ER -

Hardness of deriving invertible sequences from finite state machines

Abstract

Conference

Access to Document

Other files and links

Fingerprint

Cite this