String Attractors for Automatic Sequences

Luke Schaeffer, Jeffrey Shallit

We show that it is decidable, given an automatic sequence $\mathbf{s}$ and a constant $c$, whether all prefixes of $\mathbf{s}$ have a string attractor of size $\le c$. Using a decision pro…