Recurrent word

2020 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