Doubled patterns with reversal and square-free doubled patterns - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Preprints, Working Papers, ... Year : 2023

Doubled patterns with reversal and square-free doubled patterns

Antoine Domenech
  • Function : Author
  • PersonId : 1294594
Pascal Ochem


In combinatorics on words, a word $w$ over an alphabet $\Sigma$ is said to avoid a pattern $p$ over an alphabet $\Delta$ if there is no factor $f$ of $w$ such that $f=h(p)$ where $h:\Delta^*\to\Sigma^*$ is a non-erasing morphism. A pattern $p$ is said to be $k$-avoidable if there exists an infinite word over a $k$-letter alphabet that avoids $p$. A pattern is \emph{doubled} if every variable occurs at least twice. Doubled patterns are known to be $3$-avoidable. Currie, Mol, and Rampersad have considered a generalized notion which allows variable occurrences to be reversed. That is, $h(V^R)$ is the mirror image of $h(V)$ for every $V\in\Delta$. We show that doubled patterns with reversal are $3$-avoidable. We also conjecture that (classical) doubled patterns that do not contain a square are $2$-avoidable. We confirm this conjecture for patterns with at most 4 variables. This implies that for every doubled pattern $p$, the growth rate of ternary words avoiding $p$ is at least the growth rate of ternary square-free words. A previous version of this paper containing only the first result has been presented at WORDS 2021.
Fichier principal
Vignette du fichier
2105.04673.pdf (139.63 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Licence : CC BY - Attribution

Dates and versions

lirmm-03799694 , version 1 (17-10-2023)





Antoine Domenech, Pascal Ochem. Doubled patterns with reversal and square-free doubled patterns. 2023. ⟨lirmm-03799694⟩
16 View
4 Download



Gmail Facebook X LinkedIn More