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.

Review text

The history of the investigation of words avoiding a given pattern reaches to the very roots of the discipline of combinatorics on words. The infinite word of Thue-Morse is the first known cube-free infinite word. Words avoiding various variants of cube words have been investigated. Since it is often not difficult to find an infinite word avoiding a given pattern, the interest moved to the investigation of other related questions. One of them is the growth rate: what is the speed of growth of the function describing the number of words of length \(n\) avoiding the pattern. The current paper shows, in a non-trivial way, that the number of words avoiding the non-empty factor \(xxx^{R}\), where \(x^{R}\) is the mirror image of the word \(x\), can be bounded both from above and from below by functions of the form \(n^{\log_{2}n+o\left( \log_{2}n\right) }\), answering in this way a question of \textit{C. F. Du} et al. [``Decision algorithms for Fibonacci-automatic words, with applications to pattern avoidance, Preprint, \url{arXiv:1406.0670}].

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)