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

РАТОВСКИЙ ОРДЕНА ТРУДОВОГО КРАСНОГО ЗНАКЕНИ ПОСУД'РСГШЕННЫЯ УНИВЕРСИТЕТ ИМ. И. Г .ЧШ(ЬЭЕВС(СОГС

, .На правах рукописи

Иангугоеза Ирина Паз лов на -

шрфизмы по-стабильны:! тожРАнтаосгям. сятагощю .автоматов

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

Автореферат диссертации на соискание ученой степени кандидата 4«31Ко-гатематачосЮ1Х нагл

Саратов - 1992

Диссертационная работа выполнь.ш в Саратовском государствен!) университете им. Н.Г.Чернышевского.

Научный рук водитель доктор технических наук, профессор,

,академик АЕН РФ А.И.Богомолов.

Стфиичальние .„лпоненты - доктор тх .ничеоких наук, профессор В.А.Твердоклебов,

кандашат 4изико-мате..этических наук, доцент А. А.Ситник.

Ведуьзя организация - Яоскоь <шй государственный университет т М. в./юйонооова.

_Л932 Г. в Чг^М

ЭаЦИТР СОСТОИТСЯ * ** /1992 г. в '— чг-?'-'мин.

на згоедании спецплиэированного Совета к 063.74.04 саратовског государотаак.ого униввроятета им. Н.Г.Чарнызевского по адресу: 410071, г.Саратов, ул.Азтраханск д.83.

С диссертаций можно ознакомиться в библиотека Саратовского государственного университета, ю» Н.Г.Черныиерского.

1-Й

Автореферат разослан "_!_" ^"'УУуаяг г.

Ученый секретарь ; специализированного Совета кандидат физ ико-кателятичвоких ^^ __ наук . - V.-',- П.Ф.Неяорезо!

PO.CO^XV-v* | бтдп ] . БИБЛИОТЕКА —;

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТУ. . . • '

