Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Recurrent word
open-in-new
<h2 id="examples">Examples</h2> <ul><li>The easiest way to make a recurrent sequence is to form a <a href="/facts/Periodic_sequence/eIJhDfJn">periodic sequence</a>, one where the sequence repeats entirely after a given number <i>m</i> of steps. Such a sequence is then uniformly recurrent and <i>n</i><i>X</i> can be set to any multiple of <i>m</i> that is larger than twice the length of <i>X</i>. A recurrent sequence that is ultimately periodic is purely periodic.<a class="footnote-ref" id="fnref:10" href="#fn:10"><sup>10</sup></a></li> <li>The <a href="/facts/Thue%E2%80%93Morse_sequence/1bvLMTBD">Thue–Morse sequence</a> is uniformly recurrent <i>without</i> being periodic, nor even eventually periodic (meaning periodic after some nonperiodic initial segment).<a class="footnote-ref" id="fnref:11" href="#fn:11"><sup>11</sup></a></li> <li>All <a href="/facts/Sturmian_word/tbwHJPb6">Sturmian words</a> are uniformly recurrent.<a class="footnote-ref" id="fnref:12" href="#fn:12"><sup>12</sup></a></li></ul> <h2 id="notes">Notes</h2> <ul><li>Allouche, Jean-Paul; <a href="/facts/Jeffrey_Shallit/4bmJgyIH">Shallit, Jeffrey</a> (2003). <i>Automatic Sequences: Theory, Applications, Generalizations</i>. <a href="/facts/Cambridge_University_Press/fgEBSSRq">Cambridge University Press</a>. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-0-521-82332-6. <a href="/facts/Zbl_(identifier)/P6rFxKKx">Zbl</a> <a href="https://zbmath.org/?format=complete&q=an:1086.11015">1086.11015</a>.</li> <li><a href="/facts/Jean_Berstel/qEnyAh29">Berstel, Jean</a>; Lauve, Aaron; Reutenauer, Christophe; Saliola, Franco V. (2009). <a href="https://www.ams.org/bookpages/crmm-27"><i>Combinatorics on words. Christoffel words and repetitions in words</i></a>. CRM Monograph Series. Vol. 27. Providence, RI: <a href="/facts/American_Mathematical_Society/fr5gotCt">American Mathematical Society</a>. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-0-8218-4480-9. <a href="/facts/Zbl_(identifier)/P6rFxKKx">Zbl</a> <a href="https://zbmath.org/?format=complete&q=an:1161.68043">1161.68043</a>.</li> <li><a href="/facts/Val%C3%A9rie_Berth%C3%A9/0puS3RSe">Berthé, Valérie</a>; Rigo, Michel, eds. (2010). <i>Combinatorics, automata, and number theory</i>. Encyclopedia of Mathematics and its Applications. Vol. 135. Cambridge: <a href="/facts/Cambridge_University_Press/fgEBSSRq">Cambridge University Press</a>. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-0-521-51597-9. <a href="/facts/Zbl_(identifier)/P6rFxKKx">Zbl</a> <a href="https://zbmath.org/?format=complete&q=an:1197.68006">1197.68006</a>.</li> <li><a href="/facts/M._Lothaire/pC43ftpJ">Lothaire, M.</a> (2011). <i>Algebraic combinatorics on words</i>. Encyclopedia of Mathematics and Its Applications. Vol. 90. With preface by Jean Berstel and Dominique Perrin (Reprint of the 2002 hardback ed.). Cambridge University Press. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-0-521-18071-9. <a href="/facts/Zbl_(identifier)/P6rFxKKx">Zbl</a> <a href="https://zbmath.org/?format=complete&q=an:1221.68183">1221.68183</a>.</li> <li>Pytheas Fogg, N. (2002). <a href="/facts/Val%C3%A9rie_Berth%C3%A9/0puS3RSe">Berthé, Valérie</a>; Ferenczi, Sébastien; Mauduit, Christian; Siegel, Anne (eds.). <i>Substitutions in dynamics, arithmetics and combinatorics</i>. Lecture Notes in Mathematics. Vol. 1794. Berlin: <a href="/facts/Springer-Verlag/nAesf6nT">Springer-Verlag</a>. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 3-540-44141-7. <a href="/facts/Zbl_(identifier)/P6rFxKKx">Zbl</a> <a href="https://zbmath.org/?format=complete&q=an:1014.11015">1014.11015</a>.</li> <li>An. Muchnik, A. Semenov, M. Ushakov, Almost periodic sequences, Theoret. Comput. Sci. vol.304 no.1-3 (2003), 1-33.</li></ul> <h2 id="references">References</h2> <ol> <li id="fn:1"><p>Lothaire (2011) p. 30 <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li> <li id="fn:2"><p>Allouche & Shallit (2003) p.325 <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li> <li id="fn:3"><p>Pytheas Fogg (2002) p.2 <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li> <li id="fn:4"><p>Lothaire (2011) p. 141 <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li> <li id="fn:5"><p>Berstel et al (2009) p.133 <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li> <li id="fn:6"><p>Lothaire (2011) p. 30 <a href="#fnref:6" class="footnote-back-ref">↩</a></p></li> <li id="fn:7"><p>Berthé & Rigo (2010) p.7 <a href="#fnref:7" class="footnote-back-ref">↩</a></p></li> <li id="fn:8"><p>Allouche & Shallit (2003) p.328 <a href="#fnref:8" class="footnote-back-ref">↩</a></p></li> <li id="fn:9"><p>Pytheas Fogg (2002) p.6 <a href="#fnref:9" class="footnote-back-ref">↩</a></p></li> <li id="fn:10"><p>Allouche & Shallit (2003) p.325 <a href="#fnref:10" class="footnote-back-ref">↩</a></p></li> <li id="fn:11"><p>Lothaire (2011) p.31 <a href="#fnref:11" class="footnote-back-ref">↩</a></p></li> <li id="fn:12"><p>Berthé & Rigo (2010) p.177 <a href="#fnref:12" class="footnote-back-ref">↩</a></p></li> </ol>