| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 429020 | Information Processing Letters | 2012 | 5 Pages |
Minimization of deterministic finite automata has traditionally required complicated programs and correctness proofs, and taken O(nklogn) time, where n is the number of states and k the size of the alphabet. Here a short, memory-efficient program is presented that runs in O(n+mlogm), or even in O(n+mlogn), time, where m is the number of transitions. The program is complete with input, output, and the removal of irrelevant parts of the automaton. Its invariant-style correctness proof is relatively short.
► Efficient DFA minimization used to be complicated but is now made simple. ► Asymptotic running time is better than that of any publication prior to 2008. ► The given correctness proofs are invariant-style and rather brief. ► Complete program code is given, so there are no hidden issues.
