Об условиях разрешимости автоматных уравнений тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат физико-математических наук Лялин, Илья Викторович

• Лялин, Илья Викторович
• кандидат физико-математических наук
• 2011

Оглавление диссертации кандидат физико-математических наук Лялин, Илья Викторович

Введение

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 Уравнение с двумя и более неизвестными.

Введение диссертации (часть автореферата) на тему «Об условиях разрешимости автоматных уравнений»

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

Вот уже несколько десятилетий происходит постоянный рост сложности интегральных схем. Путем синтеза из простейших элементов, таких как логические функции и задержки, создаются все более сложные системы, являющиеся по сути автоматными схемами. Современные интегральные схемы могут содержать миллиарды логических элементов. При этом на первый план выходит задача синтеза интегральной схемы. Когда известен автомат, который должна реализовать интегральная схема, и требуется этот автомат "собрать" из простейших элементов. В этой области могут оказаться полезными результаты работы, решающие задачу синтеза (построения) недостающего участка автоматных схем так, чтобы вся схема функционировала требуемым образом.

Рассматривается задача решения автоматных уравнений, которая заключается в следующем. Есть автоматная схема, некоторые автоматы которой можно заменять на другие автоматы. Требуется определить, можно ли произвести такую замену, чтобы схема стала эквивалентна некоторому заранее заданному автомату.

В работе используются методы теории автоматов, теории графов и теории алгоритмов.

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

В работе впервые решается задача нахождения всех решений произвольного автоматного уравнения для одного неизвестного. Впервые рассматриваются уравнения с более чем одной неизвестной. Доказывается неразрешимость пролемы существования решения уравнений с более чем одной неизвестной.

Результаты работы могут оказаться полезными для теории автоматов, а также могут быть использованы при проектировании интегральных схем.

1. Предложен алгоритм для решения автоматного уравнения с одной неизвестной.

2. Доказана алгоритмическая неразрешимость проблемы существования решения автоматных уравнений с двумя и более неизвестными.

Автор выражает благодарность профессору В.А. Буевичу за постановку задачи, профессору Э.Э. Гасанову и академику В.Б. Кудрявцеву за ценные замечания при написании этой работы.

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

Алфавит {0,., к — 1} будем обозначать E¡¡.

Пусть А - произвольный конечный алфавит. Обозначим А* множество всех слов, а ^4°° - множество всех сверхслов над данным алфавитом.

Пусть a, b G А*, тогда |а| будем обозначать длину слова a. a ab - конкатенация этих слов.

Функция / : А* —»• В* называется детерминированной, если она удовлетворяет следующим условиям.

1) Если а б А*, то |/(а)| = (а|.

2) Пусть ai = а(1). а(к) и а2 = а'(1). .a'(fc), /(ai) = b(l).b(k) и /(«г) = b'(l). .b'{k). И пусть при всех s, 1 < s < к, если а( 1) = а'(1), ■., a(s) = a'(s), то Ъ(1) = 1/(1),., 6(s) = V(s).

Детерминированная функция д : А* В* называется частичной для детерминированной функции / : А* —> В*, если существует такое 7 G А*. что для любого слова a G A* /(7a) = f(y)g(ce).

Детерминированная функция называется ограниченно-детерминированной, или о.-д. функцией, если она имеет конечное множество частичных функций.

Детерминированным автоматом (ДА, или просто автоматом) называется шестерка (A, Q, В, ф, ф, q°). где:

А - конечный входной алфавит;

В - конечный выходной алфавит;

Q - конечное множество состояний; ф : Q х А—> Q - функция переходов: ф : Q х АВ - функция выходов; q° G Q - начальное состояние.

В случае, когда Л = А\ х А2 х . х Ап, будем говорить, что автомат имеет п входов и алфавит г'-ого входа

В случае, когда В = В\ х В2 х . х Вгп, будем говорить, что автомат имеет т выходов и алфавит г-ого выхода - Вг. При этом функция выходов ф : Q х А —»■ В разбивается на т функций выходов фг : Q х А —► Вг, 1 < i < т следующим образом. Если для некоторых, g G Q и a G /1 Ф(<1, о) = (bi, b2,., bm), то а) = Ьъ. То есть ^ = ^ х ф2 х . х

Множество автоматов с входным алфавитом А и выходным В обозначим Р(А,В).

Обозначим Р множество всех таких автоматов, каждый вход и выход которого имеет алфавит Е^ где к - некоторое натуральное число, для каждого входа или выхода своё.

Пусть здесь и далее v = (A, Q, В, ф^ ?/;, q°) - детерминированный автомат.

Обозначим Ф : А* —> Q функцию, возвращающую состояние Ф(а), в котором окажется автомат v, если на вход ему подать слово а. Более строго:

1) Ф(А) = q°. где А - пустое слово:

2) Ф(а(1). а(п - 1)а(тг)) = ^(Ф(а(1). а(п - 1)), а(п)).

Обозначим Ф* : А* —» Q* функцию, возвращающую последовательность состояний Ф*(а), через которые проходит автомат г>, если на вход ему подать слово а. Более строго:

1) Ф*(Л) = 5°, где Л - пустое слово;

