Doubled patterns with reversal and square-free doubled patterns - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Pré-Publication, Document De Travail Année : 2023

Doubled patterns with reversal and square-free doubled patterns

Antoine Domenech
  • Fonction : Auteur
  • PersonId : 1294594
Pascal Ochem

Résumé

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
Origine : Fichiers produits par l'(les) auteur(s)
Licence : CC BY - Paternité

Dates et versions

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

Licence

Paternité

Identifiants

Citer

Antoine Domenech, Pascal Ochem. Doubled patterns with reversal and square-free doubled patterns. 2023. ⟨lirmm-03799694⟩
23 Consultations
4 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More