Recurrent word
Jump to navigation
Jump to search
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 nX (often much longer than the length of X) such that X appears in every block of length nX.[1][6][7] The terms minimal sequence[8] and almost periodic sequence (Muchnik, Semenov, Ushakov 2003) are also used.
Examples
[edit | edit source]- 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.[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
[edit | edit source]References
[edit | edit source]- Lua error in Module:Citation/CS1/Configuration at line 2172: attempt to index field '?' (a nil value).
- Lua error in Module:Citation/CS1/Configuration at line 2172: attempt to index field '?' (a nil value).
- Lua error in Module:Citation/CS1/Configuration at line 2172: attempt to index field '?' (a nil value).
- Lua error in Module:Citation/CS1/Configuration at line 2172: attempt to index field '?' (a nil value).
- Lua error in Module:Citation/CS1/Configuration at line 2172: attempt to index field '?' (a nil value).
- An. Muchnik, A. Semenov, M. Ushakov, Almost periodic sequences, Theoret. Comput. Sci. vol.304 no.1-3 (2003), 1-33.