2) Ф*(а(1). а(п - 1)а(п)) = Ф*(а(1). а(п - 1))Ф(а(1). а(п)).

Обозначим Ф : А* —> В функцию, возвращающую последнюю букву

Ф(а), выданную на выходе автомата v, если на вход ему подать слово а. Более строго:

Ф(а(1). .а(п — 1)а(гс)) = ф(Ф(а(1) .а(п- 1)), а(п)).

Обозначим Ф* : А* —> В* функцию, возвращающую выходную после-довательттость Ф*(а), выданную на выходе автомата v, если на вход ему подать слово а. Более строго:

1) Ф*(Л) = Л, где Л - пустое слово;

2) Ф*(а(1). а(п - 1)а(тг)) = Ф*(а(1). а{п - 1))Ф(а(1). а(п)).

Функцию Ф* будем называть функцией автомата у.

В [4] доказывается, что функция любого автомата всегда является о.-д. функцией, и наоборот: для любой о.-д. функции существует автомат, функцией которого она является.

Два автомата называются эквивалентными, если их автоматные функции совпадают.

Определим некоторые элементарные операции над автоматами, с помощью которых будут строиться автоматные схемы:

Операцией добавления фиктивного входа (см. рис. 1) будем называть функцию, отображающую множество Р(А, В) во множество Р(А х А', В), такую что произвольный автомат у = (А, С^ В, ф: ф, (р) переходит в автомат у' = (А х А', ф, В, ф', ф\ д°), такой что для всех д е <5, а £ Л и а' € Л' выполняется:

Ф'{Ъ а')) = а);

Ф'(<1, {а, а')) = ^(<?,а).

Таким образом, операция добавления фиктивного входа просто добавляет ещё один вход к автомату, при этом новый вход становится несущественным. Обозначается данная операция

Операцией изъятия выхода (см. рис. 2) будем называть функцию, отображающую множество Р(А, В х В') во множество Р(А, В), такую что произвольный автомат у = (А, В\ х . х Вт, ф, ф, д°) переходит в автомат у' = (А, х . х Вт-1,ф,ф',д°), такой что для всех д е а € А и 1 < г < т — 1 выполняется: ФМ, а)

Таким образом, операция изъятия выхода просто игнорирует последний выход автомата. Обозначается данная операция 2%.

Пусть Ап-1 = Ап. Операцией склеивания входов (см. рис. 3) будем называть функцию, отображающую множество Р{А\ х . х Ап 1 х Ап,В) во множество Р(А\ х . х Ап-1,В), такую что произвольный автомат у = (Ах х . х Ап 1 х Ап, В, ф, ф, д°) переходит в автомат у' = (Ах х . х Ап1, В, ф', ф5°), такой что для всех д € <5 и <2г- € А^ выполняется: д, (си,., апх)) = </>(д, (ах,., о„1, а„х)); ф'(д, (а1?., апх)) = ^(<7, (»1, • • •, апх)). а а а i i i i i i 1 г 1 1 1 1 1— 1 1 1 1 ■ ■ ■ ■

1 1 1 1 1 1 а а а а 1 1 1 1 1 1 ■ ■ ^ ■ ■ ■ ■ ■ ■

Рис. 1:

Рис. 2:

Рис. 3:

Рис. 4:

Рис. 5:

Рис. 6:

Рис. 7:

Рис. 8:

Обозначается данная операция З^.

Пусть произвольная перестановка элементов множества

1,. , п}. Операцией переименования входов (см. рис. 4) будем называть функцию, отображающую множество Р(А^ 1 х . х В) во множество Р{А\ х . х Ап,В), такую что произвольный автомат v — (А^ х . х А{п, В, ф, ф, д°) переходит в автомат у' = х . х Ап, СВ, ффд°). такой что для всех д € ф. а{ £ А{ выполняется:

Ф'{<1, («Ъ • • • > «п)) = </>(4, (а'гп - - •, Ог„)); аь ., ап)) = ^(д, (а^,• • •, а*п)).

Обозначается данная операция у' = 4х;(г;, ¿1,., гп).

Пусть ,., 2т - произвольная перестановка элементов множества {1 ,.,т}. Операцией переименования выходов (см. рис. 5) будем называть функцию, отображающую множество Р(А, В^ х . х Вгш) во множество Р(А, В\ х. х такую что произвольный автомат у = (А, (5, В^ х . х £?гт, ф, д°) переходит в автомат у' = (А, С£,В\Х . х Вт, ф, д°). такой что для всех д € <5, а€/1и1<&<т выполняется: а).

Обозначается данная операция 5е, г/ = .

Операцией расщепления выхода (см. рис. 6) будем называть функцию, отображающую множество Р(А, В\ х . х Вгп) во множество Р(А, В\ х . х Вт х Вт+х). такую что произвольный автомат у = (А, В\ х . х Бт, ф, ф, д°) переходит в автомат у' = (А, <5, х . х Вт х Вт+1, ф, ф', д°). такой что для всех д е а е А выполняется:

•(д, а) = ^-(д, а), если1 < ^ < т,

Обозначается данная операция Пусть = (Д <2, х . х Вт, ф, д°), г = (С1 х . х Сп, В, фг, фг, д5).

Скажем, что автомат 7ъ(у,г, г, э) = (А'^ х С2г,Вг,ф',ф', (д°, д®)} получен из автоматов и и г с помощью операции последовательного соединения (или выход г автомата у соединен со входом у автомата г, см. рис. 7). если выполняются следующие условия.

1) Вг С Су

2) А' = А X Сг х . х С/1 х х . х Сп.

