Brunel University Research Archive(BURA) preserves and enables easy and open access to all
types of digital content. It showcases Brunel's research outputs.
Research contained within BURA is open access, although some publications may be subject
to publisher imposed embargoes. All awarded PhD theses are also archived on BURA.
Please use this identifier to cite or link to this item:
http://bura.brunel.ac.uk/handle/2438/9988| Title: | Distinguishing sequences for partially specified FSMs |
| Authors: | Hierons, RM Türker, UC |
| Keywords: | Distinguishing Sequences (DSs);computational complexity;Adaptive and Preset DSs (ADSs/PDSs) |
| Issue Date: | 2014 |
| Publisher: | Springer Verlag |
| Citation: | LNCS: 62 - 76, 2014 |
| Abstract: | 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 * 106 PSFSMs. © 2014 Springer International Publishing. |
| URI: | http://link.springer.com/chapter/10.1007%2F978-3-319-06200-6_5 http://bura.brunel.ac.uk/handle/2438/9988 |
| DOI: | http://dx.doi.org/10.1007/978-3-319-06200-6_5 |
| ISSN: | 0302-9743 |
| Appears in Collections: | Mathematical Sciences |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| llncs_submitted.pdf | 5.26 MB | Adobe PDF | View/Open |
Items in BURA are protected by copyright, with all rights reserved, unless otherwise indicated.