Универсальные хорновы классы графов и формальных языков

• Автор: Кравченко, Александр Владимирович
• Шифр специальности: 01.01.06
• Научная степень: Кандидатская
• Год защиты: 1999
• Место защиты: Новосибирск
• Количество страниц: 86 с.

Оглавление
Введение
1. Цветосемейства предикатных систем
1. Определения и предварительные результаты
2. Универсальные хорновы классы
3. Ядра, цветосемейства и нормальные формы
4. Конечно порожденные цветосемейства
5. Цветосемейства формальных языков
2. Антимногообразия и цветосемейства графов
6. Гомоморфизмы и конгруэнции графов
7. Цветосемейства графов
8. Решетка цветосемейств графов
9. Решетка антимногообразий графов
10. Решетка, квазимногообразий графов
11. Квазитождества и антитождества цветосемейств
3. Сложность решеток квазимногообразий графов и эндографов
12. Квазимногообразия ориентированных графов
13. Квазимногообразия эндографов
Литература

Введение
Универсальная хор нова логика является одним из важнейших фрагментов логики первого порядка. Это объясняется тем, что она достаточно проста, но при этом выразительна. Язык универсальной хорновой логики позволяет формулировать многие задачи, возникающие в математике. Это, например, проблемы вложения в алгебре, допустимые правила вывода в логике, аффинные пространства и отношение “между” в геометрии, алгебраические пространства замыкания в комбинаторике, дветосемейства графов и семейства интерпретируемости в формальных языках (см. [1]).
Основы теории универсальных хорновых классов были заложены А. И. Мальцевым в 50-60-х годах (см. [2]). В настоящее время эта теория является интенсивно развивающимся направлением и имеет приложения в теории моделей и универсальной алгебре, неклассической и алгебраической логике, теории дедуктивных систем, логическом программировании и теории баз данных. Универсальная хорнова логика взята за основу для создания новых языков программирования, для обработки баз данных, и становится одним из основных инструментов представления знания (см. Ковальски [3]).
Основным объектом исследования эквационалъной логики (теории многообразий) являются алгебры, т. е. системы функциональной сигнатуры. Эта теория представлена в монографиях Грет-цера [4], Бурриса и Санкаппанавара [5], Маккензи, Макналти и Тейлора [6] и Д. М. Смирнова [7]. В отличие от эквациональной логики, наибольший интерес для исследования в универсальной хорновой логике представляют предикатные системы. По мнению
Биркгофа [8] сейчас актуально изучать именно предикатные системы, и эта актуальность сохранится еще несколько десятилетий. Действительно, в различных областях математики естественно возникают классы систем, сигнатура которых состоит только из предикатных символов. Примерами таких классов могут служить, например, графы, формальные языки [9], пространства замыкания [10].
Алгебраический подход в универсальной хорновой логике был предложен в работах В. А. Горбунова и представлен в его монографии [1]. С помощью этого подхода удалось решить ряд известных проблем, стоявших в этой области, а также по-новому посмотреть на многие другие другие задачи.
Нетрудно заметить, что некоторые вопросы теории графов могут быть сформулированы в терминах гомоморфизмов: например, свойство графа быть гг-раскрашиваемым можно определить через существование гомоморфизма в полный граф с п вершинами. В теории формальных языков важную роль играет понятие интерпретации, которое также можно определить через существование гомоморфизмов. Это позволяет применять алгебраические методы к проблемам, казалось бы, далеким от универсальной хорновой логики.
Изучение гомоморфизмов графов было начато Сабидусси в конце 50-х-начале 60-х годов. Полученные им тогда результаты были опубликованы в [11]. Позднее, он же начал изучение еще одной алгебраической конструкции, подпрямых произведений, в случае графов и доказал аналог теоремы о подпрямом разложении [12]. В 60-е-70-е годы изучение гомоморфизмов графов и более общих предикатных систем было продолжено так называемой пражской школой теории категорий во главе с Хедрлином и Пултром. Полученные в это время результаты представлены в [13]. В конце 70-х-начале 80-х годов большое внимание уделялось вопросам иерархии классов интерпретаций формальных языков и цветосемейств

Пусть Я и В — алфавиты. Морфизмом называется такое отображение к : А* —» В*, что к{ии) = к{и)к[у) для всех и, у € А* (т. е. это обычный гомоморфизм свободных моноидов). Для подмножества А в А определен его образ к(Ь) = {к(т) : ю € В}. Морфизм И, называется побуквенным если /г(Я) С В.
Формальным языком, над А называется пара [А, Ь), где А С А*. Язык (Я, А) называется конечным, если множества А и А конечны. Для данных языков (Я, А) и (В, К) побуквенный морфизм И : Я —> В называется интерпретацией (Я, А) в (В, К), если А*(А) С К, где к* — единственное продолжение к до гомоморфизма из свободного моноида Я* в свободный моноид В*. Мы пишем (Я, А) < (В, К), если существует интерпретация (Я, Ь) в (В, К). Язык называется универсальным, если любой язык является его интерпретацией. Легко видеть, что язык (Я, А) универсален тогда и только тогда, когда Ь содержит подмоноид {а}*, порожденный одним элементом а <Е Я.
С языком (Я, Ь) над конечным алфавитом Я свяжем следующие языковые семейства:
- ЛЮ(Я, А) = {(В, К) : (В, К) < (Я, I)},
- £(Я, I) = {(5, /-Г) : (В, К) < (Я, Ь) и |В| < со},
- МЯ, Ц = {(В, К) : (В, АО < (Я, А) и |В|, | А| < со}.
Очевидно, для любых языков (Я1, АД и (Я2, А2) над конечными алвафитами имеют место импликации (Ях, АД = ПоДЯг, А2) =Ф-П(Я1,АД = £(Я2, А2) £д(Ях,АД = £д(Я2,А2). В [16] доказано, что выполняется также импликация АДЯАх) = £<д(Я2,А2) => .СоДЯх, А) = А00(Я2,А2), т. е. все указанные равенства эквивалентны. Используя результаты предыдущего параграфа, мы дадим другое доказательство этого факта.
Сначала установим соответствие между языками и предикатными системами специального вида. Рассмотрим предикатную сигнатуру Л = : п < со}, где Яп — д-местный предикатный