Empirical Research into the Intractability of Finite State Machines




Ihemelandu, Ngozi I.

Journal Title

Journal ISSN

Volume Title



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.



Intractability, Finite state machine, Algorithm, Testing


Ihemelandu, N. I. (2011). <i>Empirical research into the intractability of finite state machines</i> (Unpublished thesis). Texas State University-San Marcos, San Marcos, Texas.


Rights Holder

Rights License

Rights URI