# zbMATH — the first resource for mathematics

The structure and complexity of minimal NFA’s over a unary alphabet. (English) Zbl 0746.68040
The complexity of the problem of minimisation of nondeterministic finite automata (NFA) is investigated. More precisely, the problem of converting a given deterministic finite automaton to a minimal NFA is shown to be computationally hard. It is proved that the vertex cover problem (a well- known $$NP$$-complete problem) can be reduced to the above stated minimisation problem (also in the case when the given deterministic finite automaton is restricted to work over a one-letter alphabet) in time $$O(n^{\log n})$$. Thus, our minimisation problem can be in $$P$$ only if $$NP\subseteq O(n^{\log n})$$.
Besides the result stated above, the authors investigated the normal forms of NFA’s and algorithms converting every NFA to an equivalent NFA in a given normal form.

##### MSC:
 68Q25 Analysis of algorithms and problem complexity 68Q45 Formal languages and automata 68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
##### Keywords:
minimisation; finite automata; nondeterminism
Full Text: