On repetitiveness measures of Thue-Morse words

We show that the size $γ(t_n)$ of the smallest string attractor of the $n$th Thue-Morse word $t_n$ is 4 for any $n\geq 4$, disproving the conjecture by Mantaci et al. [ICTCS 2019] that it is $n$. We also show that $δ(t_n) = \frac{10}{3+2^{4-n}}$ for $n \geq 3$, where $δ(w)$ is the maximum over all $...

Szczegółowa specyfikacja

Opis bibliograficzny

Główni autorzy:	Kutsukake, Kanaru, Matsumoto, Takuya, Nakashima, Yuto, Inenaga, Shunsuke, Bannai, Hideo, Takeda, Masayuki
Format:	Artykuł
Wydane:	2020
Hasła przedmiotowe:	Data Structures and Algorithms Discrete Mathematics
Dostęp online:	https://arxiv.org/abs/2005.09524 http://arxiv.org/abs/2005.09524
Etykiety:	Dodaj etykietę Nie ma etykietki, Dołącz pierwszą etykiete!