Введение 3
Предварительные сведения 4
Обзор исследований по теме диссертации 9
Обзор диссертации 17
1 Предмаксимальные слова 24
1.1 Общая схема построения предмаксимальных слов 24
1.2 Бинарный бескубный язык 27
1.2.1 Построение буферных слов 28
1.2.2 Доказательство корректности конструкции 31
1.2.3 Построение двусторонних предмаксимальных слов ... 38
1.3 Тернарный бесквадратный язык 39
1.3.1 Коды Пансьё и маршрутные коды 39
1.3.2 Обзор основной конструкции для предмаксимальных слов 42
1.3.3 Маршрутный код слова Аршона 44
1.3.4 Свойства слов р'п 46
1.3.5 Построение буферных слов и доказательство бесквад-
ратности 48
1.3.6 Построение предмаксимальных слов 53
2 Избегаемость буквенных шаблонов в бесквадратных словах 57
2.1 Построение бесквадратных кодов из слов Фибоначчи 58
2.2 Экспоненты слов, избегающих 5- и 6-буквенные шаблоны ... 61
2.3 Дальнейшие перспективы исследования буквенных шаблонов . 65
3 Структура префиксного дерева тернарного бесквадратного языка 66
3.1 Логарифмическая оценка длины фиксированного контекста . . 67
3.1.1 Короткие квадраты 67
3.1.2 Длинные квадраты 71
3.2 Частота ветвления префиксного дерева языка ЗБ 77
3.3 О возможном усилении Теоремы 14 78
Заключение 80
Список литературы 82
Комбинаторика слов, относительно молодая и активно развивающаяся дисциплина, возникшая на рубеже XIX и XX веков, представляет собой важное
направление на стыке современной дискретной математики и теоретических
компьютерных наук, изучающее свойства символьных последовательностей
(слов). Методы и результаты, разработанные и полученные в комбинаторике слов, широко применимы во многих областях, например, в теории групп,
теории кодирования, теории игр, биоинформатике, сжатии данных.
Одним из основных объектов исследований в комбинаторике слов являются бесповторные языки — множества слов, не содержащих внутри себя повторяющихся фрагментов, или, как говорят, избегающих определённые
структурные элементы. Норвежский математик Аксель Туэ в начале XX века занимался конструированием и изучением нескольких конкретных бесповторных языков, и принято считать, что именно с этих работ комбинаторика
слов берёт своё начало как самостоятельная дисциплина. Туэ рассматривал,
например, бескубный язык над двухбуквенным (бинарным) алфавитом и бесквадратный язык над трёхбуквенным (тернарным) алфавитом — эти языки
состоят из слов, не содержащих трёх и двух идущих подряд одинаковых
фрагментов, соответственно, — и получил ряд нетривиальных результатов,
касающихся, в первую очередь, вопроса о конечности или бесконечности того
или иного языка. Со времён Туэ тема бесповторных языков получила весьма
широкое развитие во многих направлениях: было обобщено понятие степени,
изучены алфавиты большей мощности, обобщено понятие избегаемости с простых повторов до шаблонов, абелевых степеней и т.д., получены результаты о
комбинаторной сложности бесповторных языков, рассмотрены бесповторные
слова с дополнительными ограничениями. Тем не менее, в отношении языков, рассмотренных Туэ, до сих пор остаётся множество открытых проблем.
Некоторые из них решены в данной диссертации.
Любой бесповторный язык является факториальным, то есть замкнутым
относительно операции взятия подслова. На множестве слов факториального
языка можно ввести три естественных отношения: «быть префиксом», «быть
суффиксом», «быть подсловом», относительно которых это множество частич-
3ВВЕДЕНИЕ 4
но упорядочено, и диаграммы этих частично упорядоченных множеств (ч.у.м.)
в первых двух случаях представляют собой деревья, в третьем — ациклический граф более общего вида. Изучение структуры таких ч.у.м. оказывается
очень интересной темой в исследовании бесповторных языков, проливающей
свет на их внутреннее устройство. Среди задач в этом направлении можно
назвать вопросы об изоморфизме поддеревьев, порождённых двумя данными словами в дереве префиксного (суффиксного) порядка, о существовании
поддеревьев или подграфов произвольной конечной высоты, о частоте и регулярности ветвления деревьев префиксного (суффиксного) порядка и другие.
Основная часть диссертации посвящена проблемам, связанным со структурой
ч.у.м. слов бинарного бескубного языка и тернарного бесквадратного языка.
Кратко подведём итоги работы по каждой из глав диссертации.
Предмаксимальные слова
Доказано существование конечных поддеревьев произвольной высоты в суффиксном (префиксном) дереве, а также конечных подграфов c цепями из суффиксных и префиксных ребёр произвольной длины в ациклическом подсловном графе языков бинарных бескубных слов CF и тернарных бесквадратных
слов SF.
