Efficient Minimization of DFAs with Partial Transition

Antti Valmari & Petri Lehtinen
Let PT-DFA mean a deterministic finite automaton whose transition relation is a partial function. We present an algorithm for minimizing a PT-DFA in $O(m lg n)$ time and $O(m+n+alpha)$ memory, where $n$ is the number of states, $m$ is the number of defined transitions, and $alpha$ is the size of the alphabet. Time consumption does not depend on $alpha$, because the $alpha$ term arises from an array that is accessed at random and never initialized....