Growth rate of binary words avoiding xxx^R

DOI10.1016/J.TCS.2015.11.004zbMATH Open1334.68170OpenAlexW1896187825MaRDI QIDQ897919FDOQ897919

Authors Narad Rampersad, James D. Currie

Publication date 8 December 2015

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1502.07014

zbMATH Keywords

pattern avoidancegrowth rate of a languageword avoiding \(xxx^R\)

Mathematics Subject Classification ID

Combinatorics on words (68R15)

Abstract: Consider the set of those binary words with no non-empty factors of the form $xx{x}^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 $C{n}^{lgn+c}$, where $C$, $c$ are constants.

Recommendations

• Binary patterns in binary cube-free words: avoidability and growth
• Binary words avoiding xx^Rx and strongly unimodal sequences
• Binary avoidability and Thue-Morse words
• Growth properties of power-free languages
• Avoiding or limiting regularities in words

Cites work

• scientific article; zbMATH DE number 3912631 (Why is no real title available?)
• scientific article; zbMATH DE number 2235059 (Why is no real title available?)
• Growth problems for avoidable words
• Growth properties of power-free languages
• On a Special Functional Equation
• On the number of Abelian square-free words on four letters
• Pattern avoidability with involution
• Sequences with subword complexity \(2n\)
• The On-Line Encyclopedia of Integer Sequences
• Unary patterns with involution
• Uniformly growing k-th power-free homomorphisms

Cited in

(11)

• scientific article; zbMATH DE number 7559450 (Why is no real title available?)
• Binary words avoiding xx^Rx and strongly unimodal sequences
• Decision algorithms for Fibonacci-automatic words. II: Related sequences and avoidability
• On the growth rate of words in generalized Thue-Morse sequence
• Avoidability index for binary patterns with reversal
• A family of formulas with reversal of high avoidability index
• Polynomial versus exponential growth in repetition-free binary words
• Relations on words
• On the aperiodic avoidability of binary patterns with variables and reversals
• Formulas with reversal
• Avoidance bases for formulas with reversal

Describes a project that uses

Uses Software

• OEIS

This page was built for publication: Growth rate of binary words avoiding \(xxx^{R}\)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q897919)