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, ...)).
(2007), Castiglione, Restivo and Sciortino replace the de Bruijn words by Fibonacci words. They show that, for this word, there is no more choice in Hopcroft's algorithm, and that the unique execution of Hopcroft's algorithm runs in time [OMEGA](n log n).
The case of Fibonacci words corresponds the directive sequence (1, 1, ...).
Example 1 (Fibonacci) For d = (1, 1, ...) = ([bar.1]), one gets [s.sub.n+1] = [s.sub.n][s.sub.n-1] for n [greater than or equal to] 1, and the standard words generated by d are the Fibonacci words 1, 0, 01, 010, 01001, ...
(2007) in the case of the Fibonacci words, with directive sequence d = ([bar.1]).
There are two types of Fibonacci words, "natural" and "arbitrary".
"Natural Fibonacci words" are composed of the letters of adjacent numbers in Fibonacci's series.
But it is of most interest because of the sacred aura surrounding the notion of the sum total of all "FIBONACCI WORDS"!
"Arbitrary Fibonacci words" are slightly more interesting.