Standard
Hardness of deriving invertible sequences from finite state machines. / Hierons, Robert M.; Mousavi, Mohammad Reza; Thomsen, Michael Kirkedal; Türker, Uraz Cengiz.
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
Harvard
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_12APA
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. Lecture notes in computer science Vol. 10139
https://doi.org/10.1007/978-3-319-51963-0_12Vancouver
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).
https://doi.org/10.1007/978-3-319-51963-0_12Author
Hierons, Robert M. ; Mousavi, Mohammad Reza ; Thomsen, Michael Kirkedal ; Türker, Uraz Cengiz. / 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).
Bibtex
@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",
address = "Switzerland",
note = "null ; Conference date: 16-01-2017 Through 20-01-2017",
}
RIS
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
Y2 - 16 January 2017 through 20 January 2017
ER -
