Avoidance bases for formulas with reversal

DOI10.1016/J.TCS.2018.04.039MaRDI QIDQ1643149zbMATH OpenOpenAlexWikidataFDO

Authors James D. Currie, Narad Rampersad, L. A. S. Mól

Publication date 18 June 2018

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

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

zbMATH Keywords

avoidability indexavoidance basisformulas with reversalpattern avoidance

Mathematics Subject Classification ID

Combinatorics on words (68R15)

Abstract: In the interest of studying formulas with reversal of high avoidability index, we find $n$-avoidance bases for formulas with reversal for $nin1,2,3$. We demonstrate that there is a unique formula with reversal in each of these three bases of highest avoidability index $n+2$; these formulas are $xx$, $xyxcdot{y}^R$, and $xyzxcdot{y}^{R}cdot{z}^R$, which belong to an infinite family of formulas with reversal that has been the subject of recent study by the authors.

Recommendations

• A family of formulas with reversal of arbitrarily high avoidability index
• A family of formulas with reversal of high avoidability index
• On avoidability of formulas with reversal
• Formulas with reversal
• Avoidability of circular formulas

Cites work

• A family of formulas with reversal of high avoidability index
• Avoidability index for binary patterns with reversal
• Avoidability of circular formulas
• Binary words avoiding xx^Rx and strongly unimodal sequences
• BLOCKING SETS OF TERMS
• Growth problems for avoidable words
• Growth rate of binary words avoiding \(xxx^{R}\)
• scientific article; zbMATH DE number 1024080 (Why is no real title available?)
• On avoidability of formulas with reversal
• Proof of Dejean's conjecture for alphabets with \(5, 6, 7, 8, 9, 10\) and \(11\) letters

Cited in

(7)

• Formulas with reversal
• Doubled patterns with reversal are 3-avoidable
• The undirected repetition threshold and undirected pattern avoidance
• A family of formulas with reversal of arbitrarily high avoidability index
• Doubled patterns with reversal and square-free doubled patterns
• On avoidability of formulas with reversal
• A family of formulas with reversal of high avoidability index

This page was built for publication: Avoidance bases for formulas with reversal

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