Введение
1 Перезапись регулярных путевых запросов и полугруппы регулярных языков 11
1.1 Вычисление запросов с использованием представлений 11
1.1.1 Базы данных, запросы, представления 11
1.1.2 Области применения перезаписей запросов 17
1.2 Перезапись регулярных путевых запросов 19
1.2.1 Основные понятия и обозначения 20
1.2.2 Модель полуструктурированных данных 21
1.2.3 Максимальная перезапись запросов 23
1.2.4 Частичная перезапись запросов 24
1.2.5 Однословная перезапись запросов 25
1.3 Применение алгоритмических методов алгебры в задачах перезаписи запросов 26
1.3.1 Перезапись запросов как задача принадлежности для полугруппы регулярных языков 27
1.3.2 Поиск перезаписи с дополнительными ограничениями 28
1.3.3 Применение задачи равенства слов при перезаписи запросов 28
1.3.4 Оценка выразительной силы набора представлений 29
1.4 Полугруппы с эффективно решаемой задачей равенства слов 30
1.4.1 Автоматные полугруппы 31
1.4.2 Рациональные полугруппы 31
1.4.3 Полугруппы Клини 33
1.5 Выводы 34
2 Рациональные множества регулярных языков 36
2.1 Принадлежность полугруппе и рациональному множеству 36
2.1.1 Принадлежность рациональному множеству 37
2.1.2 Анализ сложности алгоритма проверки принадлежности рациональному множеству 42
2.2 Ядро полугруппы или класс эквивалентности 44
2.2.1 Регулярность класса эквивалентности полугруппы 44
2.2.2 Алгоритм построения класса эквивалентности 45
2.2.3 Оптимальная перезапись запроса 46
2.3 Конечность полугруппы и рационального множества 50
2.3.1 Конечность полугруппы 51
2.3.2 Конечность рационального множества 54
2.3.3 Анализ сложности алгоритма проверки конечности рационального множества 56
2.4 Эквивалентность полугрупп и рациональных множеств 56
2.4.1 Алгоритм проверки вложенности полугрупп 57
2.4.2 Неразрешимость задачи эквивалентности рациональных множеств . 57
2.5 Выводы 58
3 Задача равенства слов для полугрупп регулярных языков 60
3.1 К автоматности полугрупп регулярных языков 60
3.1.1 Автоматность рациональных полугрупп 62
3.1.2 Нерациональность конечно порожденной полугруппы регулярных языков 64
3.2 Случай однобуквенного алфавита 65
3.2.1 Строение полугрупп в случае конечных порождающих элементов . 66
3.2.2 Строение полугрупп в случае произвольных порождающих элементов, содержащих пустое слово 77
3.2.3 Автоматность полугрупп регулярных языков 90
3.2.4 Клиновость, рациональность полугрупп регулярных языков 101
3.3 Выводы 107
4 Реализация и тестирование алгоритмов 108
4.1 Реализованные алгоритмы 108
4.1.1 Подсистема вычисления запроса 108
4.1.2 Построение максимальной перезаписи 110
4.1.3 Построение однословной перезаписи 111
4.2 Эксперименты с перезаписью 113
4.2.1 К задаче равенства слов 113
4.2.2 К константе Хашигучи 115
4.3 Выводы 121
Заключение 123
Приложения 124
Литература 130
