On the number of alpha-power-free binary words for 2alpha<=7/3
On the number of alpha-power-free binary words for 2alpha<=7/3
复制标题
关于 2alpha<=7/3 的 alpha 无幂二进制字的数量
DOI：
10.1016/j.tcs.2009.01.031
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
R. Jungers
中科院分区：
文献类型：
--
作者：
V. Blondel;J. Cassaigne;R. Jungers
本文研究了（2，7/3）中有理数α为固定值时，长度为n的无α幂二进制字的个数uα（n），以及当n趋于无穷大时，u α（n）的渐近性.对于任意的α，我们证明了一个结构结果，它允许我们将序列uα（n）构造性地描述为2-正则序列。这提供了一种算法，对于固定的α，在对数时间内计算数量uα（n）。然后，推广最近的结果2+-自由字，我们描述的渐近行为uα（n）的联合谱量的一对矩阵，可以有效地构建，给定一个有理数α。当α=7/3时，我们计算了该自动机，并给出了uα（n）的渐近性质的精确估计.
We study the number uα(n) of α-power-free binary words of length n, and the asymptotics of this number when n tends to infinity, for a fixed rational number α in (2,7/3]. For any such α, we prove a structure result that allows us to describe constructively the sequence uα(n) as a 2-regular sequence. This provides an algorithm that computes the number uα(n) in logarithmic time, for fixed α. Then, generalizing recent results on 2+-free words, we describe the asymptotic behaviour of uα(n) in terms of joint spectral quantities of a pair of matrices that one can efficiently construct, given a rational number α. For α=7/3, we compute the automaton and give sharp estimates for the asymptotic behaviour of uα(n).