Skip to Main content Skip to Navigation
Journal articles

Continuant polynomials and worst-case behavior of Hopcroft's minimization algorithm

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. In a previous paper, we have proved that this holds for all standard Sturmian words having an ultimately periodic directive sequence (the directive sequence for Fibonacci words is (1, 1, ...)). We prove here that the same conclusion holds for all standard Sturmian words having a directive sequence with bounded elements. More precisely, we obtain in fact a characterization of those directive sequences for which Hopcroft's algorithm has worst case running time. These are the directive sequences (d(1), d(2), d(3), ...) for which the sequence of geometric means (d(1)d(2) ... d(n))(1/n) is bounded. As a consequence, we easily show that there exist directive sequences for which the worst case for the running time is not attained.
Document type :
Journal articles
Complete list of metadata

https://hal-upec-upem.archives-ouvertes.fr/hal-00619761
Contributor : Jean Berstel Connect in order to contact the contributor
Submitted on : Tuesday, September 6, 2011 - 5:39:10 PM
Last modification on : Friday, April 29, 2022 - 4:25:05 PM

Links full text

Identifiers

Citation

Jean Berstel, Luc Boasson, Olivier Carton. Continuant polynomials and worst-case behavior of Hopcroft's minimization algorithm. Theoretical Computer Science, Elsevier, 2009, 410 (30-32), pp.2811-2822. ⟨10.1016/j.tcs.2009.01.039⟩. ⟨hal-00619761⟩

Share

Metrics

Record views

36