3) I)' = X . . . X Вт X I).

4) <£'((д, дг), (а, сь ., с,-ь с,-+ь., сп)) = (0(д, а), (сь ., ?/>г-(д, а), ., сп))).

5) Если к < т, то ^¿.((д, (а, сь ., с7-ь с,-+ь., с„)) = ^(д, а).

6) ^т+жз) &)> о, сь . . . , су+1, . . . , с„)) = (С1, • • •,Сэ-иФМ, а), 1,., Сп)).

Будем говорить, что в состоянии д автомата г> = (Л1 х . х Ап, С^, В\ х . х £?то, ф,ф,(р) г-тый выход не зависит от ^'-того входа, если для любых а>к € Ак (1 < к < п) и любого а е А,- выполняется равенство

Ь • • •, %+ь • • • , Йп)) = («1, • ■ ■ , О-з-Ъ а> %+Ь ■ ■ • > ¿п))

Автомат у = (А\ х . х С^, В\х . .х Вт, ф, ф, д°) будем называть Ц-корректным для обратной связи, если выполняются следующие условия.

1) В состоянии д° г-тый выход не зависит от j-rroтo входа.

2) Если в состоянии д £ <3 г-тый выход не зависит от ^-того входа, то для любых ак € А}ц (1 < к < п) в состоянии д, (аь ., ^¿(д, Оъ • • •, ь ., ап)), а-,+1, ., ап)) г-тый выход тоже не зависит от ^-того входа.

Пусть автомат у = (А\ х . х Ап, С}, В\х . .х Вт, ф, д°) ¿^'-корректен для обратной связи. Будем говорить, что автомат г, = (А', <3', х . .хВт, ф',ф',д°) получен из автомата у с помощью операции инициальной обратной связи (см. рис. 8) для г-ого выхода и j-oгo входа, если выполняются следующие условия.

1) А' — А\ х . х А]-1 х 1 х . х Ап.

2) 0,' есть множество всех состояний автомата у. в которых г-тый выход не зависит от ^'-того входа.

3) Для любых ак Е Ак (1 < к < п) и д € О!

Ф'(<1, (¿ъ • • •, о-з-ъ • • •, о«)) = Ф(д, (аь ., Фг(ч, (аь • ■ ■, а„)), ь • • •, ап))

Поскольку автомат у 27-корректен для обратной связи, то ф' не выходит за рамки .

4) Для любых ак Е Ак {1 < к < п) и q Е Qf

1, - • ■, %-ъ Ц+и ■ - -, о«)) = (^1, • • •, ап)).

5) Для любых ак € Ак (1 < к < п), д € Я' и I ф г

Ф'М, ., %-ь ., Оп)) = (аь • • ■ > аз-ь ^¿(<7, («1, • • •, ап)), %+1,., ап))

Состояние автомата д называется достижимым, если существует такое а е А*, что Ф(а) = д.

Будем говорить, что выход г автомата v зависит с задержкой от входам, если в каждом достижимом состояния автомата V ¿-тый выход не зависит от ^-того входа.

Пусть в автомате V г-тый выход зависит с задержкой от ^'-того входа. Будем говорить, что автомат 9е[у^,]) получен из автомата v с помощью операции классической обратной связи для г-ого выхода и 7-ого входа, если

