Структурный анализ многоленточных автоматов

• Автор: Хачатрян, Владимир Ервандович
• Шифр специальности: 01.01.09
• Научная степень: Докторская
• Год защиты: 2008
• Место защиты: Белгород
• Количество страниц: 201 с. : ил.

Оглавление
Введение
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 Допустимые срезы класса эквивалентности и построение минимальных автоматов в них
Заключение
Список литературы

Введение
Модель вычислений в широком смысле может трактоваться как множество конструктивных объектов с приписанной ему универсальной процедурой, посредством которой каждому объекту сопоставляется порождаемое им множество.
Классическими моделями вычислений являются алгебраические выражения, формулы логики, конечные автоматы, абстрактные вычислительные машины, схемы программ и другие [2,4,5,9,11,13,23,72,84,102,110]. Исследование моделей вычислений позволяет, с одной стороны, заняться только изучением тех конкретных свойств, которые заложены в данную модель вычислений, абстрагируясь от всех остальных, что позволяет обычно добиться положительного результата ввиду упрощения исходной задачи. С другой стороны, полученные результаты обычно переносимы на более сложные реальные объекты. Это достигается путем наложения на последние дополнительных ограничений, нацеленных на возможность использования исследованной модели вычислений.
При изучении моделей вычислений необходимо решить такие проблемы, как проблема эквивалентности, эквивалентных
преобразований, минимизации и некоторые другие. Это фундаментальные проблемы теории моделей вычислений.
Изучение вышеописанных проблем для обычных конечных детерминированных автоматов позволило решить многие проблемы, возникшие в вычислительной технике и программировании.
Предлагаемая работа посвящена решению фундаментальных проблем классической модели вычислений - многоленточных автоматов, введенной М. Рабином и Д. Скоттом в 1959 году в их классической статье [110]. Эта модель является естественным обобщением конечных детерминированных автоматов, состоящим в переходе от одной ленты,

Рис. 2.4.
На рис. 2.4 показано, каким образом преобразуется q-вepшинa, являющаяся внешним выходом, одна из дуг которой направлена в нее же.
Шаг 3. Рассмотрим в диаграмме О]" фрагмент Рь внутренними вершинами которого являются внутренние вершины фрагмента Б', а также все его внешние выходы. Легко увидеть, что Р1 - фрагмент с границей.
К фрагменту Р ] применим преобразование по аксиоме С4, заменив его фрагментом Р2; при этом вершину, являющуюся образом вершины VI1, обозначим VI*. Полученная диаграмма, обозначим ее О]*, удовлетворяет требованиям леммы 2.5, упомянутая в ней вершина, эквивалентная вершине
У2,-ЭТО У)*.
На рис. 2.3 г. приведен фрагмент, полученный после шага 3 из фрагмента, приведенного на рис.2.3 в.
Лемма 2.5 доказана.