RAIRO-Theor. Inf. Appl.
Volume 43, Number 1, January-March 2009
|Page(s)||165 - 178|
|Published online||12 March 2008|
Least Periods of Factors of Infinite Words
Department of Mathematics & Statistics, University of Winnipeg, Winnipeg, R3B2E9, Canada
2 Department of Mathematics and Turku Centre for Computer Science, University of Turku, Turku, Finland; email@example.com
Accepted: 6 February 2008
We show that any positive integer is the least period of a factor of the Thue-Morse word. We also characterize the set of least periods of factors of a Sturmian word. In particular, the corresponding set for the Fibonacci word is the set of Fibonacci numbers. As a by-product of our results, we give several new proofs and tightenings of well-known properties of Sturmian words.
Mathematics Subject Classification: 68R15
Key words: Periodicity / Fibonacci word / Thue-Morse word / Sturmian word.
© EDP Sciences, 2008
Initial download of the metrics may take a while.