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