Growth rate of binary words avoiding xxx^R

DOI10.1016/J.TCS.2015.11.004MaRDI QIDQ897919zbMATH OpenOpenAlexFDO

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

growth rate of a languagepattern avoidanceword 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

• Growth problems for avoidable words
• Growth properties of power-free languages
• scientific article; zbMATH DE number 3912631 (Why is no real title available?)
• scientific article; zbMATH DE number 2235059 (Why is no real title available?)
• 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

(12)

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

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)