Repetitions in Sturmian strings

In this paper we apply a simple representation of Sturmian strings, which w e call a "reduction sequence", to three algorithms. The first algorithm acc epts 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 su perstring u of x that is a prefix of an infinite Sturmian string. The third algorithm uses the reduction sequence of u to compute all the repetitions in u in time Theta>(*) over bar *(\u\), thus extending a recent result for Fibonacci strings. The third algorithm is also based on a characterization of the repetitions in a Sturmian string that describes them compactly in te rms of "runs". Finally, for every integer r greater than or equal to4, we s how how to construct an infinite Sturmian string that contains maximal repe titions of exponents 2, 3,..., r - 1, but none of exponent r. (C) 2000 Else vier Science B.V. All rights reserved.