On the Average Complexity of Moore's State Minimization Algorithm
Loading...
Date
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Description
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.