Growth rate of binary words avoiding xxxR
Metadata
Show full item recordAuthor
Currie, James D.
Rampersad, Narad
Date
2016 - 01Citation
Theoret. Comput. Sci. 609 (2016), 456–468
Abstract
摘要考虑爬山e 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 of the form n^{lg n+o(lg n)} on the number of such words of length n, where lg n denotes the base-2 logarithm of n.