On repetitiveness measures of Thue-Morse words

05/19/2020

∙

by   Kanaru Kutsukake, et al.

∙

0

∙

share

We show that the size γ(t_n) of the smallest string attractor of the nth Thue-Morse word t_n is 4 for any n≥ 4, disproving the conjecture by Mantaci et al. [ICTCS 2019] that it is n. We also show that δ(t_n) = 10/3+2^4-n for n ≥ 3, where δ(w) is the maximum over all k = 1,…,|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.