Back to Search
Start Over
String Attractors for Automatic Sequences
- Publication Year :
- 2020
- Publisher :
- arXiv, 2020.
-
Abstract
- We show that it is decidable, given an automatic sequence $\bf s$ and a constant $c$, whether all prefixes of $\bf s$ have a string attractor of size $\leq c$. Using a decision procedure based on this result, we show that all prefixes of the period-doubling sequence of length $\geq 2$ have a string attractor of size $2$. We also prove analogous results for other sequences, including the Thue-Morse sequence and the Tribonacci sequence. We also provide general upper and lower bounds on string attractor size for different kinds of sequences. For example, if $\bf s$ has a finite appearance constant, then there is a string attractor for ${\bf s}[0..n-1]$ of size $O(\log n)$. If further $\bf s$ is linearly recurrent, then there is a string attractor for ${\bf s}[0..n-1]$ of size $O(1)$. For automatic sequences, the size of the smallest string attractor for ${\bf s}[0..n-1]$ is either $\Theta(1)$ or $\Theta(\log n)$, and it is decidable which case occurs. Finally, we close with some remarks about greedy string attractors.<br />Comment: revision adding significant new results due to Luke Schaeffer
Details
- Database :
- OpenAIRE
- Accession number :
- edsair.doi.dedup.....a940a83c1cd5f55cb16ed9da40f0e6c8
- Full Text :
- https://doi.org/10.48550/arxiv.2012.06840