Approximations of words by words without self-duplication

M. Yu. Baryshev

Diskretnaya Matematika, Tome 1 (1989) no. 2, pp. 52-56.

Résumé

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)$.