Recurrent word

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[8] or almost periodic sequence(Muchnik, Semenov, Ushakov 2003) is also used.

Examples

References

  1. 1 2 Lothaire (2011) p. 30
  2. 1 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
This article is issued from Wikipedia - version of the Wednesday, February 03, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.