Finite Automata with Restricted Nondeterminism and Universality
Abstract
Deterministic, 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 tradeoffs 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.
URI for this record
http://hdl.handle.net/1974/29518Request an alternative format
If you require this document in an alternate, accessible format, please contact the Queen's Adaptive Technology CentreThe following license files are associated with this item:
Except where otherwise noted, this item's license is described as Queen's University's Thesis/Dissertation NonExclusive License for Deposit to QSpace and Library and Archives Canada
Related items
Showing items related by title, author, creator and subject.

New metrics for finite automaton complexity and subregular language hierarchies
Keeler, ChrisThe degree of ambiguity of nondeterministic finite automata (NFA) has been studied significantly since at least the 1980s. Roughly speaking, the degree of ambiguity counts the number of accepting computations of an ... 
Single Stage Power Factor Corrected ThreeLevel Resonant Converters
Agamy, Mohammed S. (20080201)In this thesis, a new approach for singlestage power factor correction converters is proposed to increase their power ratings to be in the multiple kilowatts levels. The proposed techniques are based on the utilization ... 
Effect of Low Temperature on the Static and Fatigue Behaviour of Reinforced Concrete Beams with Temperature Differentials
Mirzazadeh, MehdiThis research conducted herein comprises two phases: experimental and numerical. In the experimental phase, the effect of low temperature and temperature differentials on the static and fatigue behaviour of eight largescale ...