Об условиях разрешимости автоматных уравнений

• Автор: Лялин, Илья Викторович
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2011
• Место защиты: Москва
• Количество страниц: 84 с. : ил.

Оглавление
Введение

1. Общая характеристика работы

2. Содержание работы

3. Публикации по теме диссертации

4. Обзор литературы

4.1 Обобщенная сеть (В.Б. Кудрявцев)

4.2 Задача декомпозиции (А.К. Григорян)

4.3 Структурные автоматные уравнения

(A.C. Подколзин, Ш.М. Ушчумлич)

4.4 Автоматные уравнения для языков

(Н.В. Евтушенко и др.)
1 Уравнение с одной неизвестной
1.1 Упрощение автоматного уравнения с одной неизвестной
1.2 Вложимость автоматов
1.3 Алгоритм для определения вложимости
1.4 Уравнение с полной информацией
1.5 Уравнение без обратной связи
1.6 Уравнение с инициальными обратными связями
1.7 Уравнение с классическими обратными связями
1.8 Свойства вложимых и редуцированных множеств
2 Уравнение с двумя и более неизвестными
3 Решение во множестве детерминированных функций
3.1 Уравнение с одной неизвестной
3.2 Уравнение с двумя и более неизвестными
4 Список литературы

Введение
1. Общая характеристика работы
Вот уже несколько десятилетий происходит постоянный рост сложности интегральных схем. Путем синтеза из простейших элементов, таких как логические функции и задержки, создаются все более сложные системы, являющиеся по сути автоматными схемами. Современные интегральные схемы могут содержать миллиарды логических элементов. При этом на первый план выходит задача синтеза интегральной схемы. Когда известен автомат, который должна реализовать интегральная схема, и требуется этот автомат "собрать" из простейших элементов. В этой области могут оказаться полезными результаты работы, решающие задачу синтеза (построения) недостающего участка автоматных схем так, чтобы вся схема функционировала требуемым образом.
Рассматривается задача решения автоматных уравнений, которая заключается в следующем. Есть автоматная схема, некоторые автоматы которой можно заменять на другие автоматы. Требуется определить, можно ли произвести такую замену, чтобы схема стала эквивалентна некоторому заранее заданному автомату.
В работе используются методы теории автоматов, теории графов и теории алгоритмов.
Задача была впервые поставлена в общем случае академиком В.Б. Кудрявцевым в [3]. Частный случай решаемой задачи был рассмотрен А.К. Григоряном в [5] и [6]. В этих работах решаются автоматные уравнения с одной неизвестной для 4 видов схем. Позже A.C. Подколзин и Ш.М. Ушчумлич в [7] ввели понятие автоматного уравнения, отличное от понятия автоматного уравнения, рассматриваемого в этой работе, и описали алгоритм, перечисляющий все решения такого уравнения с одной неизвестной. Кроме того, Н.В. Евтушенко в своих работах [8] - [10] рассматривала автоматные уравнения для разных классов языков, в том числе и для недетермини-

рованных автоматов и получила необходимое условие для недетерминированного автомата, чтобы он был решением уравнения.
В работе впервые решается задача нахождения всех решений произвольного автоматного уравнения для одного неизвестного. Впервые рассматриваются уравнения с более чем одной неизвестной. Доказывается неразрешимость пролемы существования решения уравнений с более чем одной неизвестной.
Результаты работы могут оказаться полезными для теории автоматов, а также могут быть использованы при проектировании интегральных схем.
1. Предложен алгоритм для решения автоматного уравнения с одной неизвестной.
2. Доказана алгоритмическая неразрешимость проблемы существования решения автоматных уравнений с двумя и более неизвестными.
Автор выражает благодарность профессору В.А. Буевичу за постановку задачи, профессору Э.Э. Гасанову и академику В.Б. Кудрявцеву за ценные замечания при написании этой работы.
2. Содержание работы
Алфавит {0,..., к — 1} будем обозначать Еь-
Пусть А - произвольный конечный алфавит. Обозначим А* множество всех слов, а А00 — множество всех сверхслов над данным алфавитом.
Пусть а, 6 £ А*, тогда |а| будем обозначать длину слова а. а аЬ - конкатенация этих слов.
Функция / : А* —► В* называется детерминированной, если она удовлетворяет следующим условиям.
1) Если а £ А*, то |/(а)| = [а|.
2) Пусть ац = о(1)...а(Аг) и ач = а'(1).. .а'(к), /(ац) = 6(1)... Ь(к) и /(аг) = 6'(1).. .6'(/г). И пусть при всех в, 1 < в < к, если а(1) = а'(1),... ,й(я) = аДй), то 6(1) = 6'(1),..., 6(я) = 6'(з).
Детерминированная функция д : А* —> В* называется частичной для детерминированной функции / : А* —» В*, если существует такое 7 £ А*, что для любого слова а £ А* /('уа) = /(7)д(а).
Детерминированная функция называется ограниченно-детерминированной, или о.-д. функцией, если она имеет конечное множество частичных функций.
Детерминированным автоматом (ДА, или просто автоматом) называется шестерка (А, С^, В, ф, ф, д°). где:

ность массива - к х п. Обозначим т2[х,у] множество, стоящее в строке х, столбце у, причем 1<х<ки1<у<п.
Смысл массива то следующий. В то находится таблица вложения К в N. Определим функцию ад : —*■ 2и следующим образом:
Изначально таблица то инициализируется единицами (в алгоритме А). В этот момент она соответствует такому га, что для всех ад и qu Є го(д). Чтобы ад было вложением К в И, требуется выполнения двух свойств из определения вложения. Алгоритм А'2 расставляет в то нули, как бы "сужая" гг таким образом, чтобы начало выполняться условие 2) из определения вло-жимости. Алгоритм А2 заканчивает свою работу только тогда, когда для ад/ начинает выполняться условие 2). Если придется, /12 при этом может всю таблицу то забить нулями, и тогда условие 2) станет выполняться. После этого алгоритм А3 проверяет выполнение для ад условия 1). Если оно выполняется, значит для ад выполняются оба условия определения вложи-мости, и значит ад есть вложение К в N. Иначе К не вложим в N.
При этом массивы ті и т2 служат лишь для ускорения работы алгоритма А<
Используемые переменные: т - множество пар чисел,
вк, в'к, вп, .в'п, в", ва, з'а, з" - переменные, принимающие значение натурального числа.
Алгоритм определения ВЛОЖИМОСТИ СОСТОИТ ИЗ трех частей А, /12, Аз, запускаемых последовательно: сначала Ау, затем А%, и потом /Ц.
Алгоритм Ау заполняет массивы ту, т2, то- Ниже приведен этот алгоритм, и напротив каждой строки стоит число, означающее сколько раз данная стока запускается в процессе работы алгоритма.
ад Є иі(д) -^=5- то[ 1. Цикл вк от 1 до к
сколько раз работает строка

2. Цикл 5„ от 1 до ад
3. ®л] =
4. ш2^,вп] =
5. Цикл йа от 1 до а
к х п х а к х п х а к
к х п к х п х а
к х п к х п к х п
6. ті^., 5П, ба] = О
7. Цикл з*, от 1 до А;
8. Цикл 5П от 1 до п 9. Цикл яа от 1 до а