论文标题
自动序列的弦吸引子
String Attractors for Automatic Sequences
论文作者
论文摘要
我们证明它是可决定的，如果$ \ bf s $的所有前缀均具有尺寸$ \ leq c $的字符串吸引子。使用基于此结果的决策过程，我们表明，长度$ \ geq 2 $的周期倍序列的所有前缀均具有尺寸$ 2 $的字符串吸引子。我们还证明了其他序列的类似结果，包括Thue-Morse序列和Tribonacci序列。 我们还为各种序列提供了弦吸引子大小的一般上限和下限。例如，如果$ \ bf s $具有有限的外观常数，则有一个$ {\ bf s}的字符串吸引子[0..n-1]尺寸$ o（\ log n）$的$。如果进一步的$ \ bf s $是线性的，则有一个$ {\ bf s} [0..n-1] $ $ o（1）$的字符串吸引子。对于自动序列，$ {\ bf s} [0..n-1] $的最小字符串吸引子的大小是$θ（1）$或$θ（\ log n）$，并且可以决定发生这种情况。最后，我们谈到了一些关于贪婪的弦吸引者的评论。
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.
