Efficient Minimization of DFAs with Partial Transition Functions

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+α)…