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

Cited literature [10 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01375829
Contributor : Pascal Ochem <>
Submitted on : Monday, October 3, 2016 - 3:47:17 PM
Last modification on : Thursday, May 24, 2018 - 3:59:22 PM
Long-term archiving on : Friday, February 3, 2017 - 2:09:31 PM

File

main.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Pascal Ochem, Matthieu Rosenfeld. Avoidability of Formulas with Two Variables. DLT: Developments in Language Theory, 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⟩

Share

Metrics

Record views

138

Files downloads

283