On the Average Complexity of Moore's State Minimization Algorithm
classification
💻 cs.DS
cs.CC
keywords
algorithmaveragecomplexityminimizationmoorestateaccessiblealphabet
read the original abstract
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.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.