Least Periods of Factors of Infinite Words
RAIRO - Theoretical Informatics and Applications (2008)
- Volume: 43, Issue: 1, page 165-178
- ISSN: 0988-3754
Access Full Article
top
Abstract
topHow to cite
topCurrie, 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- 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.
- J. Berstel, On the index of Sturmian words. In Jewels are forever. Springer, Berlin (1999) 287–294.
- W.-T. Cao and Z.-Y. Wen, Some properties of the factors of Sturmian sequences. Theor. Comput. Sci.304 (2003) 365–385.
- 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.
- L.J. Cummings, D.W. Moore and J. Karhumäki, Borders of Fibonacci strings. J. Comb. Math. Comb. Comput.20 (1996) 81–87.
- D. Damanik and D. Lenz, Powers in Sturmian sequences. Eur. J. Combin.24 (2003) 377–390.
- A. de Luca and A. De Luca, Some characterizations of finite Sturmian words. Theor. Comput. Sci.356 (2006) 118–125.
- N.J. Fine and H.S. Wilf, Uniqueness theorems for periodic functions. Proc. Amer. Math. Soc.16 (1965) 109–114.
- T. Harju and D. Nowotka, Minimal Duval extensions. Int. J. Found. Comput. Sci.15 (2004) 349–354.
- M. Lothaire, Combinatorics on Words. Cambridge University Press, Cambridge (1997).
- M. Lothaire, Algebraic Combinatorics on Words, Encyclopedia of Mathematics and its Applications, Vol. 90. Cambridge University Press, Cambridge (2002).
- F. Mignosi and L.Q. Zamboni, A note on a conjecture of Duval and Sturmian words. RAIRO-Theor. Inf. Appl.36 (2002) 1–3.
- M. Mohammad-Noori and J.D. Currie, Dejean's conjecture and Sturmian words. Eur. J. Combin.28 (2007) 876–890.
- 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.
Citations in EuDML Documents
topNotesEmbed ?
topYou 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.