DOAJ Open Access 2008

Hopcroft's automaton minimization algorithm and Sturmian words

Jean Berstel Luc Boasson Olivier Carton

Lihat Sumber DOI

Abstrak

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)$).

Topik & Kata Kunci

Mathematics

Penulis (3)

Jean Berstel

Luc Boasson

Olivier Carton

Format Sitasi

APA MLA BibTeX

Berstel, J., Boasson, L., Carton, O. (2008). Hopcroft's automaton minimization algorithm and Sturmian words. https://doi.org/10.46298/dmtcs.3576

Akses Cepat

Lihat di Sumber doi.org/10.46298/dmtcs.3576

Informasi Jurnal

Tahun Terbit: 2008
Sumber Database: DOAJ
DOI: 10.46298/dmtcs.3576
Akses: Open Access ✓