Finite Automata with Restricted Nondeterminism and Universality

Thumbnail Image
Keeler, Chris
finite automata , nondeterminism , alternation , NFA , DFA , AFA , regular language , state complexity , tree width , path width , ambiguity , universal width , existential width , combined width , width measure , measures of nondeterminism , measures of universality , cycle height , language density , descriptional complexity , alternating
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 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.
External DOI