Abstract: Arseny Shur

GROWTH PROPERTIES OF POWER-FREE LANGUAGES       

 

           The languages given by the restrictions on repetitions in words constitute one of the central objects to study in combinatorics of words. We deal with the problem of estimating the order of growth for such languages. The considered repetitions are powers and fractional powers of words. Power-free languages consist of all words (over an arbitrary fixed alphabet) that avoid powers exceeding some threshold value. Languages of square-free, cube-free, and overlap-free words are well-known examples of power-free languages. First we describe a fast algorithm to obtain upper bounds to the growth rates of arbitrary power-free languages. Then we show a way to turn these upper bounds to the two-sided ones and also give some numerical results. Finally, we shed some light on the asymptotic behavior of the growth rate.