Оглавление
Введение
1. Основные понятия, постановка рассматриваемых задач и
средства их решения
1.1 Определение многоленточного автомата.
1.2 Рассматриваемые проблемы в теории многоленточных автоматов
1.3 Проблема эквивалентных преобразований
1.4 Проблема эквивалентности и включения.
1.5 Проблема минимизации и поиска всех минимальных форм
1.6 Фрагментиые преобразования. Общий подход к решению проблем.
2.Частичная разрешимость проблемы эквивалентности в множестве всех детерминированных бинарных многоленточных автоматов и в двух его подмножествах построение полных систем э. п..
2.1 Полная система фрагментных преобразований для многоленточных автоматов.
2.2 Полная система для автоматов с непересекающимися циклами
2.3. Полная система для однородных автоматов.
3. Трансформационный метод анализа структуры многоленточных автоматов.
3.1 Метод трансформационного распознавания эквивалентности
в моделях вычислений.
3.2 Применение трансформационного метода для случая
автоматов с непересекающимися циклами
3.3Достаточное условие применимости трансформационного
метода и его использование
3.4 Классификация сечений для конечных автоматов.
3.5 Использование трансформационного метода для случая с неразрешимой проблемой включения.
4. Обобщенная проблема минимизации и ее решение в одном классе двухленточных автоматов
4.1. Множество М детерминированных бинарных двухленточных автоматов и некоторые их свойства
4.2. Система Т эквивалентных преобразований автоматов и сведение обобщенной проблемы минимизации из М в М.
4.3 Срезы класса эквивалентности и стратегия поиска минимальных автоматов в классе эквивалентности.
4.4 Главный срез и минимальные в нем автоматы.
4.5 Допустимые срезы класса эквивалентности и построение минимальных автоматов в них
Заключение
Список литературы
- Київ+380960830922