MINIMAL NFA PROBLEMS ARE HARD

Finite automats (FA's) are of fundamental importance in theory and in applications. The following basic minimization problem is studied: Giv en a DFA (deterministic FA), find a minimum equivalent nondeterministi c FA (NFA). This paper shows that the natural decision problem associa ted with it is PSPACE-complete. More generally, let A --t B denote the problem of converting a given FA of type A to a minimum FA of type B. This paper also shows that most of these problems are computationally hard. Motivated by the question of how much nondeterminism suffices t o make the decision problem involving an NFA computationally hard, the authors study the complexity decision problems for FA's and present s everal intractability results, even for cases in which the input is de terministic or nondeterministic with a very limited nondeterminism. Fo r example, it is shown that it is PSPACE-complete to decide if L(M(1)) .L(M(2))=L(M(3)), where M(1), M(2), and M(3) are DFAs. These problems are related to some classical problems in automata theory (such as dec iding whether an FA has the finite power property), as well as recent ones (such as determining the diversity of a given FA).