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.
Type de document :
Article dans une revue
RAIRO - Theoretical Informatics and Applications (RAIRO: ITA), EDP Sciences, 2016, 50 (1), pp.101-103. 〈10.1051/ita/2016007〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01347424
Contributeur : Isabelle Gouat <>
Soumis le : jeudi 21 juillet 2016 - 06:55:49
Dernière modification le : jeudi 11 janvier 2018 - 06:26:13

Lien texte intégral

Identifiants

Collections

Citation

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〉

Partager

Métriques

Consultations de la notice

83