9е(М,.7') = 8

То есть инициальная обратная связь и классическая обратная связь есть одна и та же операция, отличаются они только областью определения. Классическая обратная связь определяется на множестве автоматов, у которых г-тый выход зависит с задержкой от ^'-того входа. Инициальная обратная связь определяется на ^/-корректных автоматах. Область определения инициальной обратной связи шире. Обычно в литературе, посвященной теории автоматов, рассматриваются классические обратные связи (поэтому они здесь и названы классическими). Однако при рассмотрении автоматных уравнений, чему посвящена данная работа, инициальные обратные связи оказываются намного естественнее. Забегая немного вперед скажем, что автоматные уравнения с одной неизвестной сначала решаются для инициальных обратных связей, а уже через этот результат - для классических.

В дальнейшем под операцией обратной связи (о. с.) мы будем подразумевать инициальную обратную связь.

Пусть VI = (Аи(21,В1,ф1,ф1,<$) и г>2 = (Л2, Я2, В2, Ф2, Я2)- БУДем говорить, что автомат у является декартовым произведением автоматов VI и и2, если V = (/Ц х А2,Я 1 х Я2,Вг х В2:фг х ф2,фх х (<#, д£)). Обозначается декартово произведение г>1 х у2.

Дадим рекурсивное определение автоматной схемы-шаблона с набором неизвестных (переменных) X, множеством входов А и множеством выходов В, которая является словом над алфавитом

Здесь обозначает символ запятой. Пусть каждой переменной из множества У — {т/1,1/2, • ■.} сопоставлен собственный входной алфавит А^ и выходной алфавит В{ таким образом, чтобы для каждой пары алфавитов А = Е^ х . х Е^ и В = Ег1 х . х Е1т существовало счетное множество переменных из У, имеющих такой входной и выходной алфавиты. Элементы множества У будем также называть неизвестными.

1) Пусть V - любой автомат из Р с входным алфавитом А и выходным алфавитом в. Тогда выражение v является схемой-птаблоном с пустым набором неизвестных, множеством входов А и множеством выходов В.

2) Пусть уг - неизвестная с входным алфавитом А и выходным алфавитом В. Тогда выражение у{ является схемой-шаблоном с набором неизвестных у г, множеством входов А и множеством выходов В.

3) Пусть 5 - схема-тттаблоп с набором неизвестных X, с входным алфавитом А\ х . х Ап и выходным алфавитом В. Тогда слово 1Е(5) является схемой-шаблоном с набором неизвестных X, входным алфавитом х . х Ап х Ап+1 и выходным алфавитом В.

4) Пусть Б - схема-шаблон с набором неизвестных X, с входным алфавитом А и выходным алфавитом В\ х . х Вт. Тогда слово 2Е(5) является схемой-шаблоном с набором неизвестных X, входным алфавитом А и выходным алфавитом В\ х . х Вт-х.

5) Пусть $ - схема-шаблон с набором неизвестных X, с входным алфавитом А\ х . х Ап и выходным алфавитом В. Тогда слово ЗЕ(б') является схемой-шаблоном с набором неизвестных X, входным алфавитом А\ х . х Ап-1 и выходным алфавитом В.

6) Пусть ,. ,гп - произвольная перестановка элементов множества {1,. , п}, <5 - схема-шаблон с набором неизвестных X, с входным алфавитом А{г х. х А{1Ь и выходным алфавитом В. Тогда слово 4£(5', г\,., гп) является схемой-шаблоном с набором неизвестных X, входным алфавитом Ь х . х Ап и выходным алфавитом В.

7) Пусть ., ут - произвольная перестановка элементов множества {1,., т}, Б - схема-шаблон с набором неизвестных X, с входным алфавитом А и выходным алфавитом В^ х . х В. Тогда слово 5£(5, ., ]ТП) является схемой-шаблоном с набором неизвестных X, входным алфавитом А и выходным алфавитом В1 х . х Вт.

8) Пусть Б - схема-шаблон с набором неизвестных X, с входным алфавитом А и выходным алфавитом В\Х. .х Вт. Тогда слово 6 XI (5) является схемой-шаблоном с набором неизвестных X, входным алфавитом А и выходным алфавитом В\ х . х Вт х Вт.

9) Пусть и £2 - схемы-шаблоны с набором неизвестных Х\ и Х^. с входными алфавитами А и А\ х . х Ап и выходным алфавитом В\ х . х Вт и В соответственно. И пусть 1<г<т\\1<2<п - такие, что ■Вг ^ А]. Тогда слово 7Е(51,г, £2,з) является схемой-тттаблоном с набором неизвестных (Х1, Х2), входным алфавитом А х А\ х . х Aj-1 х 1 х . х Ап и выходным алфавитом ^ х . х Вт х В.

10) Пусть Б - схема-нтаблон с набором неизвестных X, с входными алфавитами х . х Ап и выходным алфавитом Д х . х Вт. И пусть 1<1<тк1<з<п - такие, что В{ С А^. Тогда слова и 9Е(5, г,^) является схемами-шаблонами с набором неизвестных X, входным алфавитом Л х А\ х. х А^-1 х х. х Ап и выходным алфавитом Вх х . х 5ГО.

11) Пусть ¿>1 и ¿>2 - схемы-шаблоны с набором неизвестных Х\ и Х%, с входными алфавитами А\ и Л2 и выходным алфавитом В\ и соответственно. Тогда слово ¿>1 х ¿2 является схемой-шаблоном с набором неизвестных (^1, Х2); входным алфавитом А\ х и выходным алфавитом £1 х Д.

Схему-шаблон Б, имеющую набор неизвестных X = (т/^, ., тугп), будем обозначать Б(у{^., уг-п); или для простоты 5(^1,., жп), подразумевая под хз переменную уу.

Содержательно схема-шаблон представляет из себя автоматную схему, некоторые автоматы в которой "неизвестны", известно только их множество входов, выходов и то, как они соединяются с другими автоматами.

Автоматной схемой будем называть схему-шаблон с пустым набором неизвестных.

Пусть Б - произвольная автоматная схема. Дадим определение автомата, соответствующего схеме Б. Или автомата, который она реализует. Будем обозначать его АуЬ{Б).

1) Если в = V и у е Р, то АуЬ(3) = V.

2) Пусть 5 = 1Е(5"). Тогда если автомат Ау1{Б') определен, то Лг;£(5) = 1 я(АиЬ(Б')). Иначе Ау1(Б) не определен.

3) Пусть 5 = 2Е(5'). Тогда если автомат Ау1(Б') определен, то Avt(S) = 2(£")). Иначе Ау^Б) не определен.

4) Пусть Б = ЗЕ(5'). Тогда если автомат Аи^Б') определен, то АуЬ(Б) =

