Geodesic
A short proof that shuffle squares are 7-avoidable
Guégan, Guillaume1 ; Ochem, Pascal2 
1 University Montpellier 2, LIRMM, France
2 CNRS, LIRMM, Montpellier, France
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Special issue dedicated to the 15th "Journées Montoises d'Informatique Théorique", Tome 50 (2016) no. 1, pp. 101-103 Cet article a éte moissonné depuis la source Numdam

Voir la notice de l'article

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. arXiv:1406.4380].

Reçu le :
Accepté le :
DOI : 10.1051/ita/2016007
Classification : 68R15
Keywords: Combinatorics on words, shuffle square, entropy compression

Guégan, Guillaume 1 ; Ochem, Pascal 2

1 University Montpellier 2, LIRMM, France
2 CNRS, LIRMM, Montpellier, France 
@article{ITA_2016__50_1_101_0,
     author = {Gu\'egan, Guillaume and Ochem, Pascal},
     title = {A short proof that shuffle squares are 7-avoidable},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {101--103},
     year = {2016},
     publisher = {EDP-Sciences},
     volume = {50},
     number = {1},
     doi = {10.1051/ita/2016007},
     zbl = {1353.68224},
     mrnumber = {3518162},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1051/ita/2016007/}
}
TY  - JOUR
AU  - Guégan, Guillaume
AU  - Ochem, Pascal
TI  - A short proof that shuffle squares are 7-avoidable
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2016
SP  - 101
EP  - 103
VL  - 50
IS  - 1
PB  - EDP-Sciences
UR  - http://geodesic.mathdoc.fr/articles/10.1051/ita/2016007/
DO  - 10.1051/ita/2016007
LA  - en
ID  - ITA_2016__50_1_101_0
ER  - 
%0 Journal Article
%A Guégan, Guillaume
%A Ochem, Pascal
%T A short proof that shuffle squares are 7-avoidable
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2016
%P 101-103
%V 50
%N 1
%I EDP-Sciences
%U http://geodesic.mathdoc.fr/articles/10.1051/ita/2016007/
%R 10.1051/ita/2016007
%G en
%F ITA_2016__50_1_101_0
Guégan, Guillaume; Ochem, Pascal. A short proof that shuffle squares are 7-avoidable. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Special issue dedicated to the 15th "Journées Montoises d'Informatique Théorique", Tome 50 (2016) no. 1, pp. 101-103. doi: 10.1051/ita/2016007

Cité par Sources :