Doubled patterns are 3-avoidable - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Article Dans Une Revue The Electronic Journal of Combinatorics Année : 2016

Doubled patterns are 3-avoidable

Pascal Ochem

Résumé

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.

Mots clés

Fichier principal
Vignette du fichier
motif45.pdf (245.16 Ko) Télécharger le fichier
Origine Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

lirmm-01375763 , version 1 (03-10-2016)

Identifiants

Citer

Pascal Ochem. Doubled patterns are 3-avoidable. The Electronic Journal of Combinatorics, 2016, 23 (1), pp.P1.19. ⟨10.37236/5618⟩. ⟨lirmm-01375763⟩
107 Consultations
127 Téléchargements

Altmetric

Partager

More