Fast brief practical DFA minimization

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.