THE STRUCTURE AND COMPLEXITY OF MINIMAL NFA’S OVER A UNARY ALPHABET

作     者：TAO JIANG EDWARD McDOWELL B. RAVIKUMAR 

作者机构：Department of Computer Science and Systems McMaster University Hamilton Ontario Canada L8S 4K1 Canada This work was supported in part by a grant from SERB McMaster University and NSERC Operating Grant OGP 0046613. Department of Mathematics and Computer Science Rhode Island College Providence RI USA Department of Computer Science and Statistics University of Rhode Island Kingston RI 02881 USA This work was supported in part by a summer faculty fellowship of the URI Foundation. 

出 版 物：《International Journal of Foundations of Computer Science》 

年 卷 期：1991年第2卷第2期

页      面：163-182页

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：Finite automaton determinism nondeterminism minimization computational complexity unary alphabet 

摘      要：Many difficult open problems in theoretical computer science center around non-determinism. We study the fundamental problem of converting a given deterministic finite automaton (DFA) to a minimal nondeterministic finite automaton (NFA). Despite extensive work on finite automata, this fundamental problem has remained open. Recently, we studied this problem and showed that this (and related) problems are computationally hard . 11 Herewe study the restriction of this problem to the case when the input DFA is over a one-letter alphabet. Even in this restricted case the problem is computationally hard even though our evidence of hardness is different from (and is weaker than) the standard ones such as NP-hardness. Let A → B denote the problem of converting a finite automaton of type A to a minimal finite automaton of type B. Our main result is that DFA → NFA , when the input is a unary cyclic DFA (a DFA whose graph is a simple cycle), is in NP but not in P unless NP ⊆ DTIME (n O( log n) ). Our work was also motivated by the problem of finding structurally simple “normal forms of NFA’s over a unary alphabet. We present some normal forms for minimal NFA’s over a unary alphabet and present an application to lower bounds on the size complexity of an NFA. In fact, the normal form result is used in a nontrivial manner to show the NP membership result stated above.