Комбинаторные характеризации формальных языков

• Автор: Шур, Арсений Михайлович
• Шифр специальности: 01.01.06
• Научная степень: Докторская
• Год защиты: 2010
• Место защиты: Екатеринбург
• Количество страниц: 287 с. : ил.

Оглавление
Введение

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 Асимметричный случай, |Е|
7.2 Асимметричный случай, |Е| > 2. Паутинные автоматы
7.3 Симметричный случай. Обобщенные паутинные автоматы
§ 8 Сходимость полиномиальных приближений
8.1 Паутинные языки
в.2 Расширение антисловарей
§ 9 Две серии языков промежуточной сложности
9.1 Суперполиномиалыюсть
9.2 Субэкспоненциальность
§ 10 Продолжаемые подмножества языков
10.1 Сравнение индексов роста
10.2 Суперполиномиальный скачок роста
§11 Экспоненциальные КАС-языкп
11.1 Базовые свойства КАС-автоматов
11.2 С-графы и редукция антисловарей
11.3 Маленькие компоненты бинарных С-графов
11.4 Алгоритм проверки кандидатов в компоненты
11.5 Взаимное расположение компонент С-графа
Глава 3. Языки, избегающие степени
§ 12 Стабильные экспоненты
12.1 Некоторые свойства морфизма в и языков ТМ и ОР
12.2 Доказательство теоремы о 2-стабильных экспонентах
12.3 (7/3)+-свободный морфизм
§ 13 Контекстная эквивалентность
13.1 Классификация слов из ОР
13.2 Сравнение сильно продолжаемых слов
13.3 Сравнение продолжаемых вправо слов
13.4 Алгоритм решения проблемы эквивалентности
ОГЛАВЛЕНИЕ

§ 14 Верхние оценки индекса роста
14.1 Использование симметрии. Алгоритм U
14.2 Построение фактор-антисловаря
14.3 Построение фактор-автомата
14.4 Существование особого случая
14.5 Свойство вложенных степеней
14.6 Численные оценки индексов роста
§ 15 Нижние оценки индекса роста
15.1 Доказательство теоремы о нижней оценке
15.2 Скорость вычисления нижней оценки
15.3 Численные оценки индексов роста
§ 16 Структура и сложность граничных языков
16.1 Кодировка Пансьё и цилиндрическое представление
16.2 Типы повторов
16.3 Анализ уравновешенных повторов
16.4 Численные оценки индексов роста
§ 17 Индекс роста как функция двух параметров
17.1 Закономерности изменения индекса роста
17.2 Асимптотические формулы для индекса роста при /3^
17.3 Асимптотические формулы для индекса роста при ß <
17.4 Асимптотика индекса роста при ß ~ RT(k)
§ 18 Оценка индекса роста для других классов языков
18.1 Языки, избегающие шаблоны
18.2 Языки, избегающие абелевы степени
Глава 4. Сложность антифакториальных языков
§ 19 Минимальные квадраты в алфавите из трех букв
19.1 Сведение к бинарным словам
19.2 Сведение к маршрутам в графе Ä3
19.3 Построение маршрутов заданного веса
§ 20 Существование минимальных /7-степеней
20.1 Случай бинарного алфавита
20.2 Большие алфавиты и большие экспоненты
20.3 Большие алфавиты и маленькие экспоненты
Литература
Предметный указатель
Список обозначений
ГЛАВА 1. СЛОЖНОСТЬ РЕГУЛЯРНЫХ ЯЗЫКОВ

(3) если существует ровно г таких собственных чисел, а именно Ат,..., Аг, то А_,- = ае{, где у — 1,... ,г, а ег = е^2~1^ есть первообразный корень из единицы г-й степени',
(4) у М есть строго положительный собственный вектор, принадлежащий а.
Число а называется корнем Фробепиуса матрицы М если М — матрица смежности орграфа в, то а называют индексом (3 и обозначают 1пб(С). Заметим, что а — алгебраическое число. Известно (см. напр., [18]), что индекс орграфа равен максимуму из индексов его компонент. Компоненты индекса 0 одноэлементны (синглетоны), а компоненты индекса 1 являются простыми циклами. Эти два типа компонент мы называем тривиальными. Индексы остальных компонент строго больше единицы.
Количество г собственных чисел с максимальным модулем называется числом импримитивности неразложимой матрицы-(или сильно связного орграфа). Для орграфов это число равно наибольшему общему делителю длин всех циклов. Матрицы- и орграфы; для которых это число равно единице, называются примитивными. Сами собственные числа, но модулю равные а (кроме самого а), будем называть спутниками.
Приведенных выше сведений достаточно, чтобы понять, что задача вычисления компонент орграфа играет важную вспомогательную роль в данной.работе. Для ее решения мы будем использовать незначительно модифицированный алгоритм Тарьяна[164]. Это эффективный но памяти, линейный алгоритм нахождения всех компонент сильной связности орграфа. Вначале дадим его неформальное описание.
Алгоритм обходит орграф в глубину, удаляя из дерева поиска найденные компоненты. При этом достигается выполнение очень полезного свойства: каждая компонента в момент обнаружения является поддеревом в текущем* дереве поиска. Корни, этих; поддеревьев назовём корнями компонент. Пусть Т[д] — номер вершины в порядке обхода в глубину, а Я[и] = шп{Г[а] | и достижима из и, V достижима из и}. Тогда вершина-д является корнем компоненты в том и только в том случае, если Я[у] = Ту. Помимо массивов 2Г и Т в алгоритме также используется стек для вершин 5, в который вершины добавляются в порядке их обнаружения. Если вершина и — корень компоненты, то все вершины, лежащие в стеке выше и, принадлежат этой компоненте. Они удаляются из стека, и алгоритм продолжает работу. Если поиск в глубину закопчен, но в графе остались непройденные вершины, поиск запускается из любой вершины в оставшейся части графа.
Алгоритм Тарьяна мы будем применять к автоматам, все вершины которых достижимы из начальной вершины. Таким образом, дерево поиска можно сделать единственным; алгоритм в данном случае реализуется запуском из начальной вершины рекурсивной процедуры.
Алгоритм Т
Вход: орграф С = (V, Е), вершина 5, из которой достижимы все вершины.
Выход: множество орграфов {б; = (V), 15;)}, состоящее из всех компонент орграфа С7.