3^(Avt(S')). Иначе Aví(S) не определен.

5) Пусть S = 4E(,S",¿i,.,гп). Тогда если автомат Avt(S') определен, то Avt(S) = 4:Y¡(Avt(Sr), ¿i,., гп). Иначе Aut(S) не определен.

6) Пусть S = 5Е(5", ji,., jm). Тогда если автомат Avt(S') определен, то Avt{S) = 5z(Avt(S'),ji,., jm). Иначе Aví(S) не определен.

7) Пусть S = 6Е(5'). Тогда если автомат Avt(S) определен, то Avt(S) = 6е(Avt(S')). Иначе Avt(S') не определен.

8) Пусть S = 7E(5i, г, S-¿,j). Тогда если автоматы Avt(Si) и Avt{S2) определены, то Avt(S) — (Avt(S\), г, Aví(S'2),j). Иначе Avt(S) не определен.

9) Пусть S — 8Е(5', Тогда если автомат Avt(S') определен и ij-корректен для обратной связи, то Avt(S) = 8yj(Avt(S'), i,j). Иначе Avt(S) не определен.

10) Пусть S = 9Е(S', i,j). Тогда если автомат Avt(S') определен и его г-тый выход зависит со сдвигом от j-того входа, то Avt(S) = 9z(Avt(S'),i, j). Иначе Avt(S) не определен.

11) Пусть S = Si х ¡5*2• Тогда если автоматы Avt{S\) и Avt(S'¿) определены, то Avt(S) — Avt(Si) х Avt(S2). Иначе Avt(S) не определен.

Пусть дана схема-птаблон S(x\,., хп), в которой каждая неизвестная Xi имеет входной алфавит A i и выходной алфавит И пусть С\ € P(/li, ¿?i),., сп € Р(Ап, Вп) - такие автоматы, что если х^ = xj для некоторых i и j, то Ci = Cj. Инстанцированием схемы-шаблона S(reí,. ,rcn) автоматами ci,., Сп называется такая автоматная схема, которая получается из слова S заменой в нем букв Х{ буквами сг- соответственно для всех г от 1 до п. Если при этом полученная схема реализует некоторый автомат. то будем обозначать его так: S(ci,., сп). а если полученная схема не реализует никакого автомата, то будем говорить, что схема-шаблон S не может быть инстанцирована набором с\,., Сп.

Содержательно инстанцированием схемы-шаблона S(x\,., хп) является подстановка вместо неизвестных х±,. ,хп каких-то автоматов Ci,. .сп с тем же множеством входов и выходов, что и у неизвестных. Если при этом все обратные связи оказываются корректными, то полученная автоматная схема будет реализовывать некоторый автомат, который обозначается S(ci,., сп).

Автоматным уравнением с п неизвестными называется пара: схема-птаблон S(xi,., хп) и автомат /г, имеющие одинаковые входные и выходные алфавиты. Записывается автоматное уравнение так:

S(xi,. ,хп) = h.

Решением автоматного уравнения с одной неизвестной 8(х\1., хп) = к является такой набор автоматов С1,. ,сп, что схема-шаблон 5 может быть инстанцирована набором ., сп, и автомат 5'(с1,., сп) эквивалентен автомату К.

Числом состояний автоматного уравнения Б{х 1,.,жп) — К назовем произведение числа состояний всех автоматов из схемьт-птаблона 5 и числа состояний автомата К.

Недетерминированным автоматом (НДА) называется следующая пятерка: (А,и, В, р,и°), где:

А - конечный входной алфавит;

В - конечный выходной алфавит;

II - конечное множество состояний НДА; и° С и - множество начальных состояний, и0 может быть пустым. р : и х А 2ихВ, где 2ихВ - множество всех подмножеств множества II х В, р называется функцией перехода .

Как несложно видеть, детерминированный автомат является частным случаем НДА, у которого:

1) Ы = 1;

2) Для всех и е 17 и а Е А выполняется |р(п, а)| = 1.

Пусть НДА N = (А,и,В,р,и°). Графиком НДА N будем называть множество М всех слов (ах, &1)(а2, Ь2) • • • (отг> Ьп) из алфавита А х В, таких что существует такая последовательность состояний НДА N щ, щ,., ип+\. что:

1) щ Е и

2) Для всех г от 1 до п (щ+и &г) € р{щ,

Поскольку автомат является частным случаем НДА, то данное определение определяет язык и для автомата тоже. Причем если слово (а,1,61). (ап,Ьп) входит в язык автомата, то при подаче на вход автомата слова аь а2,., ап на выходе будет слово 61,62,., Ъп.

Будем говорить, что автомат г является редукцией НДА -/V, если язык автомата г является подмножеством языка НДА N.

В Главе 1 исследуются уравнения с одной неизвестной и получены следующие результаты.

Утверждение 1. Пусть автомат является редукцией НДА N и автомат х2 эквивалентен автомату Тогда г2 тоэюе является редукцией НДА N.

НДА N = (A, U, В, р, и0) будем называть выходо-недетерминирован-ным автоматом (ВИДА), если:

1) \и°\ < 1;

2) Для любых щ EU, сьеАтлЬеВ существует не более одного «2 такого, что («2, b) € p(ui,a).

