A short proof that shuffle squares are 7-avoidable - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Journal Articles RAIRO - Theoretical Informatics and Applications (RAIRO: ITA) Year : 2016

A short proof that shuffle squares are 7-avoidable

Guillaume Guégan
  • Function : Author
  • PersonId : 1165626
Pascal Ochem

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.
Fichier principal
Vignette du fichier
GueganOchemShuffle.pdf (318.15 Ko) Télécharger le fichier
Origin Files produced by the author(s)

Dates and versions

lirmm-01347424 , version 1 (19-09-2022)

Identifiers

Cite

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

Altmetric

Share

More