On the Average Complexity of Moore's State Minimization Algorithm

Frédérique Bassino 1 Julien David 2 Cyril Nicaud 2
1 LIPN - Laboratoire d'Informatique de Paris-Nord
2 LIGM - Laboratoire d'Informatique Gaspard-Monge
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.
Keywords : finite automata state minimization Moore's algorithm average complexity
Type de document :
Communication dans un congrès
Susanne Albers and Jean-Yves Marion. 26th International Symposium on Theoretical Aspects of Computer Science STACS 2009, Feb 2009, Freiburg, Germany. IBFI Schloss Dagstuhl, pp.123-134, 2009, Proceedings of the 26th Annual Symposium on the Theoretical Aspects of Computer Science
Liste complète des métadonnées

Littérature citée [18 références]  Voir  Masquer  Télécharger
https://hal.inria.fr/inria-00359162
Contributeur : Publications Loria <>
Soumis le : vendredi 6 février 2009 - 10:35:36
Dernière modification le : mercredi 11 avril 2018 - 12:12:02
Document(s) archivé(s) le : jeudi 30 juin 2011 - 10:50:23

Fichiers

bassino_new.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00359162, version 1
  • ARXIV : 0902.1048

Collections

STACS2009 | LIGM | LIGM_ALGO | UNIV-MLV | PARISTECH | ENPC | UPEC-UPEM | UNIV-PARIS13 | LIPN | LIGM_MOA | USPC

Citation

Frédérique Bassino, Julien David, Cyril Nicaud. On the Average Complexity of Moore's State Minimization Algorithm. Susanne Albers and Jean-Yves Marion. 26th International Symposium on Theoretical Aspects of Computer Science STACS 2009, Feb 2009, Freiburg, Germany. IBFI Schloss Dagstuhl, pp.123-134, 2009, Proceedings of the 26th Annual Symposium on the Theoretical Aspects of Computer Science. 〈inria-00359162〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

381

Téléchargements de fichiers

156

Contact


archive-ouverte@inria.fr