Structural properties of NFAs and growth rates of nondeterminism measures

Abstract Tree width (respectively, string path width) measures the maximal number of partial (respectively, complete) computations of a nondeterministic finite automaton on an input of given length. We characterize polynomial and exponential growth rates of tree width and string path width by structural properties of the corresponding nondeterministic finite automaton (NFA). As the main result we show that the degree of the polynomial bounding the tree width of an NFA differs by at most one from the degree of the polynomial bounding the string path width of the same NFA. The condition characterizing polynomial growth rates, roughly speaking, requires that any computation can go through a bounded number of cycles where the strings of characters labeling the cycles satisfy certain requirements. More generally, an NFA is said to have cycle height K if any computation can visit at most K distinct cycles. We give a polynomial time algorithm to decide whether an NFA has finite cycle height and, in the positive case, to compute its optimal cycle height. Nondeterministic finite automata of finite cycle height recognize the polynomial density regular languages. Also we study the worst case state complexity of converting an NFA with finite string path width to an NFA with finite tree width.