RAIRO-Theor. Inf. Appl. (2008)
DOI: 10.1051/ita:2008006

Least periods of factors of infinite words

James D. Currie¹ and Kalle Saari<sup>2

1</sup>  Department of Mathematics & Statistics, University of Winnipeg, Winnipeg, R3B2E9, Canada
²  Department of Mathematics and Turku Centre for Computer Science, University of Turku, Turku, Finland; kasaar@utu.fi

(Received November 28, 2007. Accepted February 6, 2008. Published online 12 March 2008.)

Abstract
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