Growth rate of binary words avoiding xxx^R

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

Authors: Narad Rampersad, James D. Currie 

Publication date: 8 December 2015

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

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.

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

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

zbMATH Keywords

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

Mathematics Subject Classification ID

Combinatorics on words (68R15)

Cites Work

• The On-Line Encyclopedia of Integer Sequences
• Pattern avoidability with involution
• Unary patterns with involution
• Title not available (Why is that?)
• Uniformly growing k-th power-free homomorphisms
• On a Special Functional Equation
• Sequences with subword complexity \(2n\)
• Title not available (Why is that?)
• Growth properties of power-free languages
• Growth problems for avoidable words
• On the number of Abelian square-free words on four letters

Cited In (11)

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

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)