2020/12/12 by Schaeffer, Luke, Shallit, Jeffrey · 1 citation
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Formal Languages and Automata Theory (cs.FL)
paper · doi:10.48550/arxiv.2012.06840
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 ≤ c. Using a decision procedure based on this result, we show that all prefixes of the period-doubling sequence of length ≥ 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.