Avoidability of Formulas with Two Variables - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Communication Dans Un Congrès Année : 2016

Avoidability of Formulas with Two Variables

Résumé

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.
Fichier principal
Vignette du fichier
main.pdf (285.91 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

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

Identifiants

Citer

Pascal Ochem, Matthieu Rosenfeld. Avoidability of Formulas with Two Variables. 20th International Conference on Developments in Language Theory (DLT 2016), Laboratoire de combinatoire et d'informatique mathématique (LaCIM), Université du Québec à Montréal, Jul 2016, Montréal, Canada. pp.344-354, ⟨10.1007/978-3-662-53132-7_28⟩. ⟨lirmm-01375829⟩
95 Consultations
182 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More