Hardness of deriving invertible sequences from finite state machines

Hierons, Robert M.Department of Computer Science, Brunel University London, Uxbridge, United Kingdom (författare)

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.

Mousavi, Mohammad Reza,1978-Högskolan i Halmstad,Centrum för forskning om inbyggda system (CERES)(Swepub:hh)mohmou (författare)
Thomsen, Michael KirkedalDepartment of Computer Science, University of Copenhagen, Copenhagen, Denmark (författare)
Turker, Uraz CengizComputer Engineering, Faculty of Engineering, Gebze Technical University, Kocaeli, Turkey (författare)
Department of Computer Science, Brunel University London, Uxbridge, United KingdomCentrum för forskning om inbyggda system (CERES) (creator_code:org_t)

Ingår i:SOFSEM 2017: SOFSEM 2017: Theory and Practice of Computer ScienceHeidelberg : Springer Berlin/Heidelberg, s. 147-16097833195196239783319519630

Av författaren/redakt...: Hierons, Robert ...; Mousavi, Mohamma ...; Thomsen, Michael ...; Turker, Uraz Cen ...

Om ämnet

Kungliga biblioteket hanterar dina personuppgifter i enlighet med EU:s dataskyddsförordning (2018), GDPR. Läs mer om hur det funkar här.
Så här hanterar KB dina uppgifter vid användning av denna tjänst.