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
Document type :
Journal articles
Complete list of metadatas

Cited literature [13 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01375763
Contributor : Pascal Ochem <>
Submitted on : Monday, October 3, 2016 - 2:40:25 PM
Last modification on : Monday, August 5, 2019 - 3:26:03 PM
Long-term archiving on : Friday, February 3, 2017 - 1:59:02 PM

File

motif45.pdf
Files produced by the author(s)

Identifiers

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

Collections

Citation

Pascal Ochem. Doubled patterns are 3-avoidable. The Electronic Journal of Combinatorics, Open Journal Systems, 2016, 23 (1), pp.P1.19. ⟨lirmm-01375763⟩

Share

Metrics

Record views

137

Files downloads

66