A short proof that shuffle squares are 7-avoidable - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue RAIRO - Theoretical Informatics and Applications (RAIRO: ITA) Année : 2016

A short proof that shuffle squares are 7-avoidable

Guillaume Guégan
  • Fonction : Auteur
  • PersonId : 1165626
Pascal Ochem

Résumé

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
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

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

Identifiants

Citer

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⟩
216 Consultations
24 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More