This article is cited in 1 paper

Mathematics

Revision of asymptotic behavior of the complexity of word assembly by concatenation circuits

V. V. Kochergin^ab, D. V. Kochergin<sup>a

a</sup> Lomonosov Moscow State University, Faculty of Mechanics and Mathematics
^b Lomonosov Moscow State University, Bogoliubov Institute for Theoretical Problems of Microphysics

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

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

UDC: 519.7

Received: 29.05.2015

 English version: Moscow University Mathematics Bulletin, Moscow University Mеchanics Bulletin, 2016, 71:2, 55–60

Bibliographic databases:

• 
• 
• 
•