Вусдэвиях. широкого прииекчнкя дискретных устройств в производстве и управления^ повивается важность и ответственность возложенных на них Функций- Какодедствие этого, возрастает роль Функционального контроля. В целом щгбледа • контроля посвящались работы П.П.ПарюмеНко, Е.и.Согожмяна, А.а.Богомолова, S.A.Твврдохлебоаа, Д.В.Сперанского, и.с.Грунс-кого и других. Методы, предложение этики авторами, в значительной степени определяются выбранной »атеаатеческой "и дель».. а такха видом контроля. "''.'•-." ,.••'{ . - •

Среди катодов проверки дравильноот работ« диокре-того устройства, в которых матекйтаческой моделью является конечна аз-томат, бол1, 'юй интерес" представляют те из; них, что оонованы на иопольз овании отабндьник • отношенийКотродирутеий автомат и этъд случае, как правило, проще исходного, но 'сохраняет его оо-нов!Ше черта. е, В: Данилов. Н,8.^Сояйсоз к ¿.П-Подкопаев ; предложили.» качестве оредотва. проверки гойошрФкШ образ' исходного автомата'. S.K.Юорноувенко отроит -шНтт»^руший ас-,эмат о помощь» некоторого отношения толерантноота'нз множестве выходных сигналов автомата*. . :..." ' ' ' .' - •. ■

'Данилой П. В. ,Колесоо Н.В. .Под*опаиа Б. П. Алгебраическая ' модель аппаратного контроля автоматов //Аьтоыатик» . и тале'»ханика. -1973. -»в. -с. 118-123. '' . ■.•':■•.•'.

гКорноуя>енко Е. К. Обобщенная аадлча проверки правильности функционирования конечного автомата //Техническая кибернетика. -1Q77. -» 3. -C.109-U5. . ' V

<

Интерес к "аким штодам усиливается благодаря возможности ясяодьэг "аТь их для организации встроенного контроля, которая в ус.»-вида высокого урс ;к.< интеграции ^хничаских средств становятся наибс.йе зффзктивнш» видом проверки. Однако, поскольку каждой из штодоа ориентирован на ограниченную область применения гсошчио-автшатаэд коке лей, то актуальной шляется задача даль Рйшегг- развитая .аппарата стаойльньк отаонакий . и использования его для функционального контроля. Исследования« по стабильный • о~ноаениям на автоматах посэдани труды Фарра3 и Ц.Е.дадидзе*, р 'Д свойств установлен в работах В.В.Печенкина* и П.М.Хруоталева". •

Другое особенностью, '.. зат^уднявдей применение конечно-авто-мааад шдехйк. язккгтся их Йодьидя размерность. Структурная теория автоматов позволяет получать компактные модели устройств, устан .вливая нужную, разкзрностъ котонект. . Среди публикаций важнее; иасто заглмаот работе В.Н.Глушшза, А.й.Богомолова, &. Б.Кудрявцева. В.А.Твердохлобоэа. . Использование структурного

err- E.H. .lattice- Properties of Sequential Machines //J.Assoc. Comput.Math. -1963. -Vol.ie '-: M •"!.' -p.343-365.. '

"лидяхэв Ц. E. О ггалорфионах лв тома tos , //Труды ВЦ АН Груз. ССР 1973. -Т. 1Э. '118-131: . - '. .'•'•'•

5Почем* нн Б. В.Гомоморфизмы автоматов //Саратов, ISSiS. ДвЛ 'и

вичити я esea-ss. р» иат.. 4а i vo, -£7с.

0Хрустлле» П.К. Избиения и покрытия со с-аойстеом подстановки крнечных дйтомятгх //Нвтохы » системы техгичаскоа лиагностии' -Саратов, löSl^: .'-Вьет, в, -е. 07-107.

'Ита в качестве математической модели дискретного устройства ур"4 необходимость- ориентации на эту модель известных методов родя.

"¿'ь.Р-З^ТУ- 1 > Разработка метода псороек.^ для 'аданкого ктурного автодата другого автошта. лоэблеаие которого ано с поведением , входного, на основе иепольэ .взния о'ло-Я отабильной толерантности.

) . Теоретической обоснованно возможности и лол'.зозашя энного метода для контроля автоматов.

зучная_нозюна_гезхльтатоз^ Предложи. новий «тод построения бита, сохраняющего существенные черты поваязннь походного, основе использования отношений стабильной толерантности, зана возможность применения "етода для контроля абстрактных руктурных автоматов в'процессе Функционирования, существлено дальнейшее исследование, стабнлышх отношений и ■ражений, связанных с ними, на абстрактных гзтоматах. Резуль-! исследований распространены. на структурное автомат«. ШШчес^о_Т2ор§1Уческ.2Я_ц§ннодть,. Полученные результата .ставляют собой теоретическое обобщенно аналогичны* рззуяь-«, касаваихоя построения гогедторфаздаз азтокитоз ко кочгру-и*м. Поэто?<у а перспективе они когут кайти прк'-'.енеимэ •.'лдальэуктся гошшрйош и тзодарфкьа образа: в Делмейсрх !нух ;?сс-ледоэа.чнях ш теорчи зОстроэтнкх н-(щукхуриьк я, а учебном процессе, при оргзкизаггч контроля дкскг^тных юйстз с эдаканткги встроенного Функционального контроля.

По теш ддооергадо* опубликовано '/

работ. По ма"7"риалам работа были сделаны сообщения и доклады . иежврсгчсой школа-семинар® "йетоды к системы технической д) шгики" /г.Саратов, 27 июня 19°* г./, на п Всесок совещании-с винаре "Метода синтеза и планирования отру» крушсшсатабнш сий'гем"/. г.Саратов.26-28 июня 1986 г./, на Всесоюзной совещании по технической диагностике и опсаз< той'пвооти п.Саратов, 28-£8 ш» 1890г./.

Структура диссертационной работы. Диссертация состоит введения, "-рех/глав, заключения и списка литературы <42 найме ванйя). Общий с'ъем диссертации -98 страниц машинописного тек ^дераа^е ВД^Я^ЦИонноа работа. Во введении дан крат обзор - рабо^ гк> Тейатакй. диссертации, перечислены основ

. а также представлен

данятйй» нсйолйуекьа в диссерггации,

, Пгва 1 ; оодеркит"парагркафа и посвящена раз рабе прятлгюв построб'. 'Я По отабильной толерантности на множес состояния аь»омата'другого автанита. поведение которого связ о поведение«» исходного. Исследование, проводится дг конеч авто«атов без уч-зтаих структуры. : ,

В.п.1.1. . приводяггся р8зульт"ш' исследований ш 'стабиль отаошнида в мта^^ -касающиеся стабиль

толерантнос-теЯ. представлениках обобщение аналогичных резу татовш стабильный зетивалайтностям. , : ' . ; , • '. ■.. . В тексте диссертации под автоматом понимается автомат мили ОпрерЁлзние* Г. у&у-у - ;на /',. «новеете э автом

а»<5л. называется стабильным, если :■■

«

<v»4,»a« э) (vx 6 x) (<»,»*,> * m -* »и)«в<» »к>> «я).

id.гчг рассматриваются стабилью» отношение эквивалентности ^руэнции) и тодерантностч. под толерантность» понимается лексивное и симметричное отношение .на раоока кркеаегш кес-тве.

з эквивалентностью однозначно связано разбиение кнохйотаа. . bJ, обладающее тем свойство«, что Функция переходов под

зтвиен любого входного сигнала переводят все элэийнты блока биения целиком в другой блок.

Аналогичным образом о толерантаоотш г на ккогеотве ^вяэыза-я покрытие'. - ,''■'..• . -

Множество lss называется предклассом в <в,т>, » любые два его элемента^» и т. толоранхнн. eflt5§Ha§_i.i.2¿ рожество a s ? называется классом ерзптноети в <з,т>, если.а есть какоимаяышй предклзео. зделение^Ч/ Совокупность вт- {Ч»9*'..классов в

отренстеё толерантности <э,т>'называется С5азисом. если

для всякой толерантной, пары (в,ti существует класо вк,

ержасмй оба этих элемента; : '

удаление из вт хотя Оы одного.'класса приводит к потере этого

йатва. ■.

Нетрудно установить, что множество стабильных толер&атностей ошта а образует решетку относительно теоретико-множественных раций пересечения и объединения. Эта решетка обозначается . Решетка TsA является подрешэткой решетки всех толерзнт-ч, тей на множестве з.'

• - е -

4- - ■

Предлагает я процедура нахождения стабильных толерантнс автоиатг й, аналогичная известной процедуре поиска кокгруэя йет . д состоит в посч^нии базисного »тожества 2-торожде тожрантаоо.ей тв'а, а затеи комбинации элементов этого жастаа о пошдао опёраида. объединения. ОЩШШШё-Ц?;. Толерантность г ' на множестве е называ 2-хк,^-аден,'-)й и обозначается тв » • онз яал?

наи"еньвей стабильной толерантностью, содержащей некот Ш-леред вшранную неупорядоченну*. пару ** »1»вав Е 'Лемма '. .1. Всякая от сильная толерантность автомата а может получена г множества 2-порожденных толерантноотэй о пом операции обьепиненил» т.е.

' -г " и { ГВ 1 > .«. т }■ ■ - . а' х '

Процедура построения шюжества т»а состоит в следующем. . 1.Согласно опреде"••ни» 1.3 для какной пары «,»"»,« з х в стрс £-порождениел толерантность. Совокупность як образует мноке Те*а » г* тк» Полагаем >«=2.

2.Строится множество стабильных толерантноетсй следушего ур . т»*а - .^ с пом', м циклической процедуры ,

3.Если \>1, то '-и перейти к п.г. в противном случае -п

4.¡Сснец. " ''

".■ П. 1.2 посвящен.непосредственно изложению погода постро ' для конечного'автомага и ; его стабильной' толерантности но

«

¡мата и связанных с ним отображений. Этот штод обобщает юг'<чные результаты для кокгруэнцкй и годаиорФизмоэ ■ ' ъ т - стабильная толерантность/ автомата' й-«з,к,у,<5,х}, tsa. По заданной стабильной толерантности • строите., отноше-р<п и отношение *<т,£> по т -и ьиданноау отношению ¡рантаости р иа .х с' помощью Формул:

>0 е р( г) <—»

< Va,, s,e S) ( <«, ,а, ) в т —» < Л<», ,X ), Л< sx ,' > а т).

