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

Саратовский ГосударстпешшЛ Униперснтет им П.Г.Чсрнышсоского Мехаиико-Математический факультет

Па пранах рукописи УДК. 519.95

ХЛЗБУН иссл влдих

ОБ УСЛОВИЯХ ПОЛНОТ!,! II ПЬП'ЛЗИМОСГИ I! ТОЧНОЙ /VII111.14-,

АВТОМАТОВ

01.01.09 -Матемагическая Кибернетика

Л П Т О Р П <1> 1:. Г Л Т

днссертиш на соискание ученой сюпемн кандидата физнко-матемашческих нлук

Сарлов

Работа выполнена на кафедре млк'машческоп теории интеллектуальных систем механики-м л к-млшчсско! о

факультета Московского юсударствсшюго университета им.М.В. Ломоносова.

Научные академик ЛТП 1'Ф, профессор

руковод ители: В. Б. К.уд ри в цев

с.н.с., к.ф.-м.Н. Д.Н.ЬаОип

Официальные профессор, д.т.н. В.А.Твердохлебов

оппоненты: доцент, к.ф.-м.н С.Л.Ботмолов

Ведущая Московский энсргешческии

организация: институт

Защита диссертации состоится

в /^часов "ЪО минут на заседании специализированною совета К063.74.04 при Саратовском государственном университете им. II.Г.Чернышевского в аудитории

