Advertisement
Published in:
2014 | OriginalPaper | Chapter
Distinguishing Sequences for Partially Specified FSMs
Authors : Robert M. Hierons, Uraz Cengiz Türker
Published in: NASA Formal Methods
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Distinguishing Sequences (DSs) are used inmany Finite State Machine (FSM) based test techniques. Although Partially Specified FSMs (PSFSMs) generalise FSMs, the computational complexity of constructing Adaptive and Preset DSs (ADSs/PDSs) for PSFSMs has not been addressed. This paper shows that it is possible to check the existence of an ADS in polynomial time but the corresponding problem for PDSs is
PSPACE-complete
. We also report on the results of experiments with benchmarks and over 8 ∗ 10
6
PSFSMs.