%0 Journal Article
%T On the Average Complexity of Moore's State Minimization Algorithm
%A Fr¨¦d¨¦rique Bassino
%A Julien David
%A Cyril Nicaud
%J Computer Science
%D 2009
%I arXiv
%X 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 O(n log n). Moreover this bound is tight in the case of unary utomata.
%U http://arxiv.org/abs/0902.1048v1