We prove that the property of being closed (resp., palindromic, rich, privileged trapezoidal, balanced) is expressible in first-order logic for automatic (and some related) sequences. It therefore follows that the characteristic function of those $n$ for which an automatic sequence $f x$ has a closed (resp., palindromic, privileged, rich, trapezoidal, balanced) factor of length? $n$ is itself automatic. For privileged words this requires a new characterization of the privileged property. We compute the corresponding characteristic functions for various famous sequences, such as the Thue-Morse sequence, the Rudin-Shapiro sequence, the ordinary? paperfolding sequence, the period-doubling sequence, and the Fibonacci sequence. Finally, we also show that the function counting the total number of palindromic factors in the prefix of length $n$ of a $k$-automatic sequence is not $k$-synchronized.
展开▼
机译:我们证明了封闭的性质(重复,回文,丰富,特权梯形,平衡)在自动(和一些相关)序列的一阶逻辑中是可表示的。因此,自动序列$ bf x $具有闭合的(分别是回文,回文,特权,丰富,梯形,平衡)长度因数的那些$ n $的特征函数是否成立? $ n $本身是自动的。对于特权字,这需要对特权属性进行新的表征。我们计算各种著名序列的相应特征函数,例如Thue-Morse序列,Rudin-Shapiro序列,普通?折页序列,倍增周期序列和斐波那契序列。最后,我们还表明,在$ k $自动序列的长度为$ n $的前缀中计算回文因子总数的函数不是$ k $同步的。
展开▼