Computational Complexity of NFA Minimization for Finite and Unary Languages.
Hermann Gruber, Markus Holzer · 2007
Abstract. We investigate the computational complexity of the nondeterministic finite automaton (NFA) minimization problem for finite and unary regular lan-guages, if the input is specified by a deterministic finite state machine. While in general the NFA minimization problem is PSPACE-complete [15], it becomes eas-ier when considering the aforementioned language families. It is easy to see that in both cases, the upper bound is ΣP2, the second level of the Polynomial Hierarchy. Concerning the lower bound, we show that minimization problem for NFAs accept-ing finite languages is hard for the complexity class DP, which includes both NP and coNP, and is a subset of ΣP2. Moreover, we show that the corresponding prob-lem for unary regular languages in general, i.e., not limited to the cyclic case, can be approximated in polynomial time within a performance ratio of O( n), where n is the number of states of the given deterministic finite state machine. This improves a recent result on the approximation of NFAs accepting cyclic unary languages [8]. We also show that one cannot approximate the unary NFA minimization problem with o(n), if the input is a NFA, which is an optimal bound, unless P = NP. 1