On the Average Complexity of Moore's State Minimization Algorithm
Résumé
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.
Origine : Fichiers produits par l'(les) auteur(s)
Loading...