Murdoch University Research Repository

Welcome to the Murdoch University Research Repository

The Murdoch University Research Repository is an open access digital collection of research
created by Murdoch University staff, researchers and postgraduate students.

Learn more

Repetitions in Sturmian strings

Franěk, F., Karaman, A. and Smyth, W.F. (1998) Repetitions in Sturmian strings. In: 9th Australasian Workshop on Combinatorial Algorithms (AWOCA '98), 27 - 30 July 1998, Perth, Western Australia



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 χ and determines in time O(|χ|) whether or not χ is Sturmian. The second algorithm is a modification of the first that, in the case that χ is Sturmian, outputs a reduction sequence for a superstring υ of χ that is a prefix of an infinite Sturmian string. The third algorithm uses the reduction sequence of υ to compute all the repetitions in u in time θ(|υ|), 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 terms of "runs". Finally, for every integer r ≥ 4, we show how to construct an infinite Sturmian string that contains maximal repetitions of exponents 2, 3, ..., r-1, but none of exponent r.

Item Type: Conference Paper
Item Control Page Item Control Page


Downloads per month over past year