Recurrent word

Uses your system voice; voice and rate in settings.

Snapshot

≈ 2 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

In mathematics, a recurrent word or sequence is an infinite word over a finite alphabet in which every factor occurs infinitely many times. 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 n X (often much longer than the length of X) such that X appears in every block of length n X . The terms minimal sequence and almost periodic sequence (Muchnik, Semenov, Ushakov 2003) are also used.

In mathematics, a recurrent word or sequence is an infinite word over a finite alphabet in which every factor occurs infinitely many times. 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 n X (often much longer than the length of X) such that X appears in every block of length n X . The terms minimal sequence 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, one where the sequence repeats entirely after a given number m of steps. Such a sequence is then uniformly recurrent and n X 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). All Sturmian words are uniformly recurrent.

References

An. Muchnik, A. Semenov, M. Ushakov, Almost periodic sequences, Theoret. Comput. Sci. vol.304 no.1-3 (2003), 1-33.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1297214573 under CC BY-SA 4.0; modifications have been made.

Sources cited in this revision

No external citation was extracted for this revision. That is a statement about the source, not a claim that none exists.