|
ОГЛАВЛЕНИЕ
Введение............................................ 5 Глава 1. Понятие автомата............................... 8 § 1. Понятие конечного автомата....................... 8 § 2. Обобщения понятия конечного автомата................ 31 Глава 2. Абстрактные автоматы............................ 39 § 1. Ограниченно-детерминированные функции.............. 39 § 2. Эквивалентность конечных автоматов................. 44 § 3. г-неотличимость конечных автоматов.................. 50 § 4. Отличимость состояний конечных автоматов............. 57 § 5. Кратные эксперименты с конечными автоматами.......... 63 § 6. Простые эксперименты с конечными автоматами.......... 80 § 7. Конечные автоматы как акцепторы................... 91 § 8. Конечные автоматы как сверхакцепторы............... 100 § 9. Конечные автоматы как перечислители................. 108 § 10. Взаимодействие конечных автоматов и конечные автоматы влабиринтах..........,........................ 116 § 11. Оценка числа автоматов приведенного вида.............. 130 § 12. Конечные автоматы как числовые акцепторы и преобразователи........................ 137 Глава 3. Структурные автоматы........................... 151 § 1. Ограниченно-детерминированные функции многих переменных............................ 151 § 2. Канонические уравнения.......................... 152 § 3. Операции над ограниченно-детерминированными функциями 155 § 4. Схемы. Структурный автомат...................... 161 § 5. Замыкание. Выразимость. Задача о полноте............. 164 § 6. Конечные А^-полные системы...................... 167 § 7. ?-полнота................................... 174 § 8. А -замыкание................................. 179 § 9. Предполные классы............................. 183 § 10. Алгоритмическая неразрешимость задач о К- и Л-полноте. 190 § 11. Разрешимый случай задачи о полноте. Линейные автоматы. 195 § 12. Ограниченно-детерминированные функции одной переменной 224 § 13. Группа AS2.................................. 229 § 14. Гомоморфизм автоматов. Моделирование............... 236
§ 15. Задача о выразимости для детерминированных функций...... 247
Глава 4. Однородные структуры........................... 253
§ 1. Определения и примеры.......................... 253
§ 2. Графы переходов однородных структур................ 265
§ 3. Анализ поведений однородных структур................ 274
§ 4. Моделирование в однородных структурах............... 295
Список литературы...................................... 311
Предметный указатель.................................... 314
Именной указатель..................................... 317
Список обозначений......................................318
|