In mathematics, a recurrent word or sequence is an infinite word over a finite alphabet in which every factor occurs infinitely many times. An infinite word is recurrent if and only if it is a sesquipower.
A uniformly recurrent word is a recurrent word in which for any given factor X in the sequence, there is some length nX (often much longer than the length of X) such that X appears in every block of length nX. The terms minimal sequence and almost periodic sequence (Muchnik, Semenov, Ushakov 2003) are also used.
Examples
- The easiest way to make a recurrent sequence is to form a periodic sequence, one where the sequence repeats entirely after a given number m of steps. Such a sequence is then uniformly recurrent and nX can be set to any multiple of m that is larger than twice the length of X. A recurrent sequence that is ultimately periodic is purely periodic.10
- The Thue–Morse sequence is uniformly recurrent without being periodic, nor even eventually periodic (meaning periodic after some nonperiodic initial segment).11
- All Sturmian words are uniformly recurrent.12
Notes
- Allouche, Jean-Paul; Shallit, Jeffrey (2003). Automatic Sequences: Theory, Applications, Generalizations. Cambridge University Press. ISBN 978-0-521-82332-6. Zbl 1086.11015.
- Berstel, Jean; Lauve, Aaron; Reutenauer, Christophe; Saliola, Franco V. (2009). Combinatorics on words. Christoffel words and repetitions in words. CRM Monograph Series. Vol. 27. Providence, RI: American Mathematical Society. ISBN 978-0-8218-4480-9. Zbl 1161.68043.
- Berthé, Valérie; Rigo, Michel, eds. (2010). Combinatorics, automata, and number theory. Encyclopedia of Mathematics and its Applications. Vol. 135. Cambridge: Cambridge University Press. ISBN 978-0-521-51597-9. Zbl 1197.68006.
- Lothaire, M. (2011). Algebraic combinatorics on words. Encyclopedia of Mathematics and Its Applications. Vol. 90. With preface by Jean Berstel and Dominique Perrin (Reprint of the 2002 hardback ed.). Cambridge University Press. ISBN 978-0-521-18071-9. Zbl 1221.68183.
- Pytheas Fogg, N. (2002). Berthé, Valérie; Ferenczi, Sébastien; Mauduit, Christian; Siegel, Anne (eds.). Substitutions in dynamics, arithmetics and combinatorics. Lecture Notes in Mathematics. Vol. 1794. Berlin: Springer-Verlag. ISBN 3-540-44141-7. Zbl 1014.11015.
- An. Muchnik, A. Semenov, M. Ushakov, Almost periodic sequences, Theoret. Comput. Sci. vol.304 no.1-3 (2003), 1-33.
References
Lothaire (2011) p. 30 ↩
Allouche & Shallit (2003) p.325 ↩
Pytheas Fogg (2002) p.2 ↩
Lothaire (2011) p. 141 ↩
Berstel et al (2009) p.133 ↩
Lothaire (2011) p. 30 ↩
Berthé & Rigo (2010) p.7 ↩
Allouche & Shallit (2003) p.328 ↩
Pytheas Fogg (2002) p.6 ↩
Allouche & Shallit (2003) p.325 ↩
Lothaire (2011) p.31 ↩
Berthé & Rigo (2010) p.177 ↩