[410!

Адрес 410601 Астраханская 83, Саратовский государственник университет, механико-математический факультет. С диссертацией можно ознакомиться в библиотеке Саратовского государственного университета.

Автореферат разослан

-199&.

Ученый секретарь специализированного совета К.063.74.04

■4

к.ф.-м.н., доцент V П.Ф.Недорезов

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

Цель работы

1. Ввести новое понятие точной алгебры автоматов и изучить ее свойства

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

3. Найти условия базируемости подалгебр точной алгебры автоматов.

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

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

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

Структура диссертации. Диссертация состоит из введения, двух глав, разбитых на параграфы, и списка литературы, содержащего 9 названий.

Содержание диссертации. Но введении дан краткий обзор результатов, полученных диссертантом.

В главе I изучаются задачи полноты и выразимосш для всей т-алгебры. В §1 вводятся основные понятия и ставятся решаемые далее задачи. Конечным автоматом называется набор

.-1 = (,{?,-С2',ф, |/Л<7о)> где ¿2 = {0,1}, Е2т входной алфавит,

Е2 выходной алфавит, <2 множество состояний, <р:(2хЕ2т О функция переходов, цг. (7 х Е2' Бг выходная функция, q0 начальное состояние. Функции (р и у естественным образом

доопределяются на множество 0>:(Е2т) , где (ТУ) множество слов в алфавите Е2 . <р^,аа) = <р(<р(<7,а),а),

у(<7,сед)= у/(р{4,а),а), где qeQ, а$Е2п, ае(ьу:), а также определяется функция б >: (Е™) ->(£/) , которая для

равна

у(ЧА-ап) = ¥{<!Л}ч>(<р{<1Л)>а1)>"-Ч'{<р((1Л-~<1„1),ап). Отображение

V'гд'[Е2") ->(Е2) , где = называется автоматной

функцией, порожденной автоматом Л.

Множество всех автоматов обозначается через 1\ множество автоматов с одним состоянием чероз 1'и, мпожеемю апюмаюп из класса М, имеющих п состояний - через Л/0, множество натуральных чисел - через N, проептх чисел - через /'. Следуя [3], вводятся операции, коюрие позволяют нолуча1Ь новые автоматы из заданных автоматов. Перечислим эш операции: (-\ - подстановка выхода одного автомат на вход другого, (А -операция обратной связи, 0} - псрескшовка входив автмап, 04 - перестановка выходов, 05 - отождествление входов, Оь отбрасывание фиктивного входа, 6>7 - доОаачение фикшшшю входа, Ог - отбрасывание выхода, 09 - раздваивание выхода. Обычно исследователя ншерсеует не ашом;и, а порождаемая им автоматная функция. Факшчески эю означает возможность использования, кроме перечисленных, еше двух операций над автоматами, оставляющих неизменной ею авюмашую функцию. Это операции 1>10 - ошрлеывамие состояний, недостижимых из начальною и - отждесыиепис

неотличимых состояний. Паря 1'а = {1',{С\,Ог,...Оп}) называется функциональной спсюмой авшмашнх функций. Она обладает следующими главными снойстлми 11][-'114).

Теорема I. Ра ямяски копечнипорождепнои.

Следствие I. Любая полная в /', спсюма содержит конечный базис.

Следствие II. Всякий замкн.мый класс и содержиюя в преднолном классе.

Теорема Н. Множество иредиолнпх классов в 1\ имеет мишноси. континуума.

Теорема III. Проблема полно im конечных ciicic.m в 7', алюрцтмически неразрешима.

Точной алгеброй автоматов называется пара (Р,{(.\ ЛК ).

точным замыканием (т-замыкание.м) - замыкание ошосшельно операций С\,..09. Т-ззмыкание мпожеиьа М с i' обозначается через (Л/). Для замыкания ( } естественным образом вводи!си понятия т-полноты, т-замкнугою класса, т-нреднолного класса, т-базиса и т-шразимости.

Функциональные системы {Ри,{(\,...0^)) и [1'ц совпадают и могут быть отождествлены с алтеОрои жилки 1\, и которой известны [4j преднолные классы: 7'0 - класс функций, сохраняющих, нуль, 1\ - класс функций, сохраняющих единицу, L - класс линейных функций, S - класс самодвойственных функций, АГу - класс монотонных функций. Сохраним эти обозначении для т-предиолных классов в Рп.

Для т-алгебртл исследуются следующие основные задачи:

Задача о т-базисах Она заключается is том, чтобы для т-замкнутого класса М описать т-базисы n М.

Задача о т-полиоте. Она заключается п описании гсех таких множеств М' с М, что (АР) с М.

Задача о т-гыразимости. Она состоит и выяснении тою, существуй-ли алгоритм проверки свойства А е ({/(¡,...4,}) для произвольных автоматов А,/^,...А„ <=Р.

Множество М' с Р называется Л^-т-унивсрсальным, если (И' и Рхг) э 1*п) при всех /1 е А',' А" с N.

Под задачей Л^-т-универсалыюсти для конечною N' понимается установление алгоритм,!, проверяющею N'-i-универсальность произвольного конечною множества автоматов или отсутствие такового.

13 §2 главы 1 решается задача о т-базисах. 1'accMaiривлется ciicicNia специальных автоматов В = {/í,,7/j,,...}, !де при н Ф 1

Вп={Е2\{1,2,-п},Е2\1Ра,х!'п1\), и у„(У» = 1>...1..Д

I...J....H

" при аеЕ,\ j е {1,2,... л}. 1\ е Рп - но

1..1...П

автомат, отождествленный с универсальной булевой функцией. Через Лр обозначается множество всех ашомакш lin из Л

таких, что п е 1\ или п - 1. Имеет место Теорема 1. Множество Pr¡ яатяется т-базнсом в Л.

Через Un обозначается множество всех {/i}-i-универсальных

автоматов, через £/-множест.о Множество K<zU, такое

л-1

что А'(п> = 0 при н íc Рг и jA'<r,1j = l при nel'r, называется регулярным. Через Л{М) обозначается множество всех подмножеств М' с М, являющихся peíулярными. Для Л/ ст Р,., (М) = Рц через £П{М) обозначается множество всех подмножеств М'с:М, таких чю М' является Оазисом в ]';,, для МсЛ, (М)-Л, через Б(М) обозначается множество всех подмножеств М' с М, которые являклея базисами в Р. Имеет место

Теорема 2. Пели М С 1' и (М)~ /', ю имей мест

1 )ЩМ)= \JiDuE]

И

2) Б{М)Ф0.

Слепстинс. Белка« конечная сисюма аиомаюв не является т-полной.

В §3 главы 1 решается задача о /м-унпвереалышегн, вмодшея понятие а - А-канонической схемы, при иеРц, ае1'\]'п и доказывается

Лемма 8. Если А е Р и схема ^ над {А}^1'п содержи! точно один раз автомат Л, то автомат С, реализованный Л', может Сыть при некотором ае Р;{ реализован а - /) -канонической схсмой. Имеет место

Теорема 3. Свойство л-т-унивсрсалыюеш авю.мата апориглшчески разрешимо.

Б §4 изучаются т-предполние классы и даечеи их полное описание. В терминах т-иредполнмх классов получас 1сн кршерий т-полпоты. Пусть Д, = ]' \1!„. Имеет мест

Лемма 9. Если р е 1'п то /?р-т-предполный класс. Вводятся обозначения Р~Р\РИ, Н1Ъ = 1'и'1[„ =/>и7|, Я, 11ь -- Р и Ь, ПИ/ = 1> и и{. Имеет место

Лемма__П. Множеств , /\;, являкиси т-

11рел г юл н ы м и (С! ас сам и.

11 ус [ ь I = { /:г>, ДГ|, ЛИ/, . Я, . А':. А;..../"...../р е /:}. Имеет место

Теорема 4. Множество т-предполных классов в Г совпадает с X. "1еоремз 5. Множество .автоматов М 1-полно пп да и только тогда, когда для любого {2 из £ гыполнено М с О.

Следствие. Если М с Р и = М, го или М = /', или дли некоторого (> выполнено М с{_>. Теорема 6 Мощность множества т-замкнушх классов р.т-на котинууму.

13 §5 главы 1 решается задача о т-ппрази.мос ш. Лводшся понятие а- {Д,....-!,.} - каноническом схемы п дока:;ывае1ся

Лемма 12. Если А е (Рп {.....•!.. }*), то найдется каноническая

схема, реализующая А. Теорема 7. Свойство т-пырлзимосш алюрнгмически ра тешимо.

Во второй главе изучается т-иолнога и т-выразимость в подклассах автоматов. Задача о т-б.гзисах и о т-милпо'.е в ч-замкнуюм классе М г: /', содержащем, г,се нстшшостнмс функции, решается аналогично случаю всей т-алк-бры /'. Удае1ся описать т-предполнпс классы в М и в терминах I-предполных классов сформулировать кршерий т-полпечы. I! §1 главы 2 решается задача о т-базисах для т-замкнугых классов, содержащих 1'ц, вводится понятие окресынош автомата А е ЛГЯ) как множества Ом (А) - {{.-!} [)01 П )>П А/'"' через обозначается множество [В еСЛ/(.-1) [Л е 0Я(В)}.

Имеет место

Лемма 13. Решетка по включению \Ог(Л) / Л е 1>!"'} окрестностей автоматов с п состояниями конечна. Пусть W и V подмножества авюмаюв, тогда множество IV называется V- регулярным, если множество [0{А) / А е IK'"1} в точности состоит из максимальных по включению элеменюв множества [О(Л) / Ле.У{п>\. Множество всех Г- регулярных

множеств обозначается через Лвюмат Ле(М'),

'М'^Рц, АеМ\Тп называется разложимым по М', если найдутся автоматы е М', такие что /1 е ({/(],... А}),

причем число состояний каждою из авюмаюв Л, ст¡xj¡о меньше числа состояний автомата А. Множество авюмаюв А е М', не разложимых но М'. обозначается через Л(Л/'). Мере) Ц{М',М) обозначается множество т-базисов в М, являющихся подмножествами М'. Имеет место Тсорсмт S. Пусть МсР, (М) = М, Мз1'ц. М' S М " (Л/') с М, тогда

1) £(М',И)= (Jí^^l

ГъГр'М-пГи) £«к4 (Л(')1

И

2) £{М',М)*0.

И §2 главы 2 вводится понятие базируемого т-замкнуюю класса как класса, имеющею т-базис. Примерами таких классов служат т-замкнутые классы, содержащие все истинностные функции и конечнопорокденные т-замкнуыле классы. Приводится пример не базируемою класса и доказываемся теорема 9, по которой свойства "т-замкнупти класс имеем базис" и "т-замкнушй класс имеет т-по.тую сисчему, m которой т-базис не выделяется" взаимно исключаю! друг друга.

В §3 главы 2 решается задача о т-полноге в базируемых т-замкн^тых классах. Пусть М ci\ (Л/) = М, М' = М'п и Л/ - т-

базис п Л/, и М'ц si//, М с Р\РИ. |Л/| называйся порядком т-базиса Л/'. Пусть М, = Л/ \ V,,,(,),), А, е Л/, а М1 = (Л/ \ Рц) и Мц1, где Л/;/ нредиолный класс в Л/п/'„. Через 1(Л/) обозначается множество т-предполш-х в Л/ классов. Имеет место Теорема 10. Пусть Л/с Р базируемый т-замкпуптй класс, то!ла

Кл/) = и{л/(.}ь'и{л//}-■ 1

Следствие 1. В конечноиорожденном т-замкнуюм классе конечное число т-предполных классов.

Следствие 2. Множество автоматов Л/ т-нолно в базируемом т-замклутом классе М тогда и только тогда, когда дли любою Q е Ъ{М) выполнено Л/

Следствие 3. Пусть МсР базируемый т-замкнугый класс, Л/с Л/, тогда или ^ЛУ^ = Л/, или для пекоюрою Q<=1.(M) выполнено Я с Q.

(.'л ene i ниц 4. Порядки Оазисов и копечпопирождеппом т-

'-ClMKIiyJüM КЛЛССС СОПНЛД.ТКЧ .

Оказывается, что свойство конечнопорожденности не наследуется т-предполными классами. Имеет место

Теорема 11. Существует конечнопорожденный т-замкнутый класс, содержащий бесконечнопорожденный т-предполный класс.

В §4 главы 2 исследуются т-универсальные автоматы.Имеет место

Лемма 14. Пусть A eU, тогдз для любых двух его состояний q¡ и q2 найдется входная буква, переводящая автомат А из состояния <7! в состояние q2.

Оказывается, что каждый автомат схемы, реализующей т-универсальный автомат также обязан бить т-универсальным.

Имеет место

Лемма 15. Пусть AsU и а,-{.■(,.....•!,}- каноническая схема

реализует А, тогда .-1, е Í/ при всех г = 1,2,.../:.

Лемма 16. Если AzU. и имеет ?п входов и / выходов, то 2"1 > п и 21 > п.

Через Рп> обозначается множество всех автоматов с т входами, а через Pü) -ti выходами. Имеет .место

Теорема 12. Для любого т е А выполнено ^ ф Р и ^ Р-

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

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

Теорема 13. Пели нешбыточиый т-универсальный автомат имеет т входов, / выходов и п состояний, то ] 1о^п[< т < 2"' и ]к^л[</< п2.

Следствие. Множество неизбыточннх т-универсальных автоматов с п состояниями конечно.

В §5 главы 2 рассматривается задача т-выразимости множества всех автоматов с п состояниями такой системой автоматов, что никакая ее собственная подсистема этим свойством не обладает. Эта система называется л-т-баэисом.

Разложение натурального числа п на (не обязательно простые) множители п = ]\р2-.-Рк, такое что для любою / , 1 < / < А, п не иредставимо в виде Р2'■■■ ■■ ■ Гк', си...ск<=1V,

называется неприводимым представлением числа п. Через Ф(п) обозначается множество длин неприводимых представлений л. Имеют место

Теорема 14. Для любых п е Лт, у е {1,2,3,4} и КеФ(п)

существует и-т-базис длины к + у. Теорема 15. Пусть М л-т-базис, тогда:

1) если М п Рп с! или М п 1), с М [, то М бесконечен;

2) если М г\РП ссили М п Рп т М[, то М конечен. Основные результаты работы содержатся в статье

Хазбун И.В. , Выразимость и полнота в точной алгебре автоматов (в печати ).

I

I г

Автор выражает благодарность своим научным руководителям: I академику В.Б.Кудрявцеву и ст.н.с Д.Н.Бабину за научное руководство.