Skip to content

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

More by Rosenfeld, Matthieu

Browse all works by Rosenfeld, Matthieu