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.

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
Mots-clés : 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},
     publisher = {EDP-Sciences},
     volume = {50},
     number = {1},
     year = {2016},
     doi = {10.1051/ita/2016007},
     zbl = {1353.68224},
     mrnumber = {3518162},
     language = {en},
     url = {http://archive.numdam.org/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://archive.numdam.org/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://archive.numdam.org/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. http://archive.numdam.org/articles/10.1051/ita/2016007/

J. Bell and T.L. Goh, Exponential lower bounds for the number of words of uniform length avoiding a pattern. Inform. Comput. 205 (2007) 1295–1306. | DOI | MR | Zbl

F. Blanchet-Sadri and B. Woodhouse, Strict bounds for pattern avoidance. Theor. Comput. Sci. 506 (2013) 17–27. | DOI | MR | Zbl

J. Currie, Shuffle squares are avoidable. Manuscript.

D. Gonçalves, M. Montassier and A. Pinlou, Entropy compression method applied to graph colorings. Preprint (2015). | arXiv

J. Grytczuk, J. Kozik and P. Micek, A new approach to nonrepetitive sequences. Random Structures & Algorithms 42 (2013) 214–225. | DOI | MR | Zbl

J. Grytczuk, J. Kozik and B. Zaleski, Avoiding tight twins in sequences by entropy compression. Available at http://ssdnm.mimuw.edu.pl/pliki/prace-studentow/st/pliki/bartosz-zaleski-3.pdf

M. Müller, Avoiding and enforcing repetitive structures in words. Ph.D. thesis (2014).

P. Ochem, Doubled patterns are 3-avoidable. Preprint (2015). | arXiv | MR

P. Ochem and A. Pinlou, Application of entropy compression in pattern avoidance. Electron. J. Combin. 21 (2014) #RP2.7. | DOI | MR | Zbl

N. Rampersad, Further applications of a power series method for pattern avoidance. Electron. J. Combin. 18 (2011) #P134. | DOI | MR | Zbl

Cité par Sources :