New metrics for finite automaton complexity and subregular language hierarchies
The 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 NFA. To get a more comprehensive understanding of the branching complexity of NFAs, we introduce and study the string path width and depth path width measures. The string path width on a string w counts the number of all accepting and non-accepting computations on w, and the depth path width on an integer l counts the number of all accepting and non-accepting computations of a length l. We focus on cases where these measures are finite, that is, there is some input which has maximal string or depth path width. We give algorithms to decide the finiteness of the string and depth path width of an NFA. The latter algorithm relies on structural properties that characterize NFAs with finite depth path width, and the former is based on existing algorithms to compute the degree of ambiguity. We give upper bounds for the finite string and depth path width of an NFA or a DFA (deterministic finite automaton). It is well known that acyclic NFAs define exactly the class of finite languages. We consider less restrictive conditions that define the class of nearly acyclic NFAs. An NFA is nearly acyclic if it does not have two cycles where one can be reached from the other. It is shown that the nearly acyclic NFAs are exactly the NFAs with finite depth path width. We study and introduce variants of existing subregular language families. We establish (non)-inclusion relationships for these new classes, relative to each other and their existing counterparts. Additionally we show that an infinite hierarchy exists within the most powerful new family, generalized word-definite languages. We examine the structural limitations and give maximal examples of nearly acyclic NFAs. We also show that nearly acyclic NFAs recognize the class of generalized word-definite languages. For nearly acyclic DFAs, we establish a stronger correspondence: they recognize all generalized word-definite languages, and any DFA recognizing a generalized word-definite language must be nearly acyclic.
Request an alternative formatIf you require this document in an alternate, accessible format, please contact the Queen's Adaptive Technology Centre
The following license files are associated with this item: