Circular sturmian words and Hopcroft's algorithm

Abstract

In order to analyze some extremal cases of Hopcroft’s algorithm, we investigate the relationships between the combinatorial properties of a circular sturmian word (x) and the run of the algorithm on the cyclic automaton Ax associated to (x). The combinatorial properties of words taken into account make use of sturmian morphisms and give rise to the notion of reduction tree of a circular sturmian word. We prove that the shape of this tree uniquely characterizes the word itself. The properties of the run of Hopcroft’s algorithm are expressed in terms of the derivation tree of the automaton, which is a tree that represents the refinement process that, in the execution of Hopcroft’s algorithm, leads to the coarsest congruence of the automaton. We prove that the shape of the reduction tree of a circular sturmian word (x) coincides with that of the derivation tree T(Ax) of the automaton Ax. From this we derive a recursive formula to compute the running time of Hopcroft’s algorithm on the automaton Ax, expressed in terms of parameters of the reduction tree of (x). As a special application, we obtain the time complexity Θ(nlogn) of the algorithm in the case of automata associated to Fibonacci words.