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

Jean Berstel (1) , Luc Boasson , Olivier Carton

1 LIGM - Laboratoire d'Informatique Gaspard-Monge

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.

Domaines: Algorithme et structure de données [cs.DS]

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