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. red. / Bernhard Steffen; Christel Baier; Mark van den Brand; Johann Eder; Mike Hinchey; Tiziana Margaria. Springer, 2017. s. 147-160 (Lecture notes in computer science, Bind 10139).
Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › fagfællebedømt
Harvard
Hierons, RM, Mousavi, MR
, Thomsen, MK & Türker, UC 2017,
Hardness of deriving invertible sequences from finite state machines. i B Steffen, C Baier, M van den Brand, J Eder, M Hinchey & T Margaria (red),
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, bind 10139, s. 147-160, 43rd International Conference on Current Trends in Theory and Practice of Computer Science, Limerick, Irland,
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. I B. Steffen, C. Baier, M. van den Brand, J. Eder, M. Hinchey, & T. Margaria (red.),
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 (s. 147-160). Springer. Lecture notes in computer science Bind 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. I Steffen B, Baier C, van den Brand M, Eder J, Hinchey M, Margaria T, red., 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. s. 147-160. (Lecture notes in computer science, Bind 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. red. / Bernhard Steffen ; Christel Baier ; Mark van den Brand ; Johann Eder ; Mike Hinchey ; Tiziana Margaria. Springer, 2017. s. 147-160 (Lecture notes in computer science, Bind 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 -
