A short proof that shuffle squares are 7-avoidable

Guillaume Guégan 1 Pascal Ochem 2
2 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : A shuffle square is a word that can be partitioned into two identical words. We obtain a short proof that there exist exponentially many words over the 7 letter alphabet containing no shuffle square as a factor. The method is a generalization of the so-called power series method using ideas of the entropy compression method as developped by Gonçalves et al. [Entropy compression method applied to graph colorings.
Document type :
Journal articles
Complete list of metadatas

Contributor : Isabelle Gouat <>
Submitted on : Thursday, July 21, 2016 - 6:55:49 AM
Last modification on : Thursday, May 24, 2018 - 3:59:22 PM

Links full text




Guillaume Guégan, Pascal Ochem. A short proof that shuffle squares are 7-avoidable. RAIRO - Theoretical Informatics and Applications (RAIRO: ITA), EDP Sciences, 2016, 50 (1), pp.101-103. ⟨10.1051/ita/2016007⟩. ⟨lirmm-01347424⟩



Record views