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.
Mots-clés : periodicity, Fibonacci word, Thue-Morse word, sturmian word
@article{ITA_2009__43_1_165_0,
author = {Currie, James D. and Saari, Kalle},
title = {Least periods of factors of infinite words},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
pages = {165--178},
publisher = {EDP-Sciences},
volume = {43},
number = {1},
year = {2009},
doi = {10.1051/ita:2008006},
mrnumber = {2483449},
zbl = {1162.68510},
language = {en},
url = {http://www.numdam.org/articles/10.1051/ita:2008006/}
}
TY - JOUR AU - Currie, James D. AU - Saari, Kalle TI - Least periods of factors of infinite words JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications PY - 2009 SP - 165 EP - 178 VL - 43 IS - 1 PB - EDP-Sciences UR - http://www.numdam.org/articles/10.1051/ita:2008006/ DO - 10.1051/ita:2008006 LA - en ID - ITA_2009__43_1_165_0 ER -
%0 Journal Article %A Currie, James D. %A Saari, Kalle %T Least periods of factors of infinite words %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2009 %P 165-178 %V 43 %N 1 %I EDP-Sciences %U http://www.numdam.org/articles/10.1051/ita:2008006/ %R 10.1051/ita:2008006 %G en %F ITA_2009__43_1_165_0
Currie, James D.; Saari, Kalle. Least periods of factors of infinite words. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 43 (2009) no. 1, pp. 165-178. doi : 10.1051/ita:2008006. http://www.numdam.org/articles/10.1051/ita:2008006/
[1] and , The ubiquitous Prouhet-Thue-Morse sequence, in Sequences and Their Applications: Proceedings of SETA'98. Springer Series in Discrete Mathematics and Theoretical Computer Science, C. Ding, T. Helleseth and H. Niederreiter, Eds., Springer-Verlag, London (1999) 1-16. | MR | Zbl
[2] , On the index of Sturmian words. In Jewels are forever. Springer, Berlin (1999) 287-294. | MR | Zbl
[3] and , Some properties of the factors of Sturmian sequences. Theor. Comput. Sci. 304 (2003) 365-385. | MR | Zbl
[4] and , Combinatorics on words. In A. Salomaa and G. Rozenberg, Eds., Handbook of Formal Languages, volume 1. Springer, Berlin (1997) 329-438. | MR
[5] , and , Borders of Fibonacci strings. J. Comb. Math. Comb. Comput. 20 (1996) 81-87. | MR | Zbl
[6] and , Powers in Sturmian sequences. Eur. J. Combin. 24 (2003) 377-390. | MR | Zbl
[7] and , Some characterizations of finite Sturmian words. Theor. Comput. Sci. 356 (2006) 118-125. | MR | Zbl
[8] and , Uniqueness theorems for periodic functions. Proc. Amer. Math. Soc. 16 (1965) 109-114. | MR | Zbl
[9] and , Minimal Duval extensions. Int. J. Found. Comput. Sci. 15 (2004) 349-354. | MR | Zbl
[10] , Combinatorics on Words. Cambridge University Press, Cambridge (1997). | MR | Zbl
[11] , Algebraic Combinatorics on Words, Encyclopedia of Mathematics and its Applications, Vol. 90. Cambridge University Press, Cambridge (2002). | MR | Zbl
[12] and , A note on a conjecture of Duval and Sturmian words. RAIRO-Theor. Inf. Appl. 36 (2002) 1-3. | Numdam | MR | Zbl
[13] and , Dejean's conjecture and Sturmian words. Eur. J. Combin. 28 (2007) 876-890. | MR | Zbl
[14] , Periods of factors of the Fibonacci word. in Proceedings of the Sixth International Conference on Words (WORDS'07). Institut de Mathématiques de Luminy (2007) 273-279.
Cité par Sources :
