Revision of asymptotic behavior of the complexity of word assembly by concatenation circuits
Vestnik Moskovskogo universiteta. Matematika, mehanika, no. 2 (2016), pp. 12-18
Voir la notice de l'article provenant de la source Math-Net.Ru
The problem of complexity of word assembly is studied. The complexity of a word means the minimal number of concatenation operations sufficient to obtain this word in the basis of one-letter words over a finite alphabet $A$ (repeated use of obtained words is permitted). Let $L_A^c(n)$ be the maximum complexity of words of length $n$ over a finite alphabet $A$. In this paper we prove that $ L_A^c(n) = \frac n {\log_{|A|} n} \left( 1 + (2+o(1)) \frac {\log_2 \log_2 n}{\log_2 n} \right). $
@article{VMUMM_2016_2_a1,
author = {V. V. Kochergin and D. V. Kochergin},
title = {Revision of asymptotic behavior of the complexity of word assembly by concatenation circuits},
journal = {Vestnik Moskovskogo universiteta. Matematika, mehanika},
pages = {12--18},
publisher = {mathdoc},
number = {2},
year = {2016},
language = {ru},
url = {http://geodesic.mathdoc.fr/item/VMUMM_2016_2_a1/}
}
TY - JOUR AU - V. V. Kochergin AU - D. V. Kochergin TI - Revision of asymptotic behavior of the complexity of word assembly by concatenation circuits JO - Vestnik Moskovskogo universiteta. Matematika, mehanika PY - 2016 SP - 12 EP - 18 IS - 2 PB - mathdoc UR - http://geodesic.mathdoc.fr/item/VMUMM_2016_2_a1/ LA - ru ID - VMUMM_2016_2_a1 ER -
%0 Journal Article %A V. V. Kochergin %A D. V. Kochergin %T Revision of asymptotic behavior of the complexity of word assembly by concatenation circuits %J Vestnik Moskovskogo universiteta. Matematika, mehanika %D 2016 %P 12-18 %N 2 %I mathdoc %U http://geodesic.mathdoc.fr/item/VMUMM_2016_2_a1/ %G ru %F VMUMM_2016_2_a1
V. V. Kochergin; D. V. Kochergin. Revision of asymptotic behavior of the complexity of word assembly by concatenation circuits. Vestnik Moskovskogo universiteta. Matematika, mehanika, no. 2 (2016), pp. 12-18. http://geodesic.mathdoc.fr/item/VMUMM_2016_2_a1/