Комбинаторные сложностные характеристики бесконечных слов, языков и перестановок

Оглавление
0.1 Актуальность темы.
0.2 Обзор.
0.2.1 Теория избегаемости.
0.2.2 Понятия сложности бесконечных слов и языков.
0.2.3 Бесконечные перестановки .
0.2.4 Моноид формальных языков
0.3 Цели и результаты работы .
0.4 Апробация и публикации
0.5 Содержание работы
1 Основные понятия
1.1 Вводные определения и обозначения.
1.2 Периодические слова.
1.3 Слова Штурма
1.4 Вращательные слова
1.5 Морфизмы и их неподвижные точки.
1.6 Автоматные слова
1.7 Схемы Теплица.
1.8 Равномерно рекуррентные слова.
1.9 Максимальная шаблонная сложность.
1. Факторные языки и операции над ними.
1. Специальные слона и сложность.
2 Арифметическая сложность бесконечных слов
2.1 Определение, обсуждение и примеры .
2.2 Сложность неподвижных точек симметрических и квазисимметрических морфизмов
2.3 Низкая арифметическая сложность равномерно рекуррентных слов.
2.3.1 Бесконечные специальные ветви.
2.3.2 Случай двух ветвей .
2.3.3 Наименьшая арифметическая сложность.
2.4 Линейная арифметическая сложность равномерно рекуррентных слов.
2.4.1 Канонически ррегулярные и ррегулярные слова.
2.4.2 Случай конечного числа бесконечных специальных ветвей
2.4.3 Основная лемма .
2.4.4 Завершение доказательства.
2.5 Арифметическая сложность обобщенных слов Теплица схемы фиксированной длины
2.5.1 Конструкция.
2.5.2 Арифметическое замыкание слова Ьри
2.5.3 Биспециальные слова языка А.
2.5.4 Степени биспециальности и диаграмма первых разностей
2.5.5 Оценки на арифметическую сложность
2.5.0 Обсуждение
2.0 Арифметическая сложность обобщенных слов Теплица схемы
ратных длин
2.0.1 Конструкция языка 3, й
2.0.2 Рекуррентная формула для первых разностей
2.0.3 Рост функции зп.
2.0.4 Тауберова теорема.
2.0.5 Завершение доказательства.
2.7 Арифметическая сложность слов Штурма верхняя оценка и точные формулы
2.7.1 Арифметические подпоследовательности слов Штурма .
2.7.2 Геометрический двойственный метод.
2.7.3 Количество граней.
2.7.4 Симметрия.
2.7.5 Наследование граней.
2.7.0 Вычислительный эксперимент
2.7.7 Интервалы Фарея и изоморфизм
2.7.8 Точные формулы
2.7.9 Обсуждение
2.8 Нижняя оценка на арифметическую сложность слов Штурма .
2.8.1 Нижняя оценка.
2.8.2 Нижняя оценка для вращательных слов
3 Периодичность и сложность бесконечных перестановок
3.1 Бесконечные перестановки и бесконечные слова.
3.2 Периодические бесконечные перестановки.
3.3 Периоды конечных перестановок
3.4 Факторы и факторная сложность .
3.5 Максимальная шаблонная сложность перестановок .
3.5.1 Определение и неравенство р п п
3.5.2 Перестановки Штурма и теорема о максимальной шаблонной сложности
3.5.3 Максимальная шаблонная сложность перестановок Штурма .
3.5.4 Схема доказательства в обратную сторону .
3.5.5 Случай последовательности Штурма.
3.5.6 Случай периодической последовательности
3.6 Автоматные перестановки
4 Моноид факторных языков
4.1 Канонические разложения
4.1.1 Подалфавиты и выжимки
4.1.2 Доказательство существования.
4.1.3 Доказательство единственности
4.2 Вид канонического разложения катенации
4.3 Свойства факторных языков.
4.4 Уравнения над факторными языками
4.4.1 Простые уравнения над словами
4.4.2 Унарные факторные языки
4.4.3 Уравнение Хп Уп
4.4.4 Коммутирование.
4.4.5 Сопряжение.
4.5 Канонические разложения регулярных факторных языков . . .
Литература