Теория направленных отношений и ее приложения

• Автор: Фальк, Вадим Николаевич
• Шифр специальности: 05.13.11
• Научная степень: Докторская
• Год защиты: 2001
• Место защиты: Москва
• Количество страниц: 260 с. : ил

Оглавление

1. ТИПИЗИРОВАННЫЕ НАПРАВЛЕННЫЕ ОТНОШЕНИЯ

1.1. Основные понятия. б

1.2. Свойства отношений.

1.3. Языки схем отношений

1.4. Классы отношений

1.5. Операции композиции отношений.

1.6. Комбинаторные отношения.

1.7. Дефинициональные расширения.

1.8. Основные сигнатуры

1.9. Конструктивные отношения.

1.9.1. Определение класса конструктивных отношений
1.9.2. Основные результаты
1 Иерархия классов отношений.
1 Исчисления включения и эквивалентности схем отношений . .
. Отношения включения и эквивалентности схем
отношений
. Исчисление сильного включения ациклических схем отношений.
. Отношение включения рекурсивных схем отношений . . .
. Отношение сильного включения схем конструктивных отношений
Основные результаты.
2. СЕТЕВАЯ ИНТЕРПРЕТАЦИЯ СХЕМ НАПРАВЛЕННЫХ
ОТНОШЕНИЙ
2.1. Графические представления схем отношений.
2.2. Базисы и сети.
2.3. Элементарные сети.
2.4. Операции композиции сетей.
2.5. Свободные и связанные сети. Вложение сетей
2.6. Сетевые языки.
2.7. Сетевая интерпретация рекурсивных схем отношений
ТЕОРИЯ НАПРАВЛЕННЫХ ОТНОШЕНИЙ И ЕЕ ПРИЛОЖЕНИЯ
ОГЛАВЛЕНИЕ
2.8. Реляционная интерпретация сетевых языков.
2.9. Примеры задания сетевых языков и их реляционной интерпретации
2 Формализация отношений реляционного включения и эквивалентности сетевых языков.
2 Примеры индуктивных доказательств эквивалентности
сетевых языков в конструктивных базисах
Основные результаты.
3. БЕСТИПОВЫЕ НАПРАВЛЕННЫЕ ОТНОШЕНИЯ
3.1. Сигнатуры языков схем бестиповых отношений
3.2. Представление типизированных рекурсивных схем бестиповыми регулярными схемами
3.3. Вычислительная полнота множества констант языка бестиповых регулярных схем отношений основной универсальной
сигнатуры
Основные результаты.
4. ФУНКЦИОНАЛЬНЫЕ НАПРАВЛЕННЫЕ ОТНОШЕНИЯ
4.1. Основные определения.
4.2. Необходимые и достаточные условия функциональности. .
4.3. Функциональные графсхемы отношений.
4.4. Модели вычислений функциональных отношений
4.4.1. Вычисление отношений в конструктивных базисах.
4.4.2. Вычисление рекурсивных функциональных отношений. . .
4.4.3. Вычисление отношений, заданных функциональными графсхемами
Основные результаты
5. НАПРАВЛЕННЫЕ ОТНОШЕНИЯ И ТЕОРИЯ СХЕМ ПРОГРАММ. .
5.1. Стандартные и рекурсивные схемы программ
5.2. Представление семантики схем программ средствами теории направленных отношений
Основные результаты
6. НАПРАВЛЕННЫЕ ОТНОШЕНИЯ И ЛОГИКА ПЕРВОГО
ТЕОРИЯ НАПРАВЛЕННЫХ ОТНОШЕНИЙ И ЕЕ ПРИЛОЖЕНИЯ
ОГЛАВЛЕНИЕ
ПОРЯДКА .
6.1. Трансляция схем направленных отношений в логический язык первого порядка
6.2. Представление логических формул схемами направленных отношений
6.3. Представление логических формул в исчислении сильного включения схем направленных отношений
Основные результаты.
7. НАПРАВЛЕННЫЕ ОТНОШЕНИЯ И ЛОГИЧЕСКИЙ ВЫВОД
7.1. Метод сетевой резолюции
7.2. Сетевая резолюция в логике первого порядка с равенством .
7.3. Доказательство противоречивости системы включений как альтернатива резолютивному логическому выводу
Основные результаты.
8. НАПРАВЛЕННЫЕ ОТНОШЕНИЯ И ФУНКЦИОНАЛЬНО
ЛОГИЧЕСКОЕ ПРОГРАММИРОВАНИЕ
8.1. Парадигмы функционального и логического программирования. .
8.2. Общие принципы построения языка функциональнологического программирования
8.3. Синтаксис языка .
8.4. Примеры программ на языке .
8.5. Архитектура и принципы реализации системы функциональнологического программирования.
Основные результаты.
СПИСОК ОБОЗНАЧЕНИЙ
СПИСОК СОКРАЩЕНИЙ.
СПИСОК ЛИТЕРАТУРЫ


