Geodesic
Approximations of words by words without self-duplication
Diskretnaya Matematika, Tome 1 (1989) no. 2, pp. 52-56 
M. Yu. Baryshev. Approximations of words by words without self-duplication. Diskretnaya Matematika, Tome 1 (1989) no. 2, pp. 52-56. http://geodesic.mathdoc.fr/item/DM_1989_1_2_a4/
@article{DM_1989_1_2_a4,
     author = {M. Yu. Baryshev},
     title = {Approximations of words by words without self-duplication},
     journal = {Diskretnaya Matematika},
     pages = {52--56},
     year = {1989},
     volume = {1},
     number = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_1989_1_2_a4/}
}
TY  - JOUR
AU  - M. Yu. Baryshev
TI  - Approximations of words by words without self-duplication
JO  - Diskretnaya Matematika
PY  - 1989
SP  - 52
EP  - 56
VL  - 1
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/DM_1989_1_2_a4/
LA  - ru
ID  - DM_1989_1_2_a4
ER  - 
%0 Journal Article
%A M. Yu. Baryshev
%T Approximations of words by words without self-duplication
%J Diskretnaya Matematika
%D 1989
%P 52-56
%V 1
%N 2
%U http://geodesic.mathdoc.fr/item/DM_1989_1_2_a4/
%G ru
%F DM_1989_1_2_a4

Voir la notice de l'article provenant de la source Math-Net.Ru

We solve a problem of defining, for the word $\alpha $, pairs of the words $x$ and $y$ with a minimal sum of lengths $l(\alpha )$ and such that $x\alpha y$ does not have self-duplication (i.e., natural subwords $\beta \colon x\alpha y=\beta\gamma_1=\gamma_2\beta$). For the function $l(n)=\max l(\alpha )$ (the maximum over all $\alpha $'s of length $n$) we show that $l(n)$ has $\log\log n$ order of growth. We obtain upper and lower bounds for $l(n)$.