Pattern Avoidance and HDOL Words

Pascal Ochem 1
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : In this talk, we consider the possibility that for every avoidable pattern P , there exists a finite set S of forbidden patterns and factors, containg P , such that the words over Σ_λ(P ) are essentially the factors of an HDOL word. This is a strong version of Cassaigne's conjecture. I will give many examples of such HDOL words characterized by forbidden patterns and factors, as well as related open problems. We will also discuss the factor complexity of words avoiding patterns.
Type de document :
Communication dans un congrès
WORDS'11: 8th International Conference on Combinatorics on Words, Czech Republic. 2011, 〈http://words2011.fjfi.cvut.cz/〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00626116
Contributeur : Pascal Ochem <>
Soumis le : vendredi 23 septembre 2011 - 15:03:55
Dernière modification le : jeudi 24 mai 2018 - 15:59:22

Identifiants

  • HAL Id : lirmm-00626116, version 1

Collections

Citation

Pascal Ochem. Pattern Avoidance and HDOL Words. WORDS'11: 8th International Conference on Combinatorics on Words, Czech Republic. 2011, 〈http://words2011.fjfi.cvut.cz/〉. 〈lirmm-00626116〉

Partager

Métriques

Consultations de la notice

127