Recurrent word

From Wikipedia, the free encyclopedia
Jump to: navigation, search

In mathematics, a recurrent word or sequence is an infinite word over a finite alphabet in which every factor occurs infinitely often.[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 n:[1][6][7] the term minimal sequence is also used.[8]

Examples[edit]

  • 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 in 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]
  • More generally, all Sturmian words are recurrent.[10]

References[edit]

  1. ^ a b Lothaire (2011) p. 30
  2. ^ a b 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