Avoidability of Formulas with Two Variables - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Journal Articles The Electronic Journal of Combinatorics Year : 2017

Avoidability of Formulas with Two Variables

Abstract

In combinatorics on words, a word w over an alphabet Σ is said to avoid a pattern p over an alphabet ∆ of variables 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. We consider the patterns such that at most two variables appear at least twice, or equivalently, the formulas with at most two variables. For each such formula, we determine whether it is 2-avoidable, and if it is 2- avoidable, we determine whether it is avoided by exponentially many binary words.

Keywords

Fichier principal
Vignette du fichier
6536-22614-1-PB.pdf (280.79 Ko) Télécharger le fichier
Loading...

Dates and versions

lirmm-01897592 , version 1 (17-10-2018)

Identifiers

Cite

Pascal Ochem, Matthieu Rosenfeld. Avoidability of Formulas with Two Variables. The Electronic Journal of Combinatorics, 2017, 24 (4), pp.#P4.30. ⟨10.37236/6536⟩. ⟨lirmm-01897592⟩
105 View
114 Download

Altmetric

Share

More