CLR cover
Previous problem

Problem 88: Periodicity and Factor Complexity

Next problem
\( \def\sub{F} \)

The property stated in the problem provides a useful condition to detect the periodicity of infinite words.

An infinite word $x$ (indices run through natural numbers) is said to be ultimately periodic or simply u-periodic if it can be written $yz^\infty$ for some (finite) words $y$ and $z$, $z\neq \varepsilon$.

Let $\sub_x(n)$ denote the number of (distinct) factors of length $n$ occurring in the infinite word $x$. The function $\sub_x$ is called the factor (or subword) complexity function of $x$.

Show that an infinite word $x$ is u-periodic if and only if $\sub_x$ is bounded by a constant.

References

  • J. Allouche and J. O. Shallit. Automatic Sequences - Theory, Applications, Generalizations. Cambridge University Press, 2003.
  • J. Berstel and J. Karhumäki. Combinatorics on words: a tutorial. Bulletin of the EATCS, 79:178, 2003.