Computing Small Nondeterministic Finite Automata

Oliver Matz
Andreas Potthoff

In TACAS, pages 74--88


The minimization problem for nondeterministic finite automata is studied. Two approaches are discussed, based on the construction of two versions of ``canonical'' automata (for a given regular language), in which minimal automata occur as subautomata. A heuristic for this search is introduced, which has been implemented in the program AMoRE.

University of Kiel, Germany.

Available as PostScript, DVI.

[BRICS symbol] BRICS WWW home page