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.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.