On repetitiveness measures of Thue-Morse words
Authors:
Preprint
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\geq 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 \geq 3$, where $\delta(w)$ is the maximum over all $k = 1,\ldots,|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$.
Keywords
All Related Versions
This publication has 13 references indexed in Scilit:
- Burrows-Wheeler Transform of Words Defined by Morphisms2019
- At the roots of dictionary compression: string attractors2018
- Faster Lyndon Factorization Algorithms for SLP and LZ78 Compressed TextLecture Notes in Computer Science, 2013
- Sublinear Algorithms for Approximating String CompressibilityAlgorithmica, 2012
- Crochemore Factorization of Sturmian and Other Infinite WordsLecture Notes in Computer Science, 2006
- The Smallest Grammar ProblemIEEE Transactions on Information Theory, 2005
- Burrows–Wheeler transform and Sturmian wordsInformation Processing Letters, 2003
- Enumeration of factors in the Thue-Morse wordDiscrete Applied Mathematics, 1989
- Data compression via textual substitutionJournal of the ACM, 1982
- On the Complexity of Finite SequencesIEEE Transactions on Information Theory, 1976