The parallel complexity of finite-state automata problems (Q1186807)

This paper classifies more precisely the complexity of several problems concerning DFAs and NFAs in terms of parallel complexity classes. Main results: (1) The minimization problem for DFAs is \(NC^ 1\)-complete for \(NL\). (2) The degree of ambiguity of an NFA is exponential, or polynomial, or bounded, and determining the degree of ambiguity for NFAs is \(NC^ 1\)- complete for \(NL\). (3) Testing whether an NFA is unambiguous or \(k\)-ambiguous for some fixed integer \(k\) is \(NC^ 1\)-complete for \(NL\). Independently of \textit{W. Kuich} (1988), it is also shown that the equivalence problems for unambiguous and \(k\)-ambiguous finite automata are both in DET (the class of problems \(NC^ 1\)-reducible to computing the determinants of integer matrices), where \(k\) is some fix constant.