• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Article

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

Moscow University Mathematics Bulletin. 2016. Vol. 71. No. 2. P. 55-60.
Kochergin V. V., Kochergin D. V.

The problem of the complexity of word assembly is studied. The complexity of the word refers to the minimum number of concatenation operations sufficient to obtain this word on the basis of one-letter words over a finite alphabet $A$ (repeated use of the received words is permitted). Let $L_A^c(n)$ be maximum complexity of words of length~$n$ over a finite alphabet $A$. In this paper, we establish 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). $