Теорема 1. Существует алгоритм, который получает на вход произвольный ВНДА N и произвольный автомат D и на выходе сообщает, является ли данный автомат D редукцией ВНДА N. Время его работы данного алгоритма линейно зависит от произведения числа переходов в N и В.

Теорема 2. Существует алгоритм, который получает на вход произвольный ВНДА N и на выходе возвращает такой автомат В, что В есть редукция ВНДА N, или сообщает, что такого автомата нет. Время работы данного алгоритма линейно зависит от количества состояний в ВНДА N.

Автоматное уравнение S(x) = h будем называть уравнением с полной информацией, если:

1) в S не используются обратные связи, то есть нет операций 8£ и 9£;

2) множество входов схемы-шаблона S совпадает со множеством входов неизвестной х.

Теорема 3. Для любого уравнения с полной информацией S(x) = h найдется такой ВНДА N, что S(c) = h тогда и только тогда, когда с есть редукция N. Причем количество состояний в N не превосходит количества состояний схемы S{x) = h. Существует алгоритм, который получает на вход произвольное уравнение S(x) = h и возвращает на выходе данный ВНДА. Время работы алгоритма линейно зависит от количества состояний входной схемы.

Автоматное уравнение S(x) = h будем называть уравнением без обратных связей, если в 5 не используются обратные связи, то есть нет операций 8S и 9D.

Теорема 4. Для любого уравнения без обратных связей S(x) = h найдется такой ВНДА N, что S(c) = h тогда и только тогда, когда с есть редукция N. Причем количество состояний в N зависит экспоненциально от количества состояний схемы S(x) = h. Существует алгоритм, который получает на вход произвольное уравнение S(x) = h и возвращает на выходе данный ВНДА.

Будем говорить, что ДА г = (Л, ф, В, ф, ф, вкладывается в НДА N — (А, и, В,р, и0), если существует такое отображение ш : СЦ —» 2е7, что:

1) си(д°) Пи0 0;

2) пусть между двумя состояниями ql,q2 ^ Q есть переход а/Ь, то есть = Ф{<1ъ а) и Ъ — а). Тогда

Ущ € о;((71) Зг¿2 € и;^) такой, что (^2,6) 6 /2(^1, а).

Про отображение ш будем говорить, что оно вкладывает г в N.

Утверждение 2. Пусть автомат отображением и) вложим в НДА N и автомат %2 эквивалентен автомату Тогда г2 тоже вло-о/сим в N.

Теорема 5. Существует алгоритм, который получает на вход произвольный НДА N и произвольный автомат В и на выходе сообщает, вкладывается ли И в N. Время его работы линейно зависит от произведения числа переходов в N и И.

Теорема 6. Существует алгоритм, который получает на вход произвольный НДА N и на выходе возвращает такой автомат И, что И вложим в N, или сообщает, что такого автомата нет. Время работы данного алгоритма линейно зависит от количества состояний в НДА N.

Теорема Т. Для произвольного уравнения 8(х) = /г найдется такой НДА N, что в (с) = Н тогда и только тогда, когда с вкладывается в N. Причем количество состояний в N зависит экспоненциально от количества состояний схемы Б(х) = К. Существует алгоритм, который получает на вход произвольное уравнение 8(х) = /г и возвращает на выходе данный НДА.

В Главе 2 исследуются уравнения с двумя и более неизвестными и получены следующие результаты.

Теорема 8. Не существует алгоритма, который бы для произвольного автоматного уравнения с двумя неизвестными и без обратных связей 3{Х],Х2) = Ь определял бы, имеет оно решение или нет.

Как следствие из предыдущей теоремы можно сформулировать следующее утверждение.

Теорема 9. Не существует алгоритма, который бы для произвольного НДА N — (/1.1 х А2, и, В\ х В2,р,и°) определял, имеет ли он хоть один вложимый в него автомат D, такой что D = D\ х D2, причем D1 € Р{АЪ Bi) и А> € Р(Л2, В2).

Теорема 10. Не существует алгоритма, который для произвольного автоматного уравнения S(x, х) = h определяет, имеет оно решение или нет.

В Главе 3 исследуется решение автоматных уравнений во множестве детерминированных функций и получены следующие результаты.

Теорема 11 .'Детерминированная функция является решением автоматного уравнения S(x) = ho тогда и только тогда, когда она вложима в тот же НДА, в который вкладываются все ограниченно-детерминированные решения уравнения S(x) — Hq (см. теорему 7).

Как следствие из предыдущей теоремы получаем, что у уравнение с одной неизвестной имеет ограниченно-детерминированное решение тогда и только тогда, когда оно имеет детерминированное решение. Но это неверно для случая уравнений с более чем одной неизвестной, что доказывается в следующей теореме.

Теорема 12. Существует уравнение с двумя неизвестными, имеющее детерминированное решение, но не имеющее ограниченно-детерминированного решения.

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

1. Лялин И. В. Решение автоматных уравнений // Тезисы докладов XIII Международной конференции "Проблемы Теоретической Кибернетики". — Казань, 2002. — часть 2 стр. 118.

2. Лялин И. В. О решении автоматных уравнений // Дискретная Математика. — 2004. — Т. 16. вып. 2. — С. 104-116

