Least Periods of Factors of Infinite Words

James D. Currie; Kalle Saari

RAIRO - Theoretical Informatics and Applications (2008)

  • 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 43.1 (2008): 165-178. <http://eudml.org/doc/92904>.

@article{Currie2008,
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},
keywords = {Periodicity; Fibonacci word; Thue-Morse word; Sturmian word.; periodicity; Sturmian word},
language = {eng},
month = {3},
number = {1},
pages = {165-178},
publisher = {EDP Sciences},
title = {Least Periods of Factors of Infinite Words},
url = {http://eudml.org/doc/92904},
volume = {43},
year = {2008},
}

TY - JOUR
AU - Currie, James D.
AU - Saari, Kalle
TI - Least Periods of Factors of Infinite Words
JO - RAIRO - Theoretical Informatics and Applications
DA - 2008/3//
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.; periodicity; Sturmian word
UR - http://eudml.org/doc/92904
ER -

References

top
  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.  
  2. J. Berstel, On the index of Sturmian words. In Jewels are forever. Springer, Berlin (1999) 287–294.  
  3. W.-T. Cao and Z.-Y. Wen, Some properties of the factors of Sturmian sequences. Theor. Comput. Sci.304 (2003) 365–385.  
  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.  
  5. L.J. Cummings, D.W. Moore and J. Karhumäki, Borders of Fibonacci strings. J. Comb. Math. Comb. Comput.20 (1996) 81–87.  
  6. D. Damanik and D. Lenz, Powers in Sturmian sequences. Eur. J. Combin.24 (2003) 377–390.  
  7. A. de Luca and A. De Luca, Some characterizations of finite Sturmian words. Theor. Comput. Sci.356 (2006) 118–125.  
  8. N.J. Fine and H.S. Wilf, Uniqueness theorems for periodic functions. Proc. Amer. Math. Soc.16 (1965) 109–114.  
  9. T. Harju and D. Nowotka, Minimal Duval extensions. Int. J. Found. Comput. Sci.15 (2004) 349–354.  
  10. M. Lothaire, Combinatorics on Words. Cambridge University Press, Cambridge (1997).  
  11. M. Lothaire, Algebraic Combinatorics on Words, Encyclopedia of Mathematics and its Applications, Vol. 90. Cambridge University Press, Cambridge (2002).  
  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.  
  13. M. Mohammad-Noori and J.D. Currie, Dejean's conjecture and Sturmian words. Eur. J. Combin.28 (2007) 876–890.  
  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.