Least periods of factors of infinite words

James D. Currie; Kalle Saari

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2009)

  • Volume: 43, Issue: 1, page 165-178
  • ISSN: 0988-3754

Abstract

top
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.

How to cite

top

Currie, James D., and Saari, Kalle. "Least periods of factors of infinite words." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 43.1 (2009): 165-178. <http://eudml.org/doc/245812>.

@article{Currie2009,
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.},
author = {Currie, James D., Saari, Kalle},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {periodicity; Fibonacci word; Thue-Morse word; sturmian word; Sturmian word},
language = {eng},
number = {1},
pages = {165-178},
publisher = {EDP-Sciences},
title = {Least periods of factors of infinite words},
url = {http://eudml.org/doc/245812},
volume = {43},
year = {2009},
}

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
PB - EDP-Sciences
VL - 43
IS - 1
SP - 165
EP - 178
AB - 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.
LA - eng
KW - periodicity; Fibonacci word; Thue-Morse word; sturmian word; Sturmian word
UR - http://eudml.org/doc/245812
ER -

References

top
  1. [1] J.-P. Allouche and J. Shallit, 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. Zbl1005.11005MR1843077
  2. [2] J. Berstel, On the index of Sturmian words. In Jewels are forever. Springer, Berlin (1999) 287–294. Zbl0982.11010MR1719097
  3. [3] W.-T. Cao and Z.-Y. Wen, Some properties of the factors of Sturmian sequences. Theor. Comput. Sci. 304 (2003) 365–385. Zbl1045.68109MR1992341
  4. [4] C. Choffrut and J. Karhumäki, Combinatorics on words. In A. Salomaa and G. Rozenberg, Eds., Handbook of Formal Languages, volume 1. Springer, Berlin (1997) 329–438. MR1469998
  5. [5] L.J. Cummings, D.W. Moore and J. Karhumäki, Borders of Fibonacci strings. J. Comb. Math. Comb. Comput. 20 (1996) 81–87. Zbl0847.68085MR1376699
  6. [6] D. Damanik and D. Lenz, Powers in Sturmian sequences. Eur. J. Combin. 24 (2003) 377–390. Zbl1030.68068MR1975942
  7. [7] A. de Luca and A. De Luca, Some characterizations of finite Sturmian words. Theor. Comput. Sci. 356 (2006) 118–125. Zbl1160.68481MR2217831
  8. [8] N.J. Fine and H.S. Wilf, Uniqueness theorems for periodic functions. Proc. Amer. Math. Soc. 16 (1965) 109–114. Zbl0131.30203MR174934
  9. [9] T. Harju and D. Nowotka, Minimal Duval extensions. Int. J. Found. Comput. Sci. 15 (2004) 349–354. Zbl1067.68112MR2071463
  10. [10] M. Lothaire, Combinatorics on Words. Cambridge University Press, Cambridge (1997). Zbl0874.20040MR1475463
  11. [11] M. Lothaire, Algebraic Combinatorics on Words, Encyclopedia of Mathematics and its Applications, Vol. 90. Cambridge University Press, Cambridge (2002). Zbl1001.68093MR1905123
  12. [12] F. Mignosi and L.Q. Zamboni, A note on a conjecture of Duval and Sturmian words. RAIRO-Theor. Inf. Appl. 36 (2002) 1–3. Zbl1013.68152MR1928155
  13. [13] M. Mohammad-Noori and J.D. Currie, Dejean’s conjecture and Sturmian words. Eur. J. Combin. 28 (2007) 876–890. Zbl1111.68096MR2300768
  14. [14] K. Saari, 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. 

NotesEmbed ?

top

You must be logged in to post comments.