Opening book details…
Can I read Lower-bounds on the Growth of Power-free Languages Over Large Alphabets on EtoBox?
Lower-bounds on the Growth of Power-free Languages Over Large Alphabets by Rosenfeld, Matthieu is a scholarly article available to read on EtoBox.
What is Lower-bounds on the Growth of Power-free Languages Over Large Alphabets about?
We study the growth rate of some power-free languages. For any integer $k$ and real $\beta>1$, we let $\alpha(k,\beta)$ be the growth rate of the number of $\beta$-free words of a given length over the alphabet $\{1,2,\ldots, k\}$. Shur studied the asymptotic behavior of $\alpha(k,\beta)$ for $\beta\ge2$ as $k$ goes to infinity. He suggested a conjecture regarding the asymptotic behavior of $\alpha(k,\beta)$ as $k$ goes to infinity when $1<\beta<2$. He showed that for $\frac{9}{8}\le\beta<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\beta<2$.
- Author
- Rosenfeld, Matthieu
- Published
- 2020
- Language
- EN