3. I. V. Lyalin. On solving automaton equations // Discrete Mathematics and Applications. — 2004. — Volume 14, No. 3. — Pp. 287-300.

4. Лялин И. В. Алгоритмическая неразрешимость автоматных уравнений с тремя неизвестными // Тезисы докладов XIV Международной конференции "Проблемы Теоретической Кибернетики". — Пенза. 2005. — С. 91.

5. Лялин И. В. Решение автоматных уравнений // Тезисы VII Международной конференции "Дискретные модели в теории управляющих систем". - Москва, 2006. - С. 96

6. Лялин И. В. Решение автоматных уравнений с одной неизвестной // Интеллектуальные системы. — 2009. — том 12. — С. 271-282

7. Лялин И. В. Решение автоматных уравнений с двумя неизвестными// Интеллектуальные системы. — 2010. — том 13.

8. Лялин И. В. Решение автоматных уравнений // Тезисы конференции "Дискретная математика и её приложения". — Москва, 2010.

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

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

В [3] В.Б. Кудрявцев вводит понятие обобщенной сети, тождественное понятию схемы-шаблона, определенному в данной работе. При этом возникает оператор ш : Р х . х Р —> Р, отображающий набор автоматов в множество автоматов. Далее множества таких операторов используются для определения последователъностной функциональной системы < М,П >. где М С Р, а О, - множество обобщенных сетей. Пользуясь операциями из П. можно из множества автоматов М получать другие автоматы. Главной задачей, рассматриваемой в [3] для последовательностных функциональных систем, является задача о полноте. Можно ли из множества автоматов М с помощью множества операций О. получить все автоматы из Р. Следом возникает задача о выразимости посредством оператора и> одних автоматов через другие. То есть существуют ли такие автоматы ., Р&. что ш{Ръ., Р/.) = Р. где Р - наперед заданный автомат.

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

В [5] и [6] А.К. Григорян решает задачу нахождения неизвестного компонента в автоматных схемах четырех видов. Это очень близко к решению автоматных уравнений для этих схем, только автора интересует не все множество возможных решений, а только существование хотя бьт одного автомата и алгоритм для его нахождения. Такой постановке задачи имеет смысл дать отдельное название (в соответствии с названием, данным А.К. Григоряном).

Задачу нахождения одного решения, или определения отсутствия решения произвольного автоматного уравнения будем называть задачей декомпозиции. Отличие от задачи решения автоматного уравнения заключается в том, что нас не интересует описание всего множества решений, а требуется найти одно любое.

Рис. 9:

Рис. 10:

Рис. 11: Рис. 12:

В [5] и [б] автор приводит полное решение задачи декомпозиции для уравнений четырех видов, изображенных на рис. 9, 10, 11 и 12. Здесь А -фиксированный автомат, X - искомый автомат. Для каждого вида уравнения доказывается эффективный критерий существования решений и приводится алгоритм, который строит одно из решений.

4.3 Структурные автоматные уравнения (А.С. Подколзин, Ш.М. Ушчумлич)

В работе [7] рассматривается задача о решении систем автоматных уравнений, представляющих собой обобщение систем канонических уравнений. Решается задача существования и нахождения решения, а также предлагается алгоритм для перечисления всех возможных решений. Определим эти системы уравнений более подробно.

