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....
This data repository is not currently reporting usage information. For information on how your repository can submit usage information, please see our documentation.