Операция объединения ассоциативна и коммутативна. Операция пересечения отношений. Л, и Я2 как графиков. Для случая пересечения типизированных с1 отношений требуется равенство арностей с1 отношений , и Я2, причем результат пересечения имеет ту же самую арность. Операция пересечения ассоциативна и коммутативна. Операция конкатенации. Д, а, ДД2 а, Д е л, й,Д2е Д,. Для типизированных с1 отношений конкатенация определена для операндов арностей л, л, и л,л2. Операция эквализации унификации. Я,УЯ2 2а1а2,ДаДе г,й2,Де Я2. Для типизированных с1 отношений эквализация определена для операндов арностей л,,л и л,. Условная композиция. Л, Д2 аа,0е Я2,а,Ге Я,. Для типизированных с отношений арности операндов условной композиции должны быть я,я, и я,я2. Результат композиции, очевидно, имеет арность второго операнда. Операция итерации. Л УА, где 0 ос9аа е О тождественное отношение,
Я1 Я и Д, Я0 Я. Я0 их,т. Для типизированных с отношений аргумент операции итерация должен иметь арность я,я, я 0 такую же арность будет иметь и результат итерации. Операция повторения. Для типизированных с отношений аргумент операции повторение должен иметь арность я,я, п. В заключение этого параграфа покажем эквивалентность задания рекурсивных схем с использованием оператора рекурсии и в форме системы уравнений. Пусть А рекурсивная схема отношений. Произведем переименование операторных переменных в А так, что для всех операторов они будут попарно различны и не будут совпадать со свободными переменными схемы А. Не ограничивая общности, будем считать, что входящие в А операторы имеют вид А,. Ак. А оператора вхождения в нее оператора х, А, на соответствующую операторную переменную х,. Очевидно, что для любой интерпретации р свободных переменных значение переменной х0 в минимальном решении этой системы уравнений в интерпретации р есть Ф9 А . Пусть, наоборот, теперь задана система уравнений вида х, А,, 0 к, где переменная х0 представляет интересующую нас схему А с отношений, причем в правых частях уравнений не используется оператор рекурсии. Полагая, что А1к А,, последовательно, для всех у кк 1,. А,и, 0 , где ЛНМ х, Л хуЛ,ш результат подстановки схемы х. Ау в правые части первых у 1 уравнений системы вместо всех вхождений переменной х ,. Наконец, искомую рекурсивную схему А определим как х0А. Комбинаторные отношения. Определение 1. Класс комбинаторных с отношений на носителе обозначим Я, полагая, что сам носитель ясен из контекста фактически нас интересует только его мощность. Замечание. Для многосортного носителя перестановка д индуцируется системой перестановок , Д для всех еГ. Теорема 1. Всякое комбинаторное отношение арности пп определяется множеством пар ,i, где некоторое отношение эквивалентности на множестве I пп индексов, а множество ребер графа на факторе множества I по отношению i с II
v,x. V Ii, , , i . Пустое множество задает пустое комбинаторное отношение. Комбинаторное отношение, индуцированное одноэлементным множеством , назовем простым. Класс простых комбинаторных отношений на обозначим Я. Среди простых комбинаторных отношений особо выделим следующие отношения 4
1 тождественные л,яарные, л0, отношения ,
. Здесь и далее мы не будем, если это не приводит к недоразумениям, различать обозначения констант символов языков и соответствующих отношений денотатов этих констант. ГГ. Теорема 1. Т конечно. Теорема 1. Я КсАг. Я.,. Теорема 1. Я КсЛ , где Х0 г Я ,,,и. Комбинаторные 3 отношения из Япа являются независимыми по операциям последовательной и параллельной композиции, если не ставится никаких ограничений на мощность носителя . Константа эквивалентна 0 для 2, для 2 и 1 О1 см. Дефинициональные расширения. Согласно теоремам 1. Покажем, например, каким образом через элементарные комбинаторные с отношения из Я с помощью операций композиции могут быть определены аналогичные им комбинаторные отношения любой арности л,л0. Пусть п. Ь , где . О, , . Хотя в определении этих с1 отношений участвует носитель , мы не отражаем его в изображении соответствующих констант, полагая, что О известен из контекста.