Пусть X = {хъх2, ■ ■ •}, У = {Уъ У2, .••},£ = • • •} - счетные алфавиты, называемые соответственно алфавитом входных переменных, алфавитом переменных состояния, алфавитом выходных переменных. Пусть а - целое неотрицательное число. Тогда выражения + а),жг(а) назовем входными атомами, выражения + а),у^а) - атомами состояния, выражения Zi(t + а), Zi(a) - выходными атомами. Выражения ., уп), (?г(г>1,., уп) будем называть автоматными термами, если ^г и С, - функции алгебры логики, а у^ - атомы. Выражение = (?г- назовем автоматным уравнением. Система автоматных уравнений есть набор из нескольких автоматных уравнений.

Пусть автомат г имеет в своей канонической записи входы XI,., хт, переменные состояния тд,., уп,. и выходные переменные ., хр. Ее- • ли заданы последовательности £1,. •, £т значений входных переменных Х1,., хт в моменты времени £ = 0,1,2,. то для автомата .г однозначно определяются последовательности значений 771,., Г)п и ., в указанные моменты времени своих переменных состояния у\,., уп и выходных переменных г\Определяемые таким образом наборы последовательностей будем называть поведениями автомата Поведение 7г автомата £ будем называть допустимым для автоматного уравнения Рг = (7г, если значения автоматных термов Ег, Сг в произвольный момент г = 0,1,. поведения тг совпадают друг с другом. Автомат £ является решением системы уравнений Б, если каждое его поведение допустимо каждым уравнением системы.

Как несложно заметить, такие системы автоматных уравнений определяют множества автоматов. Вернее, множества канонических уравнений автоматов, поскольку может оказаться так, что из двух канонических уравнений, определяющих эквивалентные автоматы, одно является решением системы уравнений, а второе нет. Причем автоматы определяются с точки зрения соответствия внутренней структуры неким условиям, определяемым системой уравнений. В отличие от этого те уравнения, которые рассматриваются в данной работе, накладывают ограничения только на внешнее поведение автоматов, игнорируя их внутреннее устройства. Ввиду этого можно уравнения, рассмотренные в [7], называть структурные автоматные уравнения, а те что рассматриваются в данной работе - абстрактные автоматные уравнения. По аналогии со структурными и абстрактными автоматами.

Теперь возникает вопрос о сравнении структурных и абстрактных автоматных уравнениях, о их связи и соотношении. Для начала необходимо провести между ними четкую границу, ясно представлять их принципиальное различие. Абстрактные уравнения накладывают ограничения на поведение автоматов. Два автомата с одинаковым поведением (то есть эквивалентные) всегда или оба будут удовлетворять уравнению, или оба не будут удовлетворять уравнению. Независимо от их внутреннего устройства. Структурные же уравнения ограничивают внутреннее устройство автоматов (и только через это - их поведение). Из двух эквивалентных автоматов, по-разному устроенных, один может удовлетворять структурному уравнению, а второй нет. Абстрактные уравнения задают множества автоматов, а структурные - множества канонических уравнений.

Пусть К - каноническое уравнение со входами х\,., хт, переменными состояния у1,., уп,. и выходными переменными Будем гово

Рис. 13: Сведение структурного уравнения к абстрактному рить, что автомат А со входами хг,. ,хт и выходами ух,.,уп, гх,. ,гр моделирует каноническое уравнение К. если входные и выходные значения для А всегда удовлетворяют каноническому уравнению К.

Завершая сравнение структурных автоматных уравнений и абстрактных, докажем следующее утверждение о сводимости структурных автоматных уравнений к абстрактным.

Утверждение 3. Для любой системы Е структурных автоматных уравнений ^ = 1 < г < п найдется (и может быть эффективно построено) такое автоматное уравнение с полной информацией = /¿0; что все его решения и только они моделируют решения системы Е. Здесь /го - автомат, всегда на выходе выдающий 0.

Доказательство : Пусть Л - максимальное число такое, что в системе Е существует атом вида х+ Л) или Х{(А) или у^Ь + А) или ?/г(Л) или + Л) или 2г(Л).

Схема Б{х) изображена на рисунке 13. Здесь блок реализует все атомы системы уравнений Е, начиная со времени Л. Каждому атому Х{ {Ь + а) соответствует свой выход V в блоке ¿>1, такой что > Л у(Ь) =

Рис. 14: Л + а). Очевидно, как V может быть получен из Х{ с помощью нужного количества задержек. Каждому атому х^а) соответствует свой выход V в блоке ¿>1, такой что V/, > Л г>(£) = Х{(а). Опять же понятно как такой выход получить. Аналогично с атомами вида + ск), У{(а), 4- а) и 2{(а), Таким образом, количество выходов блока есть количество атомов системы П. Все эти выходы соединяются со входами блока , который просто проверяет, что в каждый момент времени, начиная с Л. выполняются все уравнения = и пока это так. выдает на выходе ноль. Сделать это не сложно, т.к. все необходимые для этого атомы поступают на входы блока 52.

Очевидно, что построенное абстрактное уравнение удовлетворяет доказываемому утверждению. ■

Напомним, что в данной работе уравнение с полной информацией решается за линейное время, и множество его решений есть множество редукций некоторого НДА.

4.4 Автоматные уравнения для языков (Н.В. Евтушенко и др.)

В работе [8] - [10] рассматриваются автоматные уравнения следующего вида.

Пусть Ь - язык в алфавите Ах В. Тогда язык, состоящий из всех таких а £ А*, для которых найдется хотя бы одно такое Ь £ В*, что слово (а, Ь) входит в язык Ь, назовем А-проекцией языка Ь. Обозначим этот язык Ь^д.

Пусть имеется схема, изображенная на рис. 14. Схема состоит из двух компонент А и В, которые взаимодействуют, обмениваясь словами друг с другом и с внешней средой. При этом язык первой компоненты Ьд ^ (II х и х V х (Л)*, а второй - Ьв С (12 х и х V х 02)*. Язык компоненты полностью описывает возможные варианты её поведения. Тогда язык, который будет соответствовать всей компоненте на рис. 14, будет

ЬА*ЬВ = (ЬА X 12 X 02 П Ьв X 1Х X 01)Ц1х12х01х02

Язык ЬА • Ьв будем называть синхронной композицией языков ЬА и ЬВ-В [8] рассматриваются следующие уравнения: С I, То есть предполагается, что компонента А - фиксированная, а компонента В - переменная (в уравнении названа X). Вместо компоненты В можно подставлять любую компоненту, так чтобы язык всей схемы был подъязыком языка Ь.

Эти уравнения решаются для разных классов языков, в том числе и для языков, соответствующих недетерминированным автоматам. В последнем случае получается такой результат: по произвольному уравнению строится недетерминированный автомат, такой что все решения данного уравнения являются его редукциями (то есть их язык является подмножеством языка данного недетерминированного автомата). Обратное не верно: если какой-то недетерминированный автомат является редукцией, то он может и не быть решением. Таким образом, для произвольного уравнения нельзя сказать, имеет ли оно хотя бы одно решение или нет.