Revision of Asymptotic Behavior of the Complexity of Word Assembly by Concatenation Circuits / V. V. Kochergin and D. V. Kochergin. // Vestnik Moskovskogo Universiteta. Seriya 1. Matematika. Mekhanika. 2016. № 2. P. 13-18 [Moscow Univ. Math. Bulletin. Vol. 72, N 2, 2017. P. 55-60].

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

Key words: concatenation circuits, word chains, circuits complexity, Shannon function.

№ 2/2016