Skip to Main content Skip to Navigation
Conference papers

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 metadata
Contributor : Pascal Ochem <>
Submitted on : Friday, September 23, 2011 - 3:03:55 PM
Last modification on : Wednesday, November 4, 2020 - 6:08:04 PM


  • HAL Id : lirmm-00626116, version 1



Pascal Ochem. Pattern Avoidance and HDOL Words. WORDS'11: 8th International Conference on Combinatorics on Words, Czech Republic. ⟨lirmm-00626116⟩



Record views