Doubled patterns are 3-avoidable

Pascal Ochem 1
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : In combinatorics on words, a word w over an alphabet Σ is said to avoid a pattern p over an alphabet ∆ if there is no factor f of w such that f = h(p) where h : ∆ * → Σ * 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 said to be doubled if no variable occurs only once. Doubled patterns with at most 3 variables and patterns with at least 6 variables are 3-avoidable. We show that doubled patterns with 4 and 5 variables are also 3-avoidable.
Keywords : Pattern avoidance Word
Type de document :
Article dans une revue
Electronic Journal of Combinatorics, Electronic Journal of Combinatorics, 2016, 23 (1), pp.P1.19. 〈http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i1p19/pdf〉
Liste complète des métadonnées

Littérature citée [13 références]  Voir  Masquer  Télécharger

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01375763
Contributeur : Pascal Ochem <>
Soumis le : lundi 3 octobre 2016 - 14:40:25
Dernière modification le : jeudi 11 janvier 2018 - 06:26:13
Document(s) archivé(s) le : vendredi 3 février 2017 - 13:59:02

Fichier

motif45.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : lirmm-01375763, version 1
  • ARXIV : 1510.01753

Collections

Citation

Pascal Ochem. Doubled patterns are 3-avoidable. Electronic Journal of Combinatorics, Electronic Journal of Combinatorics, 2016, 23 (1), pp.P1.19. 〈http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i1p19/pdf〉. 〈lirmm-01375763〉

Partager

Métriques

Consultations de la notice

32

Téléchargements de fichiers

36