Name
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"1d"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. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1016/j.tcs.2009.01.039 | Theor. Comput. Sci. |
Keywords | DocType | Volume |
Continuant polynomials,worst-case behavior,continuant polynomial,geometric mean,Automata minimization,previous paper,Hopcroft’s algorithm,periodic directive sequence,directive sequence,Fibonacci word,worst case behavior,standard Sturmian word,bounded element,deterministic finite state automaton,worst case,minimization algorithm,Standard Sturmian sequence | Journal | 410 |
Issue | ISSN | Citations |
30-32 | Theoretical Computer Science | 14 |
PageRank | References | Authors |
0.78 | 11 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| jean berstel | 1 | 664 | 111.00 |
| Luc Boasson | 2 | 490 | 75.99 |
| Olivier Carton | 3 | 381 | 40.97 |