论文标题
大型语言在大型字母上的增长较低
Lower-bounds on the growth of power-free languages over large alphabets
论文作者
论文摘要
我们研究了某些无电语语的增长率。对于任何整数$ k $和真实的$β> 1 $，我们让$α（k，β）$是给定长度的$β$ free单词的增长率，比字母$ \ {1,2，\ ldots，k \ \} $。 Shur研究了$β\ ge2 $的$α（k，β）$的渐近行为，$ k $ to to to Infinity。他提出了关于$α（k，β）$的渐近行为为$ k $的猜想，当$ k $时为$ 1 <β<2 $。他表明，以$ \ frac {9} {8} \leβ<2 $渐近上限的猜想所保持。我们表明，他的猜想中的渐近下限存在。这意味着对于$ \ frac {9} {8} \leβ<2 $而言，猜想是正确的。
We study the growth rate of some power-free languages. For any integer $k$ and real $β>1$, we let $α(k,β)$ be the growth rate of the number of $β$-free words of a given length over the alphabet $\{1,2,\ldots, k\}$. Shur studied the asymptotic behavior of $α(k,β)$ for $β\ge2$ as $k$ goes to infinity. He suggested a conjecture regarding the asymptotic behavior of $α(k,β)$ as $k$ goes to infinity when $1<β<2$. He showed that for $\frac{9}{8}\leβ<2$ the asymptotic upper-bound holds of his conjecture holds. We show that the asymptotic lower-bound of his conjecture holds. This implies that the conjecture is true for $\frac{9}{8}\leβ<2$.
