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
Key words: concatenation circuits, word chains, circuits complexity, Shannon function.