Geodesic
Hopcroft's automaton minimization algorithm and Sturmian words
Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AI, Fifth Colloquium on Mathematics and Computer Science, DMTCS Proceedings vol. AI, Fifth Colloquium on Mathematics and Computer Science (2008).

Voir la notice de l'article provenant de la source Episciences

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)$). 
@article{DMTCS_2008_special_254_a22,
     author = {Berstel, Jean and Boasson, Luc and Carton, Olivier},
     title = {Hopcroft's automaton minimization algorithm and {Sturmian} words},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {DMTCS Proceedings vol. AI, Fifth Colloquium on Mathematics and Computer Science},
     year = {2008},
     doi = {10.46298/dmtcs.3576},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3576/}
}
TY  - JOUR
AU  - Berstel, Jean
AU  - Boasson, Luc
AU  - Carton, Olivier
TI  - Hopcroft's automaton minimization algorithm and Sturmian words
JO  - Discrete mathematics & theoretical computer science
PY  - 2008
VL  - DMTCS Proceedings vol. AI, Fifth Colloquium on Mathematics and Computer Science
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3576/
DO  - 10.46298/dmtcs.3576
LA  - en
ID  - DMTCS_2008_special_254_a22
ER  - 
%0 Journal Article
%A Berstel, Jean
%A Boasson, Luc
%A Carton, Olivier
%T Hopcroft's automaton minimization algorithm and Sturmian words
%J Discrete mathematics & theoretical computer science
%D 2008
%V DMTCS Proceedings vol. AI, Fifth Colloquium on Mathematics and Computer Science
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3576/
%R 10.46298/dmtcs.3576
%G en
%F DMTCS_2008_special_254_a22
Berstel, Jean; Boasson, Luc; Carton, Olivier. Hopcroft's automaton minimization algorithm and Sturmian words. Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AI, Fifth Colloquium on Mathematics and Computer Science, DMTCS Proceedings vol. AI, Fifth Colloquium on Mathematics and Computer Science (2008). doi : 10.46298/dmtcs.3576. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3576/

Cité par Sources :