Том 11, серия 1, номер 1, 2004 г., Стр. 52-78
УДК 519.714
В. Н. Потапов
Аддитивная сложность слов с ограничениями на состав подслов
Аннотация:
Аддитивной сложностью слова называется длина кратчайшей схемы конкатенации, порождающей это слово. Для слов длины$n$ , удовлетворяющих различным ограничениям на состав подслов, получены асимптотические (при$n\to\infty$ ) верхние оценки аддитивной сложности. Показано, что эти оценки неулучшаемы для наиболее сложных слов из рассматриваемых множеств.
Потапов В. Н. 1
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
е-mail: vpotapov@math.nsc.ru
Статья поступила 15 августа 2003 г.
