Avoidability of Formulas with Two Variables

Pascal Ochem 1 Matthieu Rosenfeld 2
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 ∆ 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.
Type de document :
Communication dans un congrès
DLT: Developments in Language Theory, Jul 2016, Montréal, Canada. 20th International Conference on Developments in Language Theory, LNCS (9840), pp.344-354, 2016, Developments in Language Theory. 〈http://dlt2016.lacim.uqam.ca〉. 〈10.1007/978-3-662-53132-7_28〉
Liste complète des métadonnées

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

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01375829
Contributeur : Pascal Ochem <>
Soumis le : lundi 3 octobre 2016 - 15:47:17
Dernière modification le : jeudi 11 janvier 2018 - 06:26:13
Document(s) archivé(s) le : vendredi 3 février 2017 - 14:09:31

Fichier

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

Identifiants

Collections

Citation

Pascal Ochem, Matthieu Rosenfeld. Avoidability of Formulas with Two Variables. DLT: Developments in Language Theory, Jul 2016, Montréal, Canada. 20th International Conference on Developments in Language Theory, LNCS (9840), pp.344-354, 2016, Developments in Language Theory. 〈http://dlt2016.lacim.uqam.ca〉. 〈10.1007/978-3-662-53132-7_28〉. 〈lirmm-01375829〉

Partager

Métriques

Consultations de la notice

22

Téléchargements de fichiers

57