УДК 519.7

Уточнение асимптотического поведения сложности сборки слов схемами конкатенации / В. В. Кочергин, Д. В. Кочергин. // Вестн. Моск. ун-та. Сер. 1, Математика. Механика. 2016. № 2. С. 13-18.

Исследуется задача о сложности сборки слов. Под сложностью слова понимается минимальное число операций конкатенации (склейки), достаточное для получения слова из однобуквенных слов над конечным алфавитом 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) .

Ключевые слова: схемы конкатенации, цепочки слов, схемная сложность, функция Шеннона.

Библиогр. 14.