On the Average Complexity of Moore's State Minimization Algorithm
Frédérique Bassino, Julien David, Cyril Nicaud · HAL (Le Centre pour la Communication Scientifique Directe) · 2009
We prove that, for any arbitrary finite alphabet and for the uniform distribution over deterministic and accessible automata with $n$ states, the average complexity of Moore's state minimization algorithm is in $\mathcal{O}(n \log n)$. Moreover this bound is tight in the case of unary automata.