Аннотация:
Исследуется задача о сложности сборки слов. Под сложностью слова понимается минимальное число операций конкатенации (склейки), достаточное для получения слова из однобуквенных слов над конечным алфавитом $A$ (допускается многократное использование полученных слов). Пусть $L_A^c(n)$ — максимальная сложность слова длины $n$ над конечным алфавитом $A$. В работе установлено, что $ L_A^c(n) = \frac n {\log_{|A|} n} \left( 1 + (2+o(1)) \frac {\log_2 \log_2 n}{\log_2 n} \right). $
Ключевые слова:схемы конкатенации, цепочки слов, схемная сложность, функция Шеннона.