• A
• A
• A
• ABC
• ABC
• ABC
• А
• А
• А
• А
• А
Regular version of the site
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).$