Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
Глава 1. Основные понятия и определения . . . . . . . . . . . . . . 12
1.1 Элементы алгебры бинарных отношений и теории полугрупп . . 12
1.2 Элементы теории графов . . . . . . . . . . . . . . . . . . . . . . . 15
1.3 Элементы теории графовых автоматов . . . . . . . . . . . . . . . 18
Глава 2. Универсальные графовые автоматы . . . . . . . . . . . . . 21
2.1 Определяемость универсальных графовых автоматов своими
полугруппами входных сигналов . . . . . . . . . . . . . . . . . . . 24
2.2 Конкретная характеризация универсальных графовых автоматов 37
2.3 Об элементарной аксиоматизации классов универсальных
графовых автоматов . . . . . . . . . . . . . . . . . . . . . . . . . . 46
2.4 Строение изоморфизмов универсальных графовых автоматов . . 55
2.5 Группы автоморфизмов универсальных графовых автоматов . . . 61
Глава 3. Универсальные графовые полуавтоматы . . . . . . . . . . 65
3.1 Конкретная характеризация универсальных графовых
полуавтоматов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
3.2 Абстрактная характеризация универсальных графовых
полуавтоматов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
3.3 Относительно элементарная определимость класса
универсальных графовых полуавтоматов в классе полугрупп . . . 78
3.4 Приложения относительно элементарной определимости класса
универсальных графовых полуавтоматов в классе полугрупп . . . 87
Глава 4. Линейное упорядочивание автоматов . . . . . . . . . . . . 96
4.1 Алгоритм перебора с возвратами и отсечениями . . . . . . . . . . 97
4.1.1 Алгоритм перебора с возвратами и отсечениями для
полуавтоматов . . . . . . . . . . . . . . . . . . . . . . . . . 97
4.1.2 Алгоритм перебора с возвратами и отсечениями для
автоматов . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
4.2 Метод имитации отжига . . . . . . . . . . . . . . . . . . . . . . . . 106
3
Стр.
4.3 Алгоритм пчелиной колонии . . . . . . . . . . . . . . . . . . . . . 110
4.4 Программная реализация методов линейного упорядочивания
полуавтоматов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
Заключение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
Список литературы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
Список рисунков . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126
Список таблиц . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
Список алгоритмов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128
Приложение А. Свидетельства о государственной регистрации
программ для ЭВМ . . . . . . . . . . . . . .129
