Show simple item record

dc.contributor.advisorMueller, Carl J.en_US
dc.contributor.authorIhemelandu, Ngozi I.
dc.date.accessioned2012-02-15T10:23:55Z
dc.date.available2011-03-07T22:33:10Z
dc.date.created2011-05
dc.date.issued2011-03-07en_US
dc.date.submittedMay 2011
dc.identifier.urihttps://digital.library.txstate.edu/handle/10877/2491
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.formatText
dc.format.extent65 pages
dc.format.medium1 file (.pdf)
dc.language.isoen_US
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
txstate.documenttypeThesis
dc.contributor.committeeMemberHazlewood, Carolen_US
dc.contributor.committeeMemberKaikhah, Khosrowen_US
thesis.degree.departmentComputer Scienceen_US
thesis.degree.disciplineSoftware Engineeringen_US
thesis.degree.grantorTexas State Universityen_US
thesis.degree.levelMastersen_US
thesis.degree.nameMaster of Scienceen_US
txstate.departmentComputer Science


Download

Thumbnail

This item appears in the following Collection(s)

Show simple item record