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.

68Q25 Analysis of algorithms and problem complexity
68Q45 Formal languages and automata
68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
Full Text: DOI