# Recurrent word

From Encyclopedia of Mathematics

2010 Mathematics Subject Classification: *Primary:* 68R15 [MSN][ZBL]

An infinite word over an alphabet $A$ (finite or infinite) in which every factor occurs infinitely often. It is sufficient for a one-sided infinite word (an element of $A^{\mathbf{N}}$) to be recurrent that every prefix occurs at least once again.

A word is uniformly recurrent if for every factor $f$ there is an $N = N(f)$ such that $f$ occurs in every factor of length $N$.

The Thue–Morse sequence is uniformly recurrent.

#### References

- Lothaire, M. "Algebraic Combinatorics on Words", Encyclopedia of Mathematics and its Applications
**90**, Cambridge University Press (2002) ISBN 0-521-81220-8. Zbl 1001.68093 - Sapir, Mark V. "Combinatorial algebra: syntax and semantics" with contributions by Victor S. Guba and Mikhail V. Volkov. Springer Monographs in Mathematics. Springer (2014) SBN 978-3-319-08030-7 Zbl 1319.05001

**How to Cite This Entry:**

Recurrent word.

*Encyclopedia of Mathematics.*URL: http://encyclopediaofmath.org/index.php?title=Recurrent_word&oldid=39279