Growth of power-free languages: Numerical and asymptotic bounds |
| |
Authors: | A. M. Shur |
| |
Affiliation: | 1.Department of Algebra and Discrete Mathematics,Ural State University,Yekaterinburg,Russia |
| |
Abstract: | We consider power-free languages over finite alphabets. That is, the words which are powers with the exponent greater than a given constant cannot be factors of words in these languages. We give numerical bounds of the exponential growth rate for a wide range of such languages. These bounds are obtained using the algorithms proposed by the author. On the basis of these bounds we suggest the asymptotic behaviour of the growth rate as a function of the exponent and the size of the alphabet, and give some theorems about this behaviour. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|