|
Approximations of words by words without self-duplication
M. Yu. Baryshev
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)$.
Received: 29.09.1988
Citation:
M. Yu. Baryshev, “Approximations of words by words without self-duplication”, Diskr. Mat., 1:2 (1989), 52–56
Linking options:
https://www.mathnet.ru/eng/dm908 https://www.mathnet.ru/eng/dm/v1/i2/p52
|
Statistics & downloads: |
Abstract page: | 308 | Full-text PDF : | 142 | First page: | 1 |
|