Show simple item record

dc.contributor.authorKeeler, Chrisen
dc.date.accessioned2021-10-25T19:19:12Z
dc.date.available2021-10-25T19:19:12Z
dc.identifier.urihttp://hdl.handle.net/1974/29518
dc.description.abstractDeterministic, nondeterministic, and alternating finite automata (DFAs, NFAs, and AFAs) recognize exactly the class of regular languages, and are one of the simplest useful models of computation, having applications in practically all areas of computer science. In general, a DFA can require exponentially more states than an NFA to recognize a language, and an NFA can require exponentially more states than an AFA to recognize a language. Significant work has gone into the descriptional complexity of these models, and in particular, the trade-offs between NFAs with different amounts of limited nondeterminism. Previously studied measures of limited nondeterminism include the ambiguity, tree width, and path width, which, respectively, measure the number of accepting computations, the total number of computations, and the number of complete computations of an NFA. We present a polynomial algorithm which decides finiteness of an NFA's tree width. We study the growth rates of tree width and path width as functions on the length of the input, paralleling existing results comparing different growth rates for the ambiguity. We show that there exist finite path width NFAs which require exponentially more states to be recognized by a finite tree width NFA, and that there exist AFAs with finite tree width for which any equivalent NFA requires exponentially more states. We introduce the universal width measure, which counts the number of parallel computations followed by an AFA in a single nondeterministically chosen computation. We derive necessary and sufficient conditions for an AFA to have finite maximal universal width, and prove that the finite maximal universal width of an AFA is at most exponentially larger than the number of states. We also introduce the existential width measure, which counts the number of existential branches which do not need to be followed by an AFA in a single computation. We prove that an NFA has finite maximal existential width if and only if it has finite tree width, and that the finite maximal existential width of an NFA is at most polynomially larger than the number of states, even though the finite tree width of an NFA can be exponentially larger.en
dc.language.isoengen
dc.relation.ispartofseriesCanadian thesesen
dc.rightsQueen's University's Thesis/Dissertation Non-Exclusive License for Deposit to QSpace and Library and Archives Canadaen
dc.rightsProQuest PhD and Master's Theses International Dissemination Agreementen
dc.rightsIntellectual Property Guidelines at Queen's Universityen
dc.rightsCopying and Preserving Your Thesisen
dc.rightsThis publication is made available by the authority of the copyright owner solely for the purpose of private study and research and may not be copied or reproduced except as permitted by the copyright laws without written authority from the copyright owner.en
dc.rightsAttribution-ShareAlike 3.0 United States*
dc.rights.urihttp://creativecommons.org/licenses/by-sa/3.0/us/*
dc.subjectfinite automataen
dc.subjectnondeterminismen
dc.subjectalternationen
dc.subjectNFAen
dc.subjectDFAen
dc.subjectAFAen
dc.subjectregular languageen
dc.subjectstate complexityen
dc.subjecttree widthen
dc.subjectpath widthen
dc.subjectambiguityen
dc.subjectuniversal widthen
dc.subjectexistential widthen
dc.subjectcombined widthen
dc.subjectwidth measureen
dc.subjectmeasures of nondeterminismen
dc.subjectmeasures of universalityen
dc.subjectcycle heighten
dc.subjectlanguage densityen
dc.subjectdescriptional complexityen
dc.subjectalternatingen
dc.titleFinite Automata with Restricted Nondeterminism and Universalityen
dc.typethesisen
dc.description.degreePhDen
dc.contributor.supervisorSalomaa, Kai
dc.contributor.departmentComputingen
dc.degree.grantorQueen's University at Kingstonen


Files in this item

Thumbnail
Thumbnail

This item appears in the following Collection(s)

Show simple item record

Queen's University's Thesis/Dissertation Non-Exclusive License for Deposit to QSpace and Library and Archives Canada
Except where otherwise noted, this item's license is described as Queen's University's Thesis/Dissertation Non-Exclusive License for Deposit to QSpace and Library and Archives Canada