|
Вестник Московского университета. Серия 1: Математика. Механика, 2016, номер 2, страницы 12–18
(Mi vmumm130)
|
|
|
|
Эта публикация цитируется в 1 научной статье (всего в 1 статье)
Математика
Уточнение асимптотического поведения сложности сборки слов схемами конкатенации
В. В. Кочергинab, Д. В. Кочергинa a Московский государственный университет имени М. В. Ломоносова, механико-математический факультет
b Московский государственный университет имени М. В. Ломоносова, ИТПМ
Аннотация:
Исследуется задача о сложности сборки слов. Под сложностью слова понимается минимальное число операций конкатенации (склейки), достаточное для получения слова из однобуквенных слов над конечным алфавитом $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). $
Ключевые слова:
схемы конкатенации, цепочки слов, схемная сложность, функция Шеннона.
Поступила в редакцию: 29.05.2015
Образец цитирования:
В. В. Кочергин, Д. В. Кочергин, “Уточнение асимптотического поведения сложности сборки слов схемами конкатенации”, Вестн. Моск. ун-та. Сер. 1. Матем., мех., 2016, № 2, 12–18; Moscow University Mathematics Bulletin, 71:2 (2016), 55–60
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/vmumm130 https://www.mathnet.ru/rus/vmumm/y2016/i2/p12
|
|