Catalog Home Page

Repetitions in Sturmian strings

Franěk, F., Karaman, A. and Smyth, W.F. (2000) Repetitions in Sturmian strings. Theoretical Computer Science, 249 (2). pp. 289-303.

Link to Published Version: http://dx.doi.org/10.1016/S0304-3975(00)00063-3
*Subscription may be required

Abstract

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 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 third algorithm uses the reduction sequence of u 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.

Publication Type: Journal Article
Publisher: Elsevier BV
Copyright: © 2000 Elsevier Science B.V.
URI: http://researchrepository.murdoch.edu.au/id/eprint/27544
Item Control Page Item Control Page