Recurrent word explained

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]

References

• Book: Allouche . Jean-Paul . Shallit . Jeffrey . Jeffrey Shallit . 978-0-521-82332-6 . . Automatic Sequences: Theory, Applications, Generalizations . 2003 . 1086.11015 .
• Book: Berstel . Jean . Lauve . Aaron . Reutenauer . Christophe . Saliola . Franco V. . Jean Berstel . Combinatorics on words. Christoffel words and repetitions in words . CRM Monograph Series . 27 . Providence, RI . . 2009 . 978-0-8218-4480-9 . 1161.68043 .
• Book: Berthé . Valérie. Valérie Berthé . Rigo . Michel . Combinatorics, automata, and number theory . Encyclopedia of Mathematics and its Applications . 135 . Cambridge . . 2010 . 978-0-521-51597-9 . 1197.68006 .
• Book: Lothaire, M. . M. Lothaire

. M. Lothaire . Algebraic combinatorics on words . With preface by Jean Berstel and Dominique Perrin . Reprint of the 2002 hardback . Encyclopedia of Mathematics and Its Applications . 90. Cambridge University Press . 2011 . 978-0-521-18071-9 . 1221.68183 .

• Book: Pytheas Fogg, N. . Berthé, Valérie. Valérie Berthé. Ferenczi, Sébastien. Mauduit, Christian. Siegel, Anne . Substitutions in dynamics, arithmetics and combinatorics . Lecture Notes in Mathematics . 1794 . Berlin . . 2002 . 3-540-44141-7 . 1014.11015 .
• An. Muchnik, A. Semenov, M. Ushakov, Almost periodic sequences, Theoret. Comput. Sci. vol.304 no.1-3 (2003), 1-33.

Notes and References

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