k l k l Ic i' > J f

"> S *<T,p> «-1

<3(в, ,в,в r) (3<M. .x.) - « pHy » . ,*-> ii y'» Ms,,»)).

V " i , * i ^ i

îyc-Tb зг. и d^ - произволение базисы пространств ¡рантностей <з,г>,<х,Р> и <y,*v соответственно. Предлагается 1уюдая процедура построения, автската по заданной тройке ^рантностей. и базисам вг» £ в1 J , с^- £ Cjj н о^» | Dk|.

вводятся обозначения: .

П { в. i » « sj, хр. п ( с. i и « cj, л { 0k ! у « dk). Через • в | т или з* обозначается .кногеатао блоков покрытия вт и зсевозможньж непуста* пересечений. Аналогично или sr

жи и их всевозможные непустое пересечения из ср, vj^ или v эки и их всевозможные непустые пересечения из о^. рассматривается три отображения:

«>; s - з)г , c;u)»5ri

■ * х1р < VK>'V

y у| , 9' (у)»у ; * 'т ' X 7 7х'

Определякггся Функции ¡' к*';

¿•^Ir* *»„- V» 10,0) - n (в^ (¿(».»y -({«<».>•>}.«,

- ■ • x«G »e<

X'» elrK.K| * vl^- , v(fl,B) - ,

где через о и s обозначены элементу множеств si и ) соответственно. .... ,, •

Поскольку элементами ююжеств 31 . и vl являй

т Р , ЗС -

подк-гжестга множеств 5,х„ и v соответственно, то на s|r , *\f оущэстаует частичный порядок по.включению. Рассматривается автомат a-(SI ^ j„»v|^..«5' i. Процедура <

' - . * г • X ,

построения напс мнает процедуру Факторизации по конгруэнция« совпадает « ней. есда толерантности .являются эквивалентности Она называется кйазйфает^рвдоцяей,, а автомат а\ -кеазифает -а^гоштом автомата а по стабильной толерантности г, г « т« Следующая теорема описывает условия корректности процеду квазифакторизации, . тот случай, когда при определен

Функций.и ^.J/tnqxecrao. :'.ий1.. {>»<»>>|>}вва

.. Y.A.'j; 'Л.'- '■ ;';.''-- . . меЗ

покрывается и^ликом ни одам», блоком осютеетотвующего покрытия.

Теорема 1 .1гродадура' кеазиФакторизйции для автома

А»(9рХ,уа,>,оо задзкньи толерантностяи г.^,J и произ,,ольн

их базисам на инсяевтва* «„ * и у соответственно определя

автомат, а- тогда и только тогда, когда т« т»а, р s р<т>, J

; Определение 1гэ Автомат a*!s,k,y»£,*> будем называть упор доченным, если каждое., из множеств s,x,v частично упорядочено. . Примером упорядоченного автоиатз может-служить квазифактор

'.автомат. ' . . .'•":.' ' \

Пусть дан упорядочен®® аэтозит з . .г Упошмоченньй гэтсдат■■ . з»<о „х.у, ,<5

Л Л А Л А л! 15 35 Э В

юзем изомор$шм авточату -вода; , судестаует. тройеа зза-¡о однозначных оюрьектквжх отображений где

з в., V '¡V * V., что

Л Щ ' Л <7> Л И ,

0<\л<я,х>)»Хв<»<;»),у.<!!))

I дахЗых « аз, I б к, кручен шздое.кз отображений <, у и о гь мзоаор4«за соотвэтстзуящих ушрадочеиша иножаста.

Пусть . задай .аатомат- а-о.х.у.л-м . >р°доченнай автомат нмозем толератыда • образоя

¡гагата я, есл» он изоморфан некоторое квазифактор^аэтомату а* поката а . ' '

Найдена необходимые и достаточный условия,- при котораг вторая упорядоченный автскат.а ярляется толарйН'ыым образом ¡анного автомата А. (Теорзма 1.4).

^деление 1,12-. Пусть <г>' ,1«' ,о-ь - отображения, определяешь в >цессе квази^кторивиции. автомата А э квазифактор -ав-омат йч ч<,о) - изоморфизм й' на некоторый толерантный образ а. Тогда )Яку отображений <г>,V,&>•<*>"!>' ) назовем юрфизмой по

¡Сильной толерантности автомата л 9 автомат а.

Пусть - горЗизи по стабильной толерантности

томата а в автомат'а-,, тогда для любых »•« з, х в*

Показано, что для произвольного автомата.а Функции переходов

и выходов err толерантного образа изотонии (Лемма l.S).

На ол,юаании теорем 1.1 предлагается процедура постро все-' толерантных о^х^оз автомат* аналогичная поотро гошшрф<!й образов. Она заключается в перебор его отабил тол^нтаостей и "йлерантноотей на х и v, удовлетворя теореме 1.1.

ьример построения то ^ рентного образа для автома 3-» оостоянияш, не имеицего нетривиальных конгруэнций (прос автомата). ' -•'■•-.'

.®В§в§31!Ш_1й1.1ь Пусть; задан автомат ft-<s,x,v,tf , \> упорядоченный ' автомат . a»<I,x,y,6,m. тройку отобрзхе! <ргде и> аз—э,у „'ix-^x,. в. iy--.v, назовем г-морФи: ав.очата А в ¿атомат а, ¿о ли для лухЗых в,« s, м « х . 7 s ?<><»>,йк>),

. «1Ч(<,»П £ >(*><*) >vbi и. . ,

Шож.зтео образов зтомата ft при p-иорфизке будем обоз на'

рМог й. :':.,,]■■''.'- ' .

Понятие . р-иорФизма - является естественным обобще! гомоморфизма авчоматоз. Показано.; что.морфизм по . толерзнтн< также является .частным ейдом.р-морФизш (Теорема' 1.4). поскольку морФизм ш толерантности определяется конструктивна он может использоваться всякий раз, -когда возникнет неос димостьпостроенияр-мор<{изма для заданного автомзта.

В. п. 1.3 дано теоретическое обоснование возможности испс зования р-»ор4«эма для контроля конечных автонатов в. проц« Функционирования <террф«ы 1:5 и 1.6). Приведен при»

иллюстрирующий полученнш результаты.

В главе 2 приведены результаты, касающиеся способа получ ния гомоморфных образов композиции автоматов. 8 п.2.' композиции автоматов предлагается описывать с поветью очетаой системы частт :но определенных операций.

множеством с понимается множество всех

г» г>

систем пяти объектов с - о, рх, ^у ,б,х>. где п,т

натура пьные числч. з,х>.....хг,>у,> ••• • произвольные, конечные -

.множества, причем х, и у содержат пустой элемент ГГ".

г» » - г» л

а <5 хрх.» 3, X 13 ><ПУ "'ГТУ- - ОТОбражеНИЯ.

Полагаем, что у каждого элемента с « с есть г> входных и п выходных каналов и узлов. На . .ожестве с определяется система операци:! г, которая содержит одну бинарную операии» д параллел'ьного соединения элементов и очетнуп систему частично определенных унзриа -операций £ где - опе^иия

отождествления 1-ого выходного и>-ого входного узлов, операция , представлена в дзу>- . видах: - отождествление без

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

Каждый элемент множества с называется автоматом со структур-м входом и выходом. Вводится понятие терма в частичной алгебре <с,Р). под термом понимается любой символ 'с. . обозначающий элемент множества с, а также любая композиция вида ^т или 9<Т4,та>, где т.т^т, - термы, 1=1,2. Под. структурным автоматом понимается автомат, представленный . в виде композиции других

автоматов и описываемый термом п^,...,^), в котором все

элементарные лж рации определены для набора <с1.....

автоматов со структурными входом и выходом. Через нот а обозначается множество воех гомоморфных образов автомата а без учета структуры и воспринимаемого как зботтйктаый автомат.

С помощь» оистеш операций р, введенной в п.г. 1, далее в п.2.г показызаетая. что некоторое подмножество множества гомоморфных образоз отружтдаого'автомата, соответствующего данной кокгоси-ции„ ионно получать как аналогичную композиции гомоморфных' образов кошонаткьк автоматов, если выполнены определенные условия.

Опдеделение 2.3. Пуоть задан автомат а«<5, п х , ц у ,о,к>.

, ' . ■..•... ..1 ' ¡-г 1

Я о .

Автомь-' в««(8, л г., л Р.,/,») будем называть структурным

1-» * Л»« '

. гомоморфным образе« автомета А, если пА- п, тя= га и сущ таувт гоаоаюрФмэц <*>,*,»> автомата й на автомат в, такой,,

чяр а,, у <■ а ^ , где г., 1«=!7п ,

в - а &. , ■.'■■' где - « IV. Р. , . .¡-1,п>.

По Зпретяению и« о

' 'Л- • т

если '<*;...* > «п* . Аналогично определяется & »¿е..

Гомоморфизм (*>,»»,©) в это» случае называется структурным

гомомор$дамо«. • -

Определение 2.4.Пусть задан структурный автомат а«тл<с*,...,с*>.

Автомат в»т....с*> называется . структурным гомоморфным . ™ * * ^

образом автомата а, если 1) в « нот а, 2)та=тв, з> каждая из компоненте*, автомата в есть структурный . =/МошрФный образ

- V3 -

соответствующей компоненты автомата <•. ' '

множество структурных гомоморфных образов автомата а . С дем обозначать Ной А.

г» т

Определение^! ..S. Пусть <*>, о у., а е.) - структурный гомоморфизм

»»1 4 ¡4 *

n т п да

автомата a«<s, nv5"*' на a*»(s*. п *"f rtV*.,5,*1X*» •

k»» ' J=H ' i»» j«<

Тогда fc-ый входной и i-ый выходной узла автомата а* назовем

согласованными, если v. = а,.

kl

IfeoEefcaJLiL Пусть задан структурный автомат ти^.ср>. пусть с",...с* -структурные гомоморфные образы компонентных автоматов

J р

