Recurrent word

In mathematics, a recurrent word or sequence is an infinite word over a finite alphabet in which every factor occurs infinitely many times. ^{[1] [2] [3]} An infinite word is recurrent if and only if it is a sesquipower. ^{[4] [5]}

A uniformly recurrent word is a recurrent word in which for any given factor X in the sequence, there is some length n_X (often much longer than the length of X) such that X appears in every block of length n_X. ^{[1] [6] [7]} The terms minimal sequence ^[8] 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 n_X 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. ^[2]
• The Thue–Morse sequence is uniformly recurrent without being periodic, nor even eventually periodic (meaning periodic after some nonperiodic initial segment). ^[9]
• All Sturmian words are uniformly recurrent. ^[10]

Notes

1. Lothaire (2011) p. 30
2. Allouche & Shallit (2003) p.325
3. Pytheas Fogg (2002) p.2
4. Lothaire (2011) p. 141
5. Berstel et al (2009) p.133
6. Berthé & Rigo (2010) p.7
7. Allouche & Shallit (2003) p.328
8. Pytheas Fogg (2002) p.6
9. Lothaire (2011) p.31
10. Berthé & Rigo (2010) p.177

References

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