The Intractability of Finite State Machine Test Sequences
| dc.contributor.author | Ihemelandu, Ngozi I. | |
| dc.contributor.author | Mueller, Carl J. | |
| dc.date.accessioned | 2011-02-03T10:03:29Z | |
| dc.date.available | 2012-02-24T10:03:35Z | |
| dc.date.issued | 2011-01-01 | |
| dc.description.abstract | Much of the high reliability and safety critical software applications use various forms of Finite State Machines (FSM) to describe their behavior. Testing software with state behavior presents a number of challenges to development organizations. One of the challenges in testing state behavior is to verify that the application has entered a specific state. A theoretical proof has established that State Verification is a PSPACE-complete problem, but the proof did not provide an empirical verification. A primary objective of this research is to provide the empirical evidence to support the theoretic proof that the State Verification problem is PSPACE-complete. A secondary objective of this research is to investigate how states and transition affect the time to derive a Unique Input Output (UIO) sequence. In addition to the investigation of the intractability of the state verification problem, the suitability of using McCabe's Cyclomatic number to predict the performance of the algorithm generating the UIO sequences was explored. Based on the empirical results, the State Verification testing problem is a PSPACE problem and not PSPACE-complete problem, but only for fully specified FSM are UIO sequences appropriate. In addition, the Cyclomatic number did not predict the time necessary to derive UIO sequences. | |
| dc.description.department | Computer Science | |
| dc.format | Text | |
| dc.format.extent | 117 pages | |
| dc.format.medium | 1 file (.pdf) | |
| dc.identifier.citation | Ihemelandu, N. I., & Mueller, C. J. (2011). The interactability of finite state machine test sequences (Report No. TXSTATE-CS-TR-2011-26). Texas State University-San Marcos, Department of Computer Science. | |
| dc.identifier.uri | https://hdl.handle.net/10877/2588 | |
| dc.language.iso | en | |
| dc.subject | verification | |
| dc.subject | validation | |
| dc.subject | testing | |
| dc.subject | state machine | |
| dc.subject | behavior | |
| dc.title | The Intractability of Finite State Machine Test Sequences | |
| dc.type | Technical Report |
Files
Original bundle
1 - 1 of 1