The structure and complexity of minimal NFA’s over a unary alphabet. (English) Zbl 0746.68040

Jiang, Tao; McDowell, Edward; Ravikumar, B.

Int. J. Found. Comput. Sci. 2, No. 2, 163-182 (1991).

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.

Reviewer: J.Hromkovič (Bratislava)

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