с>( ..ср соответственно. Тогда, если для каждой операции -f^

Терма Т(е*,...с*> k-ИЙ входной и i-ый выходной узлы * р »

соответствующих автоматов согласованны, то т<е*,...с*> есть структурный гомоморфный образ t<cjp. ..cf), то есть ■

Т(с*„. . .с*> в Нош Т<с ,.. .с >.

л .р * р ■

В п.2.3 приводится ряд свойств прямо, о произведения бинариых

отношенниЛ эквивалентности и толерантности, • которые далее

используются при дока -.тельстве теорем. Рассматривается

отношения вида г = г а га ... иу, на множестве г - п i ,

i.» *

ys 2.x zx, l-ITn. ' ' ",;■.-•./

В п.2.4 приводится процедура и критерии возможности нахождения гомоморфных образов композиции автоматов о помощью гомоморфных образов компонентных автоматов. * ;

г> - - . г» А А

Рассматривается автомат а-о, п х., п и его. Фактор -

' ' »-«ß 1 i**

автомат по конгруэнции с ча з и разумениям р = о *> на . х

- 16 -

П д »

и * г о * на y, л^ '„=»s| , п XJ ' п V u .<5*. *>. где

j»i ' > = i I»« >

„ >" '

V П 'V*» x^V'--.«,,»-1 » » i

Теорема,2.3. »актор - автомат fi^. pjl по заданной конгруэнции < и

отношениям эквивалентности р = а Рs P(tj и « ~ а

■\*tv > * » J

есть структурный гомоыорфчый образ автомата а. Отношения р<*> к «<«,*») определяются Формулами:

<х,и') «•*><«> «—» <V» ,в' «SX («,»' )е * ) ,<5( , к ' > )

(у ,у' ' <з г(с,р> 4—» |3(»,«' )» i) О!«,»' ) б р)(у « &

и{«,р) » т<*,р),

где т<*,р> обозначает транзитивное замыкание отношения т<с,я).

Через £<п далее обозначайся множа та о всех отношений эквивалентности на иножестве г.

Пусть ¿-каягруэнция автомата п V П у.*6,х> ■

Пуоть €< 1 5-1 3 П, ».в £< У.>, Г 5 j £ ФаКТОр ~

автомат ^ £ ж ■ ерть структурный гошморФньй образ • а , - \ 1

тогда и только тогда, когда а#<*>, *'<*» Ь р >, где р*

• • . ,. I»1

и определяется'соответственно Формулами:'

(и ,Х. I в р (*> *—» V » «

,м » « х.х...х x xx _х...хх )

' »-4* IV 4 ХМ г>

< ( <И , .. . ,>(*,»< >...,м >.(Х )Г"*,К ,...,>! 1) «(><*■>>-' (1)

4* ' \ ' 1*1? Л ~ - I 1И г> г

(у..у ) е т'(с.р) <—»

I I I

<Э(е.5>* > е *> (3<>1, н ' е р) (у => рг Х(в,х > у.*рг Л<'>>. (2)

¡1 I I

п (Хщ р)«г | (<:, *?) , (3)

ГД6 1«Т7п,

Теорема 2.4 позволяет предложить процедуру поиска всех структурных гомоморфных образов автомата со структурным входом и рыходом. Она заключается в переборе всех троек <«,р,«> разбиений, удоз. отворяющих это1 теореме.

Пусть задан автомат в - 1 где

г> гг»

о'"', п V П>/ ■ .Для автомата в существует структурный >■> 1 ¡ч '

гомоморфный образ г?*=-г'1л'\ где а*« Нов а. тог^а и только тогда, когда для эвтомата а существует конгруэнция с и биение на рк< р*<с>, такие, что .

о о.,.о р^о о а..,о о),

где определяется Формулой (1), определяется формулам (2) и (з>, а "о" обозначает тривиальное разбиение, 1 £ й п, ( £ 1 5 п.

ШОШШЛ^ Пусть задан автомат в « * * л , где

г» т

Для автомата " существует • структурный

гомоморфный образ в*«^*^*, где н0м а, тогда и только тогда, когда для автомата а существует конгруэнция с, такая, что р*(£) г «Г<«,о>, ,

к V .

где рк" < ^) определяется Формулой (1), определяется Формулами <г> и о).

Теоремы 2.5 и 2.6 описывает условия, . дря которых возможно

построить ГОМО'*ОрфНЫЙ образ композиции с помощью гомоморфных образов композитных автоматов.

Приьеден пример нахождения гомоморфного образа структурного автомата с помощью гомоморфных образов компонент композиции.

Глава 3 обобщает результата, подучи. № в главах 1 и 2. В п.3.1 понятие р-юрФизиа . распространяется на структурные автоматы. Дано определение упорядоченного структурного авточата как автомата. ыножества состояний, входных и выходных сигналов которого упорядочены и определение структурного р-мор$изма или р»-мор$изиа для автоматов со структурным входом и выходом.

Если структурный автомат с задан термом т<с4,...,'с >, то, множество образов автомата "с при р-ыорФизме, которые задаются аналогична термом т^,...,ср) и для которых Б - образ с^ при рв-морфизые. 1 £ 1 ¿ р. будеи обозначать рйоГТ, На случай р«-к )рФизмов распространяется понятие согласованных узлов, введенное для гойоморФких образов. При этой предполагается,что частичный порядок алфавитов на согласованных уздах один и тот же. Теорема 3.3 Пусть задан структурный автомат т«^,...,ср), где с4,... ,£г - автоматы со структурно входом, и ' выходом, и. пусть для каждого автомата с.. существует р»-шрфизм в некоторый упорядоченный автомат-с., Функции переходов и выходов которого изотопны. i 5:1 5 р. ТОГДа, 60ли вкомпозйции т^,...;^) для каждой одарапин терка т: к-кй входной и Г-ый выходной узлы соотаетстаугхжго автомата согласованы, то существует ра-шрфдаа автомата т<с4,...,с )■ в упорядоченный автомат кс^,.. ..¡Г,), т.е.

ТЧс^,, ,. « рМог Т(с4,... ,ср. .

причем функции переходов и выходов автомата т<е1,...,ср> изотопны.

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

Вьедено понятие' структурного квазифактор-автомата, структурного толерантного образа и структурного морфизжз по толерантности.

Из определен т толерантного образа следует, что теорема 3.3.

верна п случае, когда с<.....ср - толерантные образы автслтов

соответственно, а это позволяет использовать композицию т(с4>... ,с ) в 4 шесве контролирующего автомата при организации контроля в процессе Акционирования. •

Пр?веден пример контроля структурного автомата с омощыо стабильной толерантности.

8 заклкяении суммируются полученные результаты. ""

За помощь, оказанную при работе над диссертацией, автор выражает глубокую благодарность своему научному руководителю Богомолову Анатолию Михайловичу. •

1.Мангушева И.П. Построение решетки стабильных тсдерантностей конечного автомата.//Методы и системы технической диагностики.-Саратов. 1981 .-Вып 2. -с. 108-112.

а.Ильичева.И.П., Печенкин В,В. Контроль структурных зтоматов'. -Саратов. 1584. -9 с. - Деп.в ВиНИТИ, № 32оЭ-84. Деп.РЖ Тех.киб.

10.81.516, 1984.

3.Ильичева И.Г., Печенкин В.В. Контроль структурных автоматов да стабил-лым отношениям.//Метода и системы технической диагностики.- Саратов.1983.-Вып S. -0.35-43.

4.Ильичева и.П. Гомоморфизмы и ком юг дии конечных автоматов. //Методы синтеза и планирования развития структур крупномасштабных систек, -Саратов, 1986. -с.37-39.

3.Ильичева И.П. Гомоморфизмы и композиции конечных автотатоь. .-Саратов. 1986. -29 0. -Дш. в ВИНИТИ, '№3018-86. Деп.РЖ' МАТ, 1986, 10Г72.

8.Нангукева И.П. Контроль конечных автоматов • по стабильным толерантностяи. //Катоды и системы технической диагностики.' -СаратовЛ990. -с.24, .

/'.Мангушзва И.П. Mopf-изш по стабильным толерантностям конечных автоматов. //Отчет о научно-исследовательской работе: "'Разработка методов алгоритмического и программного'обеспечения раочетно-логическихсистем искусственного интеллекта, систем автоматизированного проектированная, контроля, управления- робототехни-чеокими комплексами и гибкими производственными системами" (заключительный). -Саратов, 1990. -с.175-208. № roo., регистрации ' 01900048503.

Ответственный за выпуск к. Ф.-м., доцент В.Н.Салий Заказ ■ . Подписано к печати 00.00.S2. Объем I печ. лист .'.Тираж 100 экз. Типография издательства СГУ. ■ ' .