Skip to Main content Skip to Navigation
Conference papers

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)$).
Complete list of metadata

Cited literature [13 references]  Display  Hide  Download

https://hal.inria.fr/hal-01194663
Contributor : Coordination Episciences Iam <>
Submitted on : Monday, September 7, 2015 - 12:50:46 PM
Last modification on : Wednesday, February 3, 2021 - 7:54:27 AM
Long-term archiving on: : Tuesday, December 8, 2015 - 12:51:58 PM

File

dmAI0123.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : hal-01194663, version 1

Citation

Jean Berstel, Luc Boasson, Olivier Carton. Hopcroft's automaton minimization algorithm and Sturmian words. Fifth Colloquium on Mathematics and Computer Science, 2008, Kiel, Germany. pp.351-362. ⟨hal-01194663⟩

Share

Metrics

Record views

374

Files downloads

672