Minimal NFA Problems are Hard 论文

摘要

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 ${\text{A}} \to {\text{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 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 $L(M_1 ) \cdot 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 deciding whether an FA has the finite power property), as well as recent ones (such as determining the diversity of a given FA).