 |
Discrete Mathematics & Theoretical Computer Science |
Jean Berstel ; Luc Boasson ; Olivier Carton - Hopcroft's automaton minimization algorithm and Sturmian words
dmtcs:3576 - Discrete Mathematics & Theoretical Computer Science, January 1, 2008, DMTCS Proceedings vol. AI, Fifth Colloquium on Mathematics and Computer Science - https://doi.org/10.46298/dmtcs.3576Hopcroft's automaton minimization algorithm and Sturmian wordsConference paper
Authors: Jean Berstel 1; Luc Boasson 2; Olivier Carton 
2
- 1 Laboratoire d'Informatique Gaspard-Monge
- 2 Laboratoire d'informatique Algorithmique : Fondements et Applications
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)$).
Source: HAL:hal-01194663v1
Volume: DMTCS Proceedings vol. AI, Fifth Colloquium on Mathematics and Computer Science
Section: Proceedings
Published on: January 1, 2008
Imported on: May 10, 2017
Keywords: [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], [MATH.MATH-DS]Mathematics [math]/Dynamical Systems [math.DS], [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], [en] finite automata, minimization algorithm, complexity, Sturmian words
3 Documents citing this article
Consultation statistics
This page has been seen 430 times.
This article's PDF has been downloaded 330 times.