On repetitiveness measures of Thue-Morse words

Abstract

We show that the size $\gamma (t_n)$ of the smallest string attractor of the $n$th Thue-Morse word $t_n$ is 4 for any $n\ge 4$, disproving the conjecture by Mantaci et al. [ICTCS 2019] that it is $n$. We also show that $\delta (t_n)=\frac{10}{3+2^{4-n}}$ for $n\ge 3$, where $\delta (w)$ is the maximum over all $k=1,\dots ,|w|$, the number of distinct substrings of length $k$ in $w$ divided by $k$, which is a measure of repetitiveness recently studied by Kociumaka et al. [LATIN 2020]. Furthermore, we show that the number $z(t_n)$ of factors in the self-referencing Lempel-Ziv factorization of $t_n$ is exactly $2n$.

accepted to SPIRE 2020