hh.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Hardness of deriving invertible sequences from finite state machines
Department of Computer Science, Brunel University London, Uxbridge, United Kingdom.
Halmstad University, School of Information Technology, Halmstad Embedded and Intelligent Systems Research (EIS), Centre for Research on Embedded Systems (CERES).ORCID iD: 0000-0002-4869-6794
Department of Computer Science, University of Copenhagen, Copenhagen, Denmark.
Computer Engineering, Faculty of Engineering, Gebze Technical University, Kocaeli, Turkey.
2017 (English)In: SOFSEM 2017: 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, Heidelberg: Springer Berlin/Heidelberg, 2017, p. 147-160Conference paper, Published paper (Refereed)
Abstract [en]

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. © Springer International Publishing AG 2017.

Place, publisher, year, edition, pages
Heidelberg: Springer Berlin/Heidelberg, 2017. p. 147-160
Series
Lecture Notes in Computer Science, ISSN 0302-9743 ; Vol. 10139
Keywords [en]
Software testing, Generation algorithm, Input sequence, NP Complete, Optimisation problems, PSPACE-complete, Single input, Test generation algorithm, Unique input/output sequences, Optimization
National Category
Discrete Mathematics
Identifiers
URN: urn:nbn:se:hh:diva-36431DOI: 10.1007/978-3-319-51963-0_12ISI: 000418793100012Scopus ID: 2-s2.0-85010657662ISBN: 978-3-319-51962-3 (print)ISBN: 978-3-319-51963-0 (electronic)OAI: oai:DiVA.org:hh-36431DiVA, id: diva2:1190770
Conference
43rd International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM), Limerick, IRELAND, January 16-20, 2017
Available from: 2018-03-15 Created: 2018-03-15 Last updated: 2018-03-15Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Authority records BETA

Mousavi, Mohammad Reza

Search in DiVA

By author/editor
Mousavi, Mohammad Reza
By organisation
Centre for Research on Embedded Systems (CERES)
Discrete Mathematics

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 10 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf