# Recurrent word

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Recurrent_word
> Markdown URL: https://mediated.wiki/source/Recurrent_word.md
> Source: https://en.wikipedia.org/wiki/Recurrent_word
> Source revision: 1297214573
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

In mathematics, a '''recurrent word''' or '''sequence''' is an infinite word over a finite alphabet in which every factor occurs infinitely many times.<ref name=LotII30>Lothaire (2011) p.&nbsp;30</ref><ref name=AS325>Allouche & Shallit (2003) p.325</ref><ref name=PF2>Pytheas Fogg (2002) p.2</ref>  An infinite word is recurrent if and only if it is a [sesquipower](/source/sesquipower).<ref name=LotII141>Lothaire (2011) p.&nbsp;141</ref><ref name=BLRS133>Berstel et al (2009) p.133</ref>

A '''uniformly recurrent word''' is a recurrent word in which for any given factor ''X'' in the sequence, there is some length ''n''<sub>''X''</sub> (often much longer than the length of ''X'') such that ''X'' appears in ''every'' block of length ''n''<sub>''X''</sub>.<ref name=LotII30/><ref name=BR7>Berthé & Rigo (2010) p.7</ref><ref name=AS328>Allouche & Shallit (2003) p.328</ref> The terms '''minimal sequence'''<ref name=PF6>Pytheas Fogg (2002) p.6</ref> 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](/source/periodic_sequence), one where the sequence repeats entirely after a given number ''m'' of steps.  Such a sequence is then uniformly recurrent and ''n''<sub>''X''</sub> 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.<ref name=AS325/>
* The [Thue–Morse sequence](/source/Thue%E2%80%93Morse_sequence) is uniformly recurrent ''without'' being periodic, nor even eventually periodic (meaning periodic after some nonperiodic initial segment).<ref name=LotII31>Lothaire (2011) p.31</ref>  
* All [Sturmian word](/source/Sturmian_word)s are uniformly recurrent.<ref name=BR177>Berthé & Rigo (2010) p.177</ref>

==Notes==
{{reflist|colwidth=30em}}

==References==
*{{cite book | last1 = Allouche | first1 = Jean-Paul | last2 = Shallit | first2 = Jeffrey | author2-link = Jeffrey Shallit | isbn = 978-0-521-82332-6 | publisher = [Cambridge University Press](/source/Cambridge_University_Press) | title = Automatic Sequences: Theory, Applications, Generalizations | year = 2003 | zbl=1086.11015 }}
* {{cite book | last1=Berstel | first1=Jean | last2=Lauve | first2=Aaron | last3=Reutenauer | first3=Christophe | last4=Saliola | first4=Franco V. | author1-link = Jean Berstel | title=Combinatorics on words. Christoffel words and repetitions in words | series=CRM Monograph Series | volume=27 | location=Providence, RI | publisher=[American Mathematical Society](/source/American_Mathematical_Society) | year=2009 | isbn=978-0-8218-4480-9 | url=https://www.ams.org/bookpages/crmm-27 | zbl=1161.68043 }}
* {{cite book | editor1-last=Berthé | editor1-first=Valérie|editor-link= Valérie Berthé | editor2-last=Rigo | editor2-first=Michel | title=Combinatorics, automata, and number theory | series=Encyclopedia of Mathematics and its Applications | volume=135 | location=Cambridge | publisher=[Cambridge University Press](/source/Cambridge_University_Press) | year=2010 | isbn=978-0-521-51597-9 | zbl=1197.68006  }}
* {{cite book | last=Lothaire | first=M. | authorlink=M. Lothaire | title=Algebraic combinatorics on words | others=With preface by Jean Berstel and Dominique Perrin | edition=Reprint of the 2002 hardback | series=Encyclopedia of Mathematics and Its Applications | volume=90| publisher=Cambridge University Press | year=2011 | isbn=978-0-521-18071-9 | zbl=1221.68183 }}
* {{cite book | last=Pytheas Fogg | first=N. | editor1=Berthé, Valérie|editor1-link=Valérie Berthé|editor2=Ferenczi, Sébastien|editor3=Mauduit, Christian|editor4=Siegel, Anne | title=Substitutions in dynamics, arithmetics and combinatorics | series=Lecture Notes in Mathematics | volume=1794 | location=Berlin | publisher=[Springer-Verlag](/source/Springer-Verlag) | year=2002 | 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.

Category:Semigroup theory
Category:Formal languages
Category:Combinatorics on words

{{algebra-stub}}

---
Adapted from the Wikipedia article [Recurrent word](https://en.wikipedia.org/wiki/Recurrent_word) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Recurrent_word?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.