Average Case Analysis of Moore's State Minimization Algorithm.

Submitted, 18 pages.International audienceWe prove that for the uniform distribution over accessible deterministic automata with n states, the average complexity of Moore's state minimization algorithm is in O(n log n). The bound is shown to be tight in the case of unary automata. The average complexity of this algorithm for other related distributions, such as the uniform distribution over possibly incomplete or co-accessible automata, is also analyzed