The Intractability of Finite State Machine Test Sequences
Date
2011-01-01
Authors
Ihemelandu, Ngozi I.
Mueller, Carl J.
Journal Title
Journal ISSN
Volume Title
Publisher
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.
Description
Keywords
verification, validation, testing, state machine, behavior
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.