Journal article
Repetitions in Sturmian strings
Theoretical Computer Science, Vol.249(2), pp.289-303
2000
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.
Details
- Title
- Repetitions in Sturmian strings
- Authors/Creators
- F. Franěk (Author/Creator) - McMaster UniversityA. Karaman (Author/Creator) - McMaster UniversityW.F. Smyth (Author/Creator) - McMaster University
- Publication Details
- Theoretical Computer Science, Vol.249(2), pp.289-303
- Publisher
- Elsevier BV
- Identifiers
- 991005541333007891
- Copyright
- © 2000 Elsevier Science B.V.
- Murdoch Affiliation
- Murdoch University
- Language
- English
- Resource Type
- Journal article
Metrics
48 Record Views
InCites Highlights
These are selected metrics from InCites Benchmarking & Analytics tool, related to this output
- Collaboration types
- Domestic collaboration
- International collaboration
- Citation topics
- 4 Electrical Engineering, Electronics & Computer Science
- 4.182 Data Structures, Algorithms & Complexity
- 4.182.1103 Efficient Algorithms
- Web Of Science research areas
- Computer Science, Theory & Methods
- ESI research areas
- Computer Science