Уточнение асимптотического поведения сложности сборки слов схемами конкатенациистатья
Статья опубликована в журнале из списка RSCI Web of Science
Статья опубликована в журнале из перечня ВАК
Статья опубликована в журнале из списка Web of Science и/или Scopus
Дата последнего поиска статьи во внешних источниках: 26 августа 2016 г.
Аннотация:Исследуется задача о сложности сборки слов.
Под сложностью слова понимается минимальное число операций
конкатенации (склейки), достаточное для получения слова из однобуквенных
слов над конечным алфавитом $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).$