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.
Document type :
Conference papers
Complete list of metadatas

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00626116
Contributor : Pascal Ochem <>
Submitted on : Friday, September 23, 2011 - 3:03:55 PM
Last modification on : Thursday, May 24, 2018 - 3:59:22 PM

Identifiers

  • 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. ⟨lirmm-00626116⟩

Share

Metrics

Record views

166