Введение
Глава1.Вспомогательные сведения 14
1.1. Слова, языки и подстановки 14
1.2. Машины Тьюринга и модель обобщённо-недетерминирован-ных автоматов 16
1.3. Основные классы сложности и модели вычислений 19
1.4. Преобразователи и сводимости 22
1.5. КС-языки 24
1.6. Базовые конструкции с автоматами и грамматиками 28
Глава 2. Модель обобщённо-недетерминированных ав томатовивопросы разрешимости 31
2.1. Модель обобщённо-недетерминированных автоматов 32
2.2. Вопросы разрешимости 36
2.3. Задачи реализуемости для сверхслов и монадические теории 41
2.4. Эквивалентность задач регулярной и префиксной реализуемости 45
Глава 3. Регулярная реализуемость для КС-языков 49
3.1. Рациональные конусы 51
3.1.1. Основные свойства и примеры 52
3.1.2. Структурные свойства рациональных конусов 56
3.1.3. Рациональные конусы и задачи регулярной реализуемости
3.2. Регулярные языки 63
3.3. Лёгкие NRR задачи для КС-фильтров 70
3.4. Трудные NRR задачи для КС-фильтров 76
3.5. Полиномиальный рациональный индекс 85
Глава 4. Автоматысословарём 89
4.1. Определение и свойства 89
4.1.1. Примеры языков 92
4.1.2. Нормальные формы
4.2. P и NP-полные языки 102
4.3. Автоматы со словарём и рациональные конусы 106
4.4. Принадлежность языков класса SA классу NP
4.4.1. Общий план 112
4.4.2. Вспомогательные конструкции 116
4.4.3. Основная часть доказательства 120
Заключение 132
Список литературы
