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. 30][Allouche & Shallit (2003) p.325][Pytheas Fogg (2002) p.2] An infinite word is recurrent if and only if it is a
sesquipower In mathematics, a sesquipower or Zimin word is a string over an alphabet with identical prefix and suffix. Sesquipowers are unavoidable patterns, in the sense that all sufficiently long strings contain one.
Formal definition
Formally, let ''A'' ...
.
[Lothaire (2011) p. 141][Berstel 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 ''n''
''X'' (often much longer than the length of ''X'') such that ''X'' appears in ''every'' block of length ''n''
''X''.
[Berthé & Rigo (2010) p.7][Allouche & Shallit (2003) p.328] The terms minimal sequence[Pytheas 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
In mathematics, a periodic sequence (sometimes called a cycle) is a sequence for which the same terms are repeated over and over:
:''a''1, ''a''2, ..., ''a'p'', ''a''1, ''a''2, ..., ''a'p'', ''a''1, ''a''2, ..., ''a' ...
, 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.[
* The ]Thue–Morse sequence
In mathematics, the Thue–Morse sequence, or Prouhet–Thue–Morse sequence, is the binary sequence (an infinite sequence of 0s and 1s) obtained by starting with 0 and successively appending the Boolean complement of the sequence obtained thus ...
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]
References
*
*
*
*
*
* An. Muchnik, A. Semenov, M. Ushakov, Almost periodic sequences, Theoret. Comput. Sci. vol.304 no.1-3 (2003), 1-33.
{{algebra-stub
Semigroup theory
Formal languages
Combinatorics on words