Average Case Analysis of Moore’s State Minimization Algorithm

We prove that the average complexity of Moore’s state minimization algorithm is $𝒪(\mathrm{kn}\log n)$ , where n is the number of states of the input and k the size of the alphabet. This result holds for a whole family of probabilistic models on automata, including the uniform distribution over deterministic and accessible automata, as well as uniform distributions over classical subclasses, such as complete automata, acyclic automata, automata where each state is final with probability γ∈(0,1), and many other variations.