Avoidability of Palindrome Patterns

1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : We characterize the formulas that are avoided by every $\alpha$-free word for some $\alpha>1$. We show that the avoidable formulas whose fragments are of the form $XY$ or $XYX$ are $4$-avoidable. The largest avoidability index of an avoidable palindrome pattern is known to be at least $4$ and at most $16$. We make progress toward the conjecture that every avoidable palindrome pattern is $4$-avoidable.
Document type :
Journal articles

https://hal-lirmm.ccsd.cnrs.fr/lirmm-03371500
Contributor : Pascal Ochem Connect in order to contact the contributor
Submitted on : Friday, October 8, 2021 - 4:43:15 PM
Last modification on : Wednesday, October 13, 2021 - 3:35:38 AM

Citation

Pascal Ochem, Matthieu Rosenfeld. Avoidability of Palindrome Patterns. The Electronic Journal of Combinatorics, Open Journal Systems, 2021, 28 (1), pp.#1.4. ⟨10.37236/9593⟩. ⟨lirmm-03371500⟩

Record views