Den här sidan är utskriven från Högskolan i Halmstads webbplats (www.hh.se). Texten uppdaterades senast den 2017-08-16. Besök webbplatsen om du vill vara säker på att läsa den senaste versionen.

Personal vid Högskolan

Tillbaka

Hardness of deriving invertible sequences from finite state machines

Hierons, Robert M., Mousavi, Mohammad Reza, Thomsen, Michael Kirkedal, Turker, Uraz Cengiz
2017

Konferensbidrag (Refereegranskat)

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

Nyckelord: Software testing; Generation algorithm; Input sequence; NP Complete; Optimisation problems; PSPACE-complete; Single input; Test generation algorithm; Unique input/output sequences; Optimization

Citera: Hierons, Robert M., Mousavi, Mohammad Reza, Thomsen, Michael Kirkedal & Turker, Uraz Cengiz, Hardness of deriving invertible sequences from finite state machines, 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., s. 147-160, 2017