String Attractors for Automatic Sequences
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2020
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911892801323008 |
|---|---|
| author | Schaeffer, Luke Shallit, Jeffrey |
| author_facet | Schaeffer, Luke Shallit, Jeffrey |
| contents | 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 $Θ(1)$ or $Θ(\log n)$, and it is decidable which case occurs. Finally, we close with some remarks about greedy string attractors. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2012_06840 |
| institution | arXiv |
| publishDate | 2020 |
| record_format | arxiv |
| spellingShingle | String Attractors for Automatic Sequences Schaeffer, Luke Shallit, Jeffrey Formal Languages and Automata Theory Discrete Mathematics Combinatorics 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 $Θ(1)$ or $Θ(\log n)$, and it is decidable which case occurs. Finally, we close with some remarks about greedy string attractors. |
| title | String Attractors for Automatic Sequences |
| topic | Formal Languages and Automata Theory Discrete Mathematics Combinatorics |
| url | https://arxiv.org/abs/2012.06840 |