Оглавление
Введение
1 Предварительные сведении
1.1 Слова
1.2 Языки и автоматы
1.3 Комбинаторная сложность
2 Обзор исследований в предметной области .
2.1 Другие виды сложности.
2.2 Сложность бесконечных слов
2.3 Общие результаты о комбинаторной сложности .
2.4 Языки, избегающие степени.
2.5 Языки, избегающие шаблоны и абелевы степени.
3 Обзор диссертации .
3.1 Цели работы.
3.2 Основные проблемы
3.3 Основные результаты
3.4 Основные методы.
3.5 Структура диссертации и организация текста .
3.6 Апробация и публикации .
Глава 1. Сложность регулярных языков
1 Инструментарий.
1.1 Оценки сложности.
1.2 Орграфы и линейная алгебра.
2 Основные характеристики роста
2.1 Проверка полиномиальности.
2.2 Вычисление индекса рост
3 Детали асимптотического поведения
3.1 Оценка числа арифметических прогрессий.
3.2 Вычисление полиномиального индекса.
3.3 Вычисление асимптотического представления .
ОГЛАВЛЕНИЕ
4 Колебания комбинаторной сложности.
Глава 2. Сложность факториальных языков. КАСязыки
5 Основные конструкции
5.1 Регулярные приближения факториальных языков.
5.2 КАСавтоматы
6 Регулярные приближения языка ТуэМорса
6.1 Антисловарь языка ТуэМорса.
6.2 Порядки точек относительно слов из ТМ.
6.3 Доказательство теоремы об индексах приближений
7 Полиномиальные КАСязыки
7.1 Асимметричный случай, Е 2
7.2 Асимметричный случай, 2. Паутинные автоматы.
7.3 Симметричный случай. Обобщенные паутинные автоматы
8 Сходимость полиномиальных приближений.
8.1 Паутинные языки.
8.2 Расширение антисловарей.
9 Две серии языков промежуточной сложности
9.1 Суперполиномиальность.
9.2 Субэкспоненциальность
Продолжаемые подмножества языков
.1 Сравнение индексов роста.
.2 Суперполиномнальный скачок роста
Экспоненциальные КАСязыки.
.1 Базовые свойства КАСавтоматов.
.2 Сграфы и редукция антисловарей
.3 Маленькие компоненты бинарных Сграфов.
.4 Алгоритм проверки кандидатов в компоненты
.5 Взаимное расположение компонент Сграфа.
Глава 3. Языки, избегающие степени
Стабильные экспоненты
.1 Некоторые свойства морфизма в и языков ТМ и ОЯ
.2 Доказательство теоремы о 2стабильных экспонентах.
.3 73свободный морфизм .
Контекстная эквивалентность
.1 Классификация слов из ОР
.2 Сравнение сильно продолжаемых слов.
.3 Сравнение продолжаемых вправо слов
.4 Алгоритм решения проблемы эквивалентности.
ОГЛАВЛЕНИЕ
Верхние оценки индекса роста.
.1 Использование симметрии. Алгоритм .
.2 Построение факторантисловаря.
.3 Построение факторавтомата
.4 Существование особого случая.
.5 Свойство вложенных степеней
.6 Численные оценки индексов роста
Нижние оценки индекса роста
.1 Доказательство теоремы о нижней оценке.
.2 Скорость вычисления нижней оценки.
.3 Численные оценки индексов роста.
Структура и сложность граничных языков
.1 Кодировка Пансьс и цилиндрическое представление.
.2 Типы повторов.
.3 Анализ уравновешенных повторов
.4 Численные оценки индексов роста.
Индекс роста как функция двух параметров .
.1 Закономерности изменения индекса роста
.2 Асимптотические формулы для индекса роста при 32
.3 Асимптотические формулы для индекса роста при 3 2
.4 Асимптотика индекса роста при 3
I Оценка индекса роста для других классов языков
.1 Языки, избегающие шаблоны.
.2 Языки, избегающие абелевы степени.
Глава 4. Сложность антифакториальных языков
Минимальные квадраты в алфавите из трех букв .
.1 Сведение к бинарным словам
.2 Сведение к маршрутам в графе I,
.3 Построение маршрутов заданного веса.
Существование минимальных Зстспенсй
.1 Случай бинарного алфавита.
2 Большие алфавиты и большие экспоненты.
.3 Большие алфавиты и маленькие экспоненты.
Литература
- Київ+380960830922