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 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
  • 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]
gollark: ++exec```luafunction factorial(x)local a = 1for i = 1, x do a = a * iendprint("fact", a)if a == 0 then return 1 endreturn aendfunction scream(x, a, b)print (x, a, b)if a == 0 thenif b == 0 thenreturn factorial(x)else return math.pow(factorial(x), scream(factorial(x), 0, b - 1))endendlocal g = factorial(scream(x, a - 1, b))return math.pow(g, g) endprint(scream(5, 2, 2))```
gollark: ++exec```luafunction factorial(x)if x == 0 then return 1 endlocal a = 1for i = 1, x do a = a * iendprint("fact", a)return aendfunction scream(x, a, b)print (x, a, b)if a == 0 thenif b == 0 thenreturn factorial(x)else return math.pow(factorial(x), scream(factorial(x), 0, b - 1))endendlocal g = factorial(scream(x, a - 1, b))return math.pow(g, g) endprint(scream(5, 2, 2))```
gollark: ++exec```luafunction factorial(x)if x == 0 then return 1 endlocal a = 1for i = 1, x do a = a * iendreturn aendfunction scream(x, a, b)if a == 0 thenif b == 0 thenreturn factorial(x)else return math.pow(factorial(x), scream(factorial(x), 0, b - 1))endendlocal g = factorial(scream(x, a - 1, b))return math.pow(g, g) endprint(scream(5, 2, 2))```
gollark: ++exec```luafunction factorial(x)local a = 1for i = 1, x do a = a * iendprint("fact", a)return aendfunction scream(x, a, b)print (x, a, b)if a == 0 thenif b == 0 thenreturn factorial(x)else return math.pow(factorial(x), scream(factorial(x), 0, b - 1))endendlocal g = factorial(scream(x, a - 1, b))return math.pow(g, g) endprint(scream(5, 2, 2))```
gollark: ++exec```luafunction factorial(x)local a = 1for i = 1, x do a = a * iendreturn aendfunction scream(x, a, b)if a == 0 thenif b == 0 thenreturn factorial(x) + 1else return math.pow(factorial(x), scream(factorial(x), 0, b - 1))endendlocal g = factorial(scream(x, a - 1, b))return math.pow(g, g) endprint(scream(5, 2, 2))```

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
  • 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. 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. 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. 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. 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.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.