View article

Finite automata (FA’s) are of fundamental importance in theory and in applications. The following basic minimization problem is studied: Given a DFA (deterministic FA), find a minimum equivalent nondeterministic FA (NFA). This paper shows that the natural decision problem associated with it is PSPACE-complete. More generally, let 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 to make the decision problem involving an NFA computationally hard, the authors study the complexity decision problems for FA’s and present several intractability results, even for cases in which the input is deterministic or nondeterministic with a very limited nondeterminism. For example, it is shown that it is PSPACE-complete to decide if , where …