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

■ЛРАТОВСКИЙ ОРДЕНА ТРУДОВОГО 'КРАСНОГО ЗНАМЕНИ ГОСУД-РСТВЕННЫЯ УНИВЕРСИТЕТ И.Ч. Н. Г.ЧЕРНЫЖеСМОГГ

- на правах рукописи

Мангуиева Ирина пазвовна -ЧОРФИЗМЫ ПО СГАБИЛЫШ ТОЛгРАЮТССТЯ!

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

Автореферат диссертации на соискание ученой степени кандидата З-иэкко-ватенатических наук

Саратов - 1932

О.

/

(с

Диссертационная работа emom.ta в Саратовском государственном университете им. Н.Г.Чернышевского.

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

.академик АЁН РФ А.М.Богомолов.

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

кандидат Физико-мате.лтических наук, доцент A.A.ситник.

Водугйй ори анизация - Москоь <сий государственный университет им Н.В.Ломоносова.

Защита состоится

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

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

Автореферат разослан" сШь^ЛГСъязя г.

Учений секретарь

специализированного Совета '•.

кандидат Физико-ютекятичбских ¿/rf/CsJ^tf^

наук '. V W^y П.Ф.Недорезов

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

Ак? В усло&иях широкого приыепния дискретных

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

среди методов проверки правильноот работ« дискретного устройства, в которых математической моделью яэляетоя конечный автомат, болпой интерес щядставл..от те кз1шх. что основаны на использовании стабильных откоцэний.' • Контрадарухздй .автомат ъ этий случае, как правило,■ прога исходного, но сохранит его основные черты. й.В./йкилоз, Н;В.«и©сов к Б.П.Подкокаев 'предложили в качестве орадстеа прозерки ^гояожр^киЯ .образ - 'исходного автомата*. Е.К.КЬрноуваико строит' 'койтро^рукшЯ ав" эшт о помощью некоторого откопения толерантнооти на шожэстве выходных сигналов автомата*. ' • .' -

'Лднияоэ П. В. .Колесо» Н. В. .Подяотмэ Б. П. Алгебраическая аппаратного контроля лптомзгоп //А&то(латика . и тел!?- эханнка. -1073. -»9, -с. 118-133. ..........- '

2Корно;гап?нп:о Е, К. Обобщенна* здддча проверки правильности <рункций.чнрогзаиня конечного автомата //Техническая кибернетика, • -10-77. .-Л 3. -с. Ю3-'13. . "

Интерес в ~аким методам усиливается благодаря возможности использс-ать их дня организгции встроенного контроля, который в усж виях высокого урсры интеграции ^хническик средств становится ваи<%.«е зффектавнш 'видош проверки. Однако, поскольку

■ ¿и-

каадый из иетодов о^ентирован на ограниченную область применения конечно-автоматнад ыолелей. то актуальной даляется задача йаль рйшер^ развитая .аппарата стабильных отношекий и использования его для функционального контроля." . Исследования» по ста-йильншё ■ о-швениян на автомате* иосвяшени труды Фарра3 и Ц.Е.Дидидзе*, р свойств установлен- в.'работах В.В.Печенккна* и П.М.Хрусталева*?.

.. Другой оссхЗенностью, затруднявшей применение конечно-авто-ма 1НИХ Моделей, является их большая разкернооть. Структурная теория автоматов позволяет получать компактные модели устройств, устаи .вливая нужнуй . размерность компонент. Среди публикаций важнее кесто заглмаюгработа В.И.Гдуикова. А.Н.Богомолова, В.Б.Кудрявцева, В.А.Твердох.лебоза. Использование структурного

Farr Е • Нв '.etticfr- Ptopsrii'»» of Sequential Machines //J.Asedc. Comput.Hath. >1963. -Vol. 10 - M -р.ЗЬ5-ЗВ5. '

*Дияияае' Ц, E. O гоыорфиоцах »btouitss , //Труды ВЦ АН Груз. ССР 1073. -Т. 12: -Й.-1. -' -c.ii8-131, 1

вЛ*чвнхии Б. В. Гомоморфизмы авгоиагое //Саратов, 1SSS. Jfen 'а

винкги п eeea-es, рк мат.. 4а по. -e?c.

"ХрусгаЯев Л. К. Разбиения : и лократия со свойством подстановки <. крнечнык Дйтоматах //Методы» системы техгичайкоя диаг-ности* и -Саратов. 1QS1. -Вьл. -с. 97-107.

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

аль_работы^ 1> разрабо-п<л метода построен, ¡я для адакного ктурного автомата другого автомата, доведение которого ано с поведение« . входного, на основе ' исшльз .вгния отьэ-й стабильной толерантности. .

) . Теоретическое обоснование возмокноота и лол-.эозгния энного метода для контроля автоматов, аучная новизна результатов. Предложен новый датод построения мата, сохраняющего сут^еотвенные ч^ргы поведши* исходного, основе использования отношений стабильной толерантности. зана возможность применения '«етода для контроля 5.601 >актных руктурньк автоматов в процессе Функционирования, сутцествлено дальнейшее исследование.стабильных отнесений и ражений, связанных о ниш, на абстрактных автоматах. Резуль-. исследований распространены, на отруктурниэ автоватм. ^ктаческая_и_т§оретачасгая_уенн^ть^ Полученные результата ставдяют собой теоретическое оОобяенив аналогичных разуль-в, касаквдхсл' построения гомоморфизмов автоматов то конгру-ям. .Поэтому в перспективе они могут найти'применение везде, используются гомошрФизш к гоиошр^ньк сбрази:' в Дальнейших них исследованиях по теорж абстрактных и структурных арто-в, в учебном процеос«. при организации контроля диокг^тных" ойстз с элементами встроенного Функционального контроля. убликауии_и_ат1ро<5зиим^ По теме диссертации опубликовано '/'

работ. По ма^ риалам работа были сделаны сообщения и доклады межвузог'чсой школе-сьминаре "Методы и системы технической дна носгики" /Т. Саратов, ^ 2? июня 19°* г./, на п Все сою н совавании-с минаре . "Методы оинтеза и планирования структ кругысмасштабньи отб^гем"/- г.Саратов.26-28 июня 1386 г./, на V Всесоюзном совещаний по технической диагностике и отказоу той'ПРости '1 . Саратов. 26-28 июнь 1990г./.

Структура дисоеттпдаонной работы. Диссертация состоит введения, -рех.глав, заключения у списка литературы <42 наимен вания). Общий с>ём диссертации -98 страниц машинописного теко Содержаще шгеорФационной работа. Во введении дан кратк ,обзрр^раЗег#' перечислены основн

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

Гл'ва 1 содержит - три гараграфа и посвящена разработ принципов построе'япо стабильной , толерантаоста на мнозкест состояний аь ^о^та даугого автойата, поведение которого связа с поведение« исходного. Исследс„ание проводится дл конечн автокатовг без г^ата их отздктуры/с.' ^

В п. 1.1. приводятся результату исследований по 'стабильн отнотания« в азтоиатах; причем результаты, касающиеся стабильн толерантносгей. представлены как обобщение аналогичных резул татов по стабильным эквивалентностяи.

В тексте диссертации под автоматом понимается автомат Мили. Определение, 1,1-- Отношение ■■ на множестве з автома' ч й»!(ё.х,у,называется стабильным, если . ' '

^v%t,шг* зну* « хх(»а,»з> * м -» и)»«*»^«)) « мб -е рассматриваются стасильнш отношения эквивалентности >нгррншш> и толерантности. Под толерантаоотью понимается клексивное и симметричное отношение на раосма даваемом листве. . ■ ...

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

встанем любого входного сигнала переводит, все элемента блока ¡биения целиком в дру'гой блок, ■ ■

Аналогичным образом с толерантность» г на шкжестве ^влзнва-:я покрытие. - /

Множество 158 называется пррдклассом в <8,т>, ■и любые два его элемента^ и т. толерантпы,

Множёотао . в £ з называется классом терантности в <з,т>, есл< в есть максимальный предкласо. ^деление 1.4. совокупность вт- {Ч»®«'1'"} оасоов в

ютранстве толерантности о,т> называется базисом, если для всякой толерантной пары <в,«:> существует класс вк, ¡аржавдй оба этих элемента:

удаление из вт хотя бы одного, оасйа приводит к потере этого >йатва. „

Нетрудно установить, что множество стабильных толер^тностей х>мата й образует решетку относительно теоретико-множественных ¡раций пересечения и объединения. Эта решетка обозначается I. Решетка ТвА является поярешетеой решетки всех толерант-, ¡тей на множестве з.

L

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

Определение t .5. Толерантность т на множестве е называе й-пс^хден'-тл, и обозначается . г , ' если она являе

наименьшей стабильной толерантностью, содержащей некото ислеред выоранную неупорядоченную пару v®*' «я, vv® 8-Всякая от сильная толерантность автомата а может б получена к множества 2-порожденных толерантностей о помо операции обьечинения, т.е.

Процедура построения множества Тед сострит в следующем.

1.Согласно определим» 1.3 для кажной пар« «^"а® 9 * s СТР°И г-порожденн4.л толерантность, совокупность их образует множес

тв'а - г* V mk«> ^ Полагаем i<-2.

2. Строится множество стабильных толерантностей следующего ур:

т«кА - } о по&-'л> циклической процедуры

, 1 ! и /-j'4» , j»i ,... ipink_',') J _,>•

3.Если mk>i. то k!=k+.i. и перейти к п.2, В противном случае -п. . Ч.Конец.г ■.'•' v'V^''••-" Л -

1,2 посвящен. непос^едств;енно изложению метода построй для конечного автомага и его стабильной' толерантности нон

«

;мата и связанных о ним отображений. Этот метод обобщает логичные результата для конгруэнций и гомоморфизмов! ' гь т - стабильная толерантность автомата' а-<8,к,у,«,\) ,

по заданной стабильно» толерантности , отроите:. отноие-р<г> и отношение *<т,р> по г -и ь-щаюшу отношений зрантности р на.х с помощью Формул.-

>0 <3 р< г> <-►

(Уа'.в.е в>4<*..*,> «г—» (Мш, ,х.) ,6<' > а т),

к I к I ■ к9 I ' I *

/У в *<т ,р) <—► - .

л .

<3<в, , в.« гМЭ< х., х.) в р> {у - /.,»,,)*.) & у' » М »,, х.) >.

к' I ^ г к". » ♦ I' )

Пусть зг. с^ и о^ - произвольные базисы иростраяств эрантностей <з,г>,-:х,р> и сооответственно. Предлагается

дувдая процедуре построения автомата по заданной гройка арантностей и базисам вг- | в1| , с ~ ^ и Ь^» | !Зк

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

п { В^ . « 3,}, г.р~: П { * « с^}, у^.« п { У • £>„}. Через.з|г или з* обозначается шожестео блоков покрытия вт и всевозможных непустых пересечений, аналогично х|р или оки и их всевозможные непустое пересечения из ср, у| и.™ V оки и их всевозможный непустые пересечения из . рассматриваются три отображения:

Б 31т <?;<в>-Вт

X ^ *1р .

0' X У - ч\т •

Определяются Функции <5 • их-:

■«•'в|гх ;|г , й-(о,о) - n {bi2 {¿(..»oJ.J -({««».x»}.^

xcO XeO

MeQ .

где через а и о обозначены элемента множеств s| и х|

■

соответственно. . • :

Поскольку элементами множеств э|г . х\р и у J ^ являхлт подкгжест множеств s,*„ и v соответственно, то на s|T .* |р существует частичный исрядок по. включению. ' Рассматривается автомат а-<3^ ). Процедура ег

построения нгщс.йнае^ процедуру Факторизации по конгрузнциям совпадает о. ней. если толерантности являются зквивалентностяю Она называется квазифакторизацией, . а автомат а; -квазиФактс -автоматом автомата я по стабильной толерантности т„ т « т«* Следующая теорзка описывает условия корректности, процедл квазифакторизации, т.е/ for случай, когда при определен функций 6-//к, ^.-^рювегоб; -{«*»>'>}„(, .'или {*<»'>,,}»«а ►

покрывается целиком ни одним.блочон соответствующего покрытая. Теорема 1.1. процедура квазифакторизиши для автомат A»<g,xfvf£tA,:>..tK> заданник.толэрантабстям r.p.i и произ^ольнь их базисам на нножевтеах а, х и у соответственно определяе автомат, av тогда и только тогда, когда т« т*а, е> s pit), £

Определение.;!\9.„ Автомат /ws.x.y^.x) будем называть упоря доменным, если важное, из ыножевтв s,x,y частично упорядочено. ...

Примером упорядоченного автомата может-служить квазифактор автомат.

- и -

Пусть дан упорядочений автояят Упорядоченный гзтешт . з-^.х

л л Л А А " Л 1} л Э 0

зозеы изоморйадм автомат?' .«,; -воле .существует тройка .зза-ио однозначных оюрьехту.в^и'. отображений «¡о,!»,®), где »э.-» 8., » II/ Iй у. что

л* А 51

. *>< (пгн) <р(в}), Хл<®> >»Хя<«»<л» '.

я лхбнх 5 « з, х « х, причем каздое кз отображений V к ® ть мзо?«>р^зк соотвзтствужщня уиорадочеишх множеств.

Пусть . задан аачшат- л»(а,х.у,й5х). орздоченннй автокгт н'тоеем толерантный образом

томата а, если он изоморфен некоторому квазкфаггор-автокату а* томата А. ''■'•..

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

ределенйе 1,12. Пусть с г»* .V' > - -¿тображения,. определяемые в эцессе квазмфакторюиции. автоиата а а квази<$актор -ав-хжат А', Л,в) - изоморфизм а■ на.некоторый толерантный образ а. Тогда эйку отображений <р,у,э>-<«>-»>'2-е' > назовем корфизмоы по збильной толерантности автомата а 8 автомат а. зрста 1.3. Пусть <р,у.в> - морФизм по стабильной толерантности гомата а в автомат а, тогда для любах »з, х «'х

р<6(*,хП <6',Р<:В>,^<Я>»,

в<\(в,х)) 5 М(>1»)'|). Показано, что для произвольного автомата.а Функции переходов

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

На о"«>эании теорЛш 1.1 предлагается процедура построе все" толерантных о'х.^оз автомат аналогичная построе гомоморфах образов. Она 'заключается в переооге его стабиль тол^рантностей и •йлерантноотей на х и v, удовлетворяю •геореме t.t.

Гоиведеч ьример построения толерантного образа для автомат 9-0 состояния®«, не имеющего нетривиальных конгруэнций (прост автомата)

Определение 1.1'. Пусть задан автомат a-<s,x,y,6 , \i упорядоченный автомат , .А«<ё,х,у,5,м. Тройку отображен .<*>,»,»), где t> аз—в, ix—х, в iY--Y, назовем г-морфиз автомата А в ¿лонат а,-^оли для любых » в s, * « х /i>iiii,»)t'si(V( *><*)), ea(i,*irsAifin,v«i); , : -

Множество образов зтоыата а при p-морфизме будем обознач

- Пошпие р-мор4мзна являето-я естественным обобщен гомоморфизма ав-юматов.; Показано,: что.морфизм по : толерантно также является частным видом р-морФизмз (Теорема 1,4).

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

В п. 1.3 дано теоретическое обоснование возможности испо зования р-мор{«зма для контроля конечных автоматов в проце Функционирования- (Tepp^vw 1:5 , и 1.6). Приведен . прим

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

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

Под множеством с понимается множество всех систем пяти объектов . с » <з, п*,» nv >^»x,< гя0 n»m

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

.множества, причем х и y. содержат пустой элемент в,- i=-i7",

—— т' V ' - г» m

J~t,m, а 6 ts хп*!* s< к ,s *flx¿*nv - отображения.

Полагаем, что у каждого элемента с «с есть п входных и п

*

выходных каналов и узлов. На , .ожестве с определяется система операций р. которая содержит одну бинарную операцию д параллельного соединения элементов и счетаую систему частично определенных унарных операций £ где fM - операция

отождествления ¡-ого выходного и к-ого вводного узлов. Операция 1М представлена в д'зух видах: - отождествление без

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

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

4 ■ •

<с,р>. Под термом понимается любой символ с, обозначавший элемент множества с, а также любая композиция вида или

9<T«'V' где Т.т4,та - термы. i=i,2. под структурным автоматом понимается автомат, представленный в виде композиции других

автоматов и описываемый термои т<е1,...,с >, в котором все элементарный операции определена для набора артома^ов со структурными входом и выходом. Через нот а обозначается множество воех гоыошфй+шх образов автомата а без учета структуры и воспринимаемого к-ак абстрактный автомат.

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

' П ,

4 Л ' ■

Определение 2.3. Пусть задан автомат *,»п

В V

Автоьк..' 8-<в, п г., и р будем называть структурным

. говонорфш образом автомата А. если пд» г>в« г>, з>л» л>в« а и сущетеует гоа»мор$изм <*>,»-,») автомата а на автомат в, такой, '

ЧТО |> 18 « о V/ , где 2.,.1-»,п ,

»»« 1 * - '

< I» - ,_

9 - о е. , : - где . е.1У. Р. ,

¡.» 1 ' .' * .. ' - ТУ

По определению : и*;»". «•.*„>» ° >>•■•,

ее ли в(]х,, Аналогично определяется в .

» о е:.

Гомоморфизм в этом случае . называется структурным

гомоморфизмов. . •• ■

Определение 2.4.Пусть задан структурный автомат а«тд<с*, -.. ,с*>. • Автомат ...,с®> называется : структурным гомоморфным

образом автомата а, если 1) в » но® а, 2)та=тя, з) каждая из ■ компоненте*, автомата 8 есть структурный . жыорФный образ

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

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

.л ж

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

автомата й-<з, п*t< Пу »5<х> «а fl"»<s*. nÄ*. П• Тогда й-ый входной и i-ый выходной узлы автомата а* назовем согласованными, если »v= V

Пусть задан структурный автомат кс^.-. .ср). Пусть с*,...с* -структурные гомоморфные образы компонентных автоматов с4, ..ср соответственно. Тогда, если для каждой операции

терма тсс*,...с*) »c-ый входной и t-itö выходной узлы

■ 1 . ■ ... «

соответствующих автоматов согласованны, то т<с*,.,.с*> есть

структурный гомоморфный образ Т<е ....с ), то есть

• » р •

Т<с ,.. .с > т Нот Т(с , . . .С ) . 1 р > р

В п.2.3 приводится ряд свойств прямо, о произведения бинарных отношенниЛ эквивалентности и толерантности, которые далее используются при . дока ^тельотве теорем, - Рассматриваются ■

■ ,г»

отношения вида г - га га ... о г^, на множестве z - п

r^s i.x zt, .■.'•.■•'

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

Г> - .. m ! ■' л Л

Рассматривается автомат а- <s, ^ х., п У него i-актор -

»*а * i»» .

автомат по конгруэнции « на s й раз Учениям р = а 'р- на х

-16 - • П м

и » ГО'« ма У, п Х| , п .¿"V где

) » <6<ь,х>> , ** р 'с'

^•ж'*«'- Л <х<»>>< >>* >

' -г, ■ '

П <Х,>р' .....«г,»'

. ; V»» к

Теорема 2.3. Фактор - автомат по заданной конгруэнции <■ и отношениям эквивалентности р = а рь< р<-г.> и * ' = о «2 *<«:,р>

V * 1 I"*

есть структурный гомоморфный образ автомата а. Отнесения «) и определятся Формулами:

е- р< *) <—> (*«,»'е31((»,»*»е (6< ь, >:), <5<а' ,х' ) )

(у, у' ' в т(«1 р) ♦—» (3(»,»'|« £НЭ(*,»') ерНу " Л

' у '» Мб' ,«'>),

*<«,р) « Т<С,р),

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

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

Теорема 2.4. Пусть «-конгруэнция автомата а=<£„ п х., ^у ,а,х>.

Пуоть ря е< )о, 1 * ч з о, е< им». Фактор -автомат а^. " ^ я есть отруктурный гомоморфный. образ а

тогда и только тогда, когда р'и), я.г **<«;, о р >, где р' и определятся соответственно Формулами.-' -

(И. ,Х. > « Р,<«> «—»

V V - 4 .

<У(х',* ,,,.,■» I < «Х...Х* XX Х...ХХ. )

< < < м ), (х., . . . ,м * ,...,>! )) е р1е)), <11

»* ' I ' 1*1* . * , П - » - ' 1 ' п '

(3<в,»') « «:> (Э<я,>1'«е р) (уу= рг Х< в, х > 1г у «рг^Мв' , )|' ) ) . (2)

х*( с ,р>»г*( £гс) , (31

ГДе 1=5,п, ,т.

Теорема 2.4 позволяет предложить процедуру поиска всех структурных гомоморфных образов автомата со структурным входом и рыходом. Она заключается в переборе всех троек <«,р,*> разбиений, удоз.отворяющих это''' теореме. . -'^орема.ЗЛГ Пуоть задан автомат, в » ■? * да, где

п V Пу ^Л» • .Для автомата в существует структурный

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

Рк& *"(«! о о...о Рка о о... о о >, где <) определяется Формулой (1). »* определяется Формулами |2) и <3), а "о" обозначает тривиальное разбиение, 1 £ к ^ п, I Л 5

|еорема__2.,§._ Пусть задан автомат в - а , где

г> *> '

п пу'Л>Х) • автомата г- буйствует ; структурный

V«* * 1*1 1

ГОМОМОРФНОЙ Образ В*»**^*, где А*е Нот А. тогда и только тогда, когда для автомата а существует конгруэнция такая, что

) & «г* <•*,»> , .

где р*(л) определяется Формулой <и, определяется Формулами <2> И 13>.

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

построить гомг<орФный образ композиции с помощью гомоморфных образов компонентных автоматов.

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

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

Еоли структурный автомат с задан термом T<ctf... ^>то множество образов автомата "с при р-морФизме. которые задат-с-Я аналэгичнш тер»юм Tic4,, ...c^j и для которых ci - обраэ при р»-норФизме, 1 £ i £ р. будем обозначать рмог . На случай р»-к орфизмов распространяется понятие согласованных узлов, введенное для гокоиорфних образов. Пш этом предполагается, что частичный шрадок алфавите» на согласованных узлах один и тот же.. Теорема 3.g Пусть задан структурный автомат т<с4,...»ер>, где с4,.., автЪваты со "структурным входом и выходом, и. пусть для каждого автомата с/, существует ра--корФизм в некоторый упорядоченный автомат.Г, Функции переходов и выходов которого "изотопны, t s:t s р. Тогда, еоли в композиции т(с1,...¿t^) для каждой операции ^терш т. k-ыЯ входной, и i-ык выходной узлы соответствущаго автомата согласованы, то существует р5-мор4мзм автомата T<ct,...,c J-в упорядоченный автомат т*^,...,^), т.е.

Tic,,,...с^) в рМог Т<е4,,

причем Функции переходов и выходов автоката т(с>(..,,ср) изотонны.

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

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

Из определен 1 толерантного образа следует, что теорема 3.3-.верна в случае, когда ...,с* - толерантные образы автоматов с4,.,.,с соответственно, а это позволяет использовать композицию т(с4,..,,( I в ' 1чесве контролирующего автомата при организации контроля в процессе <т>"икционирования. *

Приведен пример контроля структурного автомата с омоиью стабильной толерантности. , '

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

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

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

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

10.81.316,1984.

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

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

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

8.Иангушева И.П. Контроль конечных автоматов по стабильчык толарантаостям. //Методы и системы технической диагностики* -Саратов,1990. -с.24. ,

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

Ответственный за выпуск к. ф.-м., доцент В.Н.Салий Заказ '• . Подписано к печати 00.00.92. 0<5ьей 1 печ. лист. Тираж 100 экз. Типография издательства СГУ.