Repetitions in Sturmian strings

In this paper we apply a simple representation of Sturmian strings, which we call a “reduction sequence”, to three algorithms. The first algorithm accepts as input a given finite string x and determines in time O(|x|) whether or not x is Sturmian. The second algorithm is a modification of the first that, in the case that x is Sturmian, outputs a reduction sequence for a superstring u of x that is a prefix of an infinite Sturmian string. The …