Empirical Research into the Intractability of Finite State Machines

Simple item page
dc.contributor.advisorMueller, Carl J.en_US
dc.contributor.authorIhemelandu, Ngozi I.
dc.contributor.committeeMemberHazlewood, Carolen_US
dc.contributor.committeeMemberKaikhah, Khosrowen_US
dc.date.accessioned2012-02-15T10:23:55Z
dc.date.available2011-03-07T22:33:10Z
dc.date.issued2011-05en_US
dc.description.abstractMuch 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.en_US
dc.description.departmentComputer Science
dc.formatText
dc.format.extent65 pages
dc.format.medium1 file (.pdf)
dc.identifier.citationIhemelandu, N. I. (2011). <i>Empirical research into the intractability of finite state machines</i> (Unpublished thesis). Texas State University-San Marcos, San Marcos, Texas.
dc.identifier.urihttps://hdl.handle.net/10877/2491
dc.language.isoen
dc.subjectIntractabilityen_US
dc.subjectFinite state machineen_US
dc.subjectAlgorithmen_US
dc.subjectTestingen_US
dc.titleEmpirical Research into the Intractability of Finite State Machinesen_US
dc.typeThesis
thesis.degree.departmentComputer Science
thesis.degree.disciplineSoftware Engineeringen_US
thesis.degree.grantorTexas State University-San Marcosen_US
thesis.degree.levelMasters
thesis.degree.nameMaster of Science

Files

Original bundle

Now showing 1 - 1 of 1
Thumbnail Image
Name:
IHEMELANDU-THESIS.pdf
Size:
618.51 KB
Format:
Adobe Portable Document Format
Download

License bundle

Now showing 1 - 2 of 2
No Thumbnail Available
Name:
license.txt
Size:
2.12 KB
Format:
Plain Text
Description:
Download
No Thumbnail Available
Name:
1_license.txt
Size:
1.71 KB
Format:
Plain Text
Description:
Download

Collections

Graduate Theses and Dissertations