Rahul Sharma (Editor)

Recurrent word

Updated on
Edit
Like
Comment
Share on FacebookTweet on TwitterShare on LinkedInShare on Reddit

In mathematics, a recurrent word or sequence is an infinite word over a finite alphabet in which every factor occurs infinitely often. An infinite word is recurrent if and only if it is a sesquipower.

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. The term minimal sequence or almost periodic sequence(Muchnik, Semenov, Ushakov 2003) is 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 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.
  • The Thue–Morse sequence is uniformly recurrent without being periodic, nor even eventually periodic (meaning periodic after some nonperiodic initial segment).
  • More generally, all Sturmian words are recurrent.

    • References

    Recurrent word Wikipedia
    (Text) CC BY-SA


    Similar Topics