Том 11, серия 1, номер 3, 2004 г., Стр. 48-58

УДК 519.11
В. Н. Потапов
О максимальной длине двоичных слов с ограниченной частотой единиц и без одинаковых подслов заданной длины

Аннотация:
Построены двоичные слова с частотой единиц не более $\beta$ $(0\leqslant\beta\leqslant1)$ и без одинаковых подслов длины $n$, длина которых менее чем на $n$ отличается от максимально возможной. Найдена асимптотика длины таких слов при $n\to\infty$. Показано, что подслова таких слов имеют асимптотически максимальную аддитивную сложность среди всех слов той же длины с частотой единиц не более $\beta$.

Потапов В. Н. ¹
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
е-mail: vpotapov@math.nsc.ru

Статья поступила 24 мая 2004 г.