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

• Автор: Фрид, Анна Эдуардовна
• Шифр специальности: 01.01.09
• Научная степень: Докторская
• Год защиты: 2012
• Место защиты: Новосибирск
• Количество страниц: 245 с. : ил.

Оглавление
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.10 Факторные языки и операции над ними
1.11 Специальные слова и сложность
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.6 Обсуждение
2.6 Арифметическая сложность обобщенных слов Теплица: схемы разных длин
2.6.1 Конструкция языка <7)
2.6.2 Рекуррентная формула для первых разностей
2.6.3 Рост функции в(п)
2.6.4 Тауберова теорема
2.6.5 Завершение доказательства
2.7 Арифметическая сложность слов Штурма: верхняя оценка и точные формулы
2.7.1 Арифметические подпоследовательности слов Штурма .
2.7.2 Геометрический двойственный метод
2.7.3 Количество граней
2.7.4 Симметрия
2.7.5 Наследование граней
2.7.6 Вычислительный эксперимент
2.7.7 Интервалы Фарея и изоморфизм
2.7.8 Точные формулы
2.7.9 Обсуждение
2.8 Нижняя оценка на арифметическую сложность слов Штурма .
2.8.1 Нижняя оценка

В разделе 3.5 аналогично словам Штурма будут введены перестановку. Штурма и доказаны некоторые их свойства.
1.4 Вращательные слова
Рассмотрим единичную окружность С, то есть интервал (0,1), концы которого отождествляются, и определим на нем сложение (а следовательно, и умножение на целое число) как в фактор-группе Ш/Ъ. Другими словами, при работе с этой группой мы рассматриваем действительные числа по модулю 1 и вместо дробной части {х} можем употреблять обозначение х (тос! 1) или просто х.
Интервал 3 = [х,у) на окружности С определяется как обычно, если 0 < х < у < 1, и как дополнение С[г/, х), если 0 < у < х < 1. Интервалы с другим сочетанием скобок определяются аналогично.
Рассмотрим теперь разбиение Р окружности С на конечное число непересекающихся интервалов с/о, Д, ■ • •, Л, = С. Мы предполагаем, что все интервалы JJ одновремен-
но либо полуоткрыты, либо полузамкнуты.
Для двух разбиений Р^Рэ, состоящих из интервалов одного типа, определим их комбинацию Р[ УРг как разбиение, интервалы в котором являются непустыми пересечениями интервалов из Р1 и Р2.
Свяжем с каждым интервалом с/3 символ а3 из конечного алфавита А: символы для разных интервалов могут совпадать. Обозначим через 1а объединение интервалов, соответствующих символу а. Разбиение {/„;а € А} окружности С называется фактор-разбиением разбиения {70, J,• ■ ■, Jk}■
Вращением называется отображение Щ : С -> С, переводящее точку х в точку {ж + £}.
Рассмотрим последовательность (т,)20, ж, € С, задаваемую равенствами ж1+1 = Л^х, для некоторого £, и определим бесконечное слово V = Но ■■■ ип ■■ ■ над алфавитом А равенствами V, = а -£=> х, € /„. Это слово V над алфавитом А называется вращательным словом с. наклоном £ и начальной точкой жо, порожденным разбиением {/а; а € А}, и обозначается Щхо, £, {/а; а € А}).