Схемы программ с константами

• Автор: Русаков, Дмитрий Михайлович
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2008
• Место защиты: Москва
• Количество страниц: 90 с. : ил.

ОГЛАВЛЕНИЕ
Страница
Введение
ГЛАВА 1. Алгебраическая модель программ с константами

1.1. Алгебраические модели программ
1.2. Матрично-алгебраические модели программ
1.3. Модель программ с константами
ГЛАВА 2. Подкласс схем с однократным вхождением константы
2.1. Критерий включения в классе
2.2. От схем программ к диаграммам
2.3. Проблема включения области определения для диаграмм из Пгад
и проблема включения в М.
2.4. Решение задач
ГЛАВА 3. Сложность проблемы включения
3.1. Каркас схемы
3.2. Алгоритм проверки включения схем
3.3. Сложность проблемы включения
ГЛАВА 4. Концепция альтернативного алгоритма проверки включения схем
4.1. От схем программ с константами — к диаграммам
4.2. Задачи для схем программ без констант
4.3. Конечные автоматы, используемые для проверки критерия вклю-
чения диаграмм
4.4. Методика проверки требования 2) леммы

ГЛАВА 5. Альтернативный алгоритм проверки включения в ШІоо
5.1. Алгоритм включения диаграмм
5.2. Использование конечных автоматов для проверки отношений над
схемами программ без констант
5.3. Алгоритмы над автоматами
5.4. Оценка сложности
Заключение
Литература

СПИСОК ИЛЛЮСТРАЦИЙ
1.1 Алгебраическая схема программ
1.2 Дерево распознавателей
1.3 Матрично-алгебраическая схема программ
2.1 Пустая схема
2.2 Пустая схема
4.1 Диаграмма
4.2 Схема программы
4.3 Автомат из Л
4.4 Автомат, принимающий множество К (С)
5.1 Схема алгоритма

Пусть г«1 £ У(В{) и гт2 — путь из ПД1?2), согласованный с гщ и завершающийся в с-вершине, где с ф с*. Это означает, что существует функция из 0(Р 1), которая в В прокладывает ветвь гщ, ав Дг- ветвь, начинающуюся путём и>2- Заменяя в функции д компоненту цс любой функцией из О (с, гщ), мы будем получать функции разметки из С, которые по прежнему прокладывают ветвь Из (2.4) следует, что каждая такая функция прокладывает в В2 некоторую ветвь. Легко увидеть, что последняя начинается путём гг2. Отсюда следует отношение (2.3).
Достаточность. Пусть для любого гщ из ]¥{В) выполнено: если гс2 из У(В2) согласован с 11)1, то и>2 перспективен для гщ.
Чтобы установить (2.4), рассмотрим произвольную функцию д из 0{В). Обозначим ветвь, которую она прокладывает в В. Так как (2.3) заведомо выполняется для со, то функция у прокладывает в В2 некоторый путь т21 длины 1. Очевидно, что ги>21 согласован с ш. Предположим, что ш2 закапчивается с-верпшной. Если с = с*, то уже доказано, что д. £ 0(В2). Пусть с ф с*. Тогда в силу (2.3) функция д прокладывает продолжение пути ш21 ещё на одну дугу; обозначим ш22 это продолжение. Путь гу22 сочетаем с гщ. Если он не завершается в с*-вершине, то к нему применимо рассуждение, проведённое для №21- Легко видеть, что продолжая такие рассуждения, мы получим ветвь из ТУ(В2), то есть [1 £ 0(В2).
Лемма 4 доказана.
Сформулируем задачи, решение которых предусматривается теоремой 4.
Для этого введём необходимые понятия.
Пусть уо — символ, добавляемый к алфавиту Уф и
У = фи {г/о}-
Рассмотрим слово в алфавите У х X, удовлетворяющее требованию: оно начинается парой (уо,х), где х 6 X, и не содержит других пар с символом