Conference paper
Repetitions in Sturmian strings
9th Australasian Workshop on Combinatorial Algorithms (AWOCA '98) (Perth, Western Australia, 27/07/1998–30/07/1998)
1998
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 χ 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.
Details
- Title
- Repetitions in Sturmian strings
- Authors/Creators
- F. Franěk (Author/Creator)A. Karaman (Author/Creator)W.F. Smyth (Author/Creator)
- Conference
- 9th Australasian Workshop on Combinatorial Algorithms (AWOCA '98) (Perth, Western Australia, 27/07/1998–30/07/1998)
- Identifiers
- 991005543159207891
- Murdoch Affiliation
- Murdoch University
- Language
- English
- Resource Type
- Conference paper
Metrics
108 File views/ downloads
103 Record Views