Hopcroft's automaton minimization algorithm and Sturmian words

Abstract : This paper is concerned with the analysis of the worst case behavior of Hopcroft's algorithm for minimizing deterministic finite state automata. We extend a result of Castiglione, Restivo and Sciortino. They show that Hopcroft's algorithm has a worst case behavior for the automata recognizing Fibonacci words. We prove that the same holds for all standard Sturmian words having an ultimately periodic directive sequence (the directive sequence for Fibonacci words is $(1,1,\ldots)$).
Type de document :
Communication dans un congrès
Roesler, Uwe. Fifth Colloquium on Mathematics and Computer Science, 2008, Kiel, Germany. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AI, Fifth Colloquium on Mathematics and Computer Science, pp.351-362, 2008, DMTCS Proceedings
Liste complète des métadonnées

Littérature citée [13 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01194663
Contributeur : Coordination Episciences Iam <>
Soumis le : lundi 7 septembre 2015 - 12:50:46
Dernière modification le : jeudi 11 janvier 2018 - 06:20:22
Document(s) archivé(s) le : mardi 8 décembre 2015 - 12:51:58

Fichier

dmAI0123.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : hal-01194663, version 1

Citation

Jean Berstel, Luc Boasson, Olivier Carton. Hopcroft's automaton minimization algorithm and Sturmian words. Roesler, Uwe. Fifth Colloquium on Mathematics and Computer Science, 2008, Kiel, Germany. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AI, Fifth Colloquium on Mathematics and Computer Science, pp.351-362, 2008, DMTCS Proceedings. 〈hal-01194663〉

Partager

Métriques

Consultations de la notice

243

Téléchargements de fichiers

71