In mathematics, a recurrent word or sequence is an infinite word over a finite alphabet in which every factor occurs infinitely many times.Lothaire (2011) p. 30Allouche & Shallit (2003) p.325Pytheas Fogg (2002) p.2 An infinite word is recurrent if and only if it is a sesquipower.Lothaire (2011) p. 141Berstel et al (2009) p.133
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.Berthé & Rigo (2010) p.7Allouche & Shallit (2003) p.328 The terms minimal sequencePytheas Fogg (2002) p.6 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. The Thue–Morse sequence is uniformly recurrent without being periodic, nor even eventually periodic (meaning periodic after some nonperiodic initial segment).Lothaire (2011) p.31 All Sturmian words are uniformly recurrent.Berthé & Rigo (2010) p.177
Notes
References
An. Muchnik, A. Semenov, M. Ushakov, Almost periodic sequences, Theoret. Comput. Sci. vol.304 no.1-3 (2003), 1-33.