Growth rate of binary words avoiding xxx^R

2015/02/25 by James D. Currie, Narad Rampersad, Currie, James D. +1
Computer Science · #semigroups and automata theory #Algorithms and Data Compression #Cellular Automata and Applications

paper · pdf · doi:10.48550/arxiv.1502.07014

Abstract

Consider the set of those binary words with no non-empty factors of the form xxx^R. Du, Mousavi, Schaeffer, and Shallit asked whether this set of words grows polynomially or exponentially with length. In this paper, we demonstrate the existence of upper and lower bounds on the number of such words of length n, where each of these bounds is asymptotically equivalent to a (different) function of the form Cn^{\lg n+c}, where C, c are constants.

Related

• Polynomial versus Exponential Growth in Repetition-Free Binary Words
• Binary words avoiding xx^Rx and strongly unimodal sequences
• Lower-bounds on the growth of power-free languages over large alphabets
• On the number of Dejean words over alphabets of 5, 6, 7, 8, 9 and 10 letters
• An explicit condition for boundedly supermultiplicative subshifts