Оглавление
Введение
1 Перезапись регулярных путевых запросов и полугруппы регулярных языков
1.1 Вычисление запросов с использованием представлений.
1.1.1 Базы данных, запросы, представления.
1.1.2 Области применения перезаписей запросов
1.2 Перезапись регулярных путевых запросов.
1.2.1 Основные понятия и обозначения.
1.2.2 Модель полуструктурированных данных
1.2.3 Максимальная перезапись запросов.
1.2.4 Частичная перезапись запросов
1.2.5 Однословная перезапись запросов
1.3 Применение алгоритмических методов алгебры в задачах перезаписи запросов
1.3.1 Перезапись запросов как задача принадлежности для полугруппы регулярных языков.
1.3.2 Поиск перезаписи с дополнительными ограничениями.
1.3.3 Применение задачи равенства слов при перезаписи запросов.
1.3.4 Оценка выразительной силы набора представлений.
1.4 Полугруппы с эффективно решаемой задачей равенства слов
1.4.1 Автоматные полугруппы
1.4.2 Рациональные полугруппы
1.4.3 Полугруппы Клини.
1.5 Выводы.
2 Рациональные множества регулярных языков
2.1 Принадлежность полугруппе и рациональному множеству
2.1.1 Принадлежность рациональному множеству.
2.1.2 Анализ сложности алгоритма проверки принадлежности рациональному множеству .
2.2 Ядро полугруппы или класс эквивалентности
2.2.1 Регулярность класса эквивалентности полугруппы
2.2.2 Алгоритм построения класса эквивалентности
2.2.3 Оптимальная перезапись запроса
2.3 Конечность полугруппы и рационального множества
2.3.1 Конечность полугруппы .
2.3.2 Конечность рационального множества
2.3.3 Анализ сложности алгоритма проверки конечности рационального множества
2.4 Эквивалентность полугрупп и рациональных множеств
2.4.1 Алгоритм проверки вложенности полугрупп
2.4.2 Неразрешимость задачи эквивалентности рациональных множеств .
2.5 Выводы.
3 Задача равенства слов для полугрупп регулярных языков
3.1 К автоматности полугрупп регулярных языков.
3.1.1 Автоматность рациональных полугрупп.
3.1.2 Нерациональность конечно порожденной полугруппы регулярных языков
3.2 Случай однобуквенного алфавита.
3.2.1 Строение полугрупп в случае конечных порождающих элементов .
3.2.2 Строение полугрупп в случае произвольных порождающих элементов,
содержащих пустое слово.
3.2.3 Автоматность полугрупп регулярных языков
3.2.4 Клиновость, рациональность полугрупп регулярных языков.
3.3 Выводы
4 Реализация и тестирование алгоритмов
4.1 Реализованные алгоритмы.
4.1.1 Подсистема вычисления запроса
4.1.2 Построение максимальной перезаписи .
4.1.3 Построение однословной перезаписи
4.2 Эксперименты с перезаписью .
4.2.1 К задаче равенства слов
4.2.2 К константе Хашигучи.
4.3 Выводы
Заключение
Приложения
Литература
- Київ+380960830922