Hyper-minimizing minimized deterministic finite state automata
Andrew Badr, Viliam Geffert, Ian Shipman (2007)
RAIRO - Theoretical Informatics and Applications
Similarity:
We present the first (polynomial-time) algorithm for reducing a given deterministic finite state automaton (DFA) into a DFA, which may have fewer states than the classically minimized DFA. The price we pay is that the language recognized by the new machine can differ from the original on a finite number of inputs. These hyper-minimized automata are optimal, in the sense that every DFA with fewer states must disagree on infinitely many inputs. With small modifications, the construction...