Устойчивость поведения атомов тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

П О Ш4

САРАТОВСКАЯ ОРЛЕНА ТРУДОВОГО КРАСНОГО ЗНА.'ЕКИ ГССУДАРСТЗЕННЫИ УНИВЕРСИТЕТ 1;М. Н.Г.ЧЕП!ЬШЕЗСК0Г0

Ка правах рукописи

Кальянов Леонтий Венеаминович УСТОЙЧИВОСТЬ П035Д5НИЯ АЗТОМАТСЗ

»

01.01.03 - математическая кибернзтлка

Автореферат

диссертации на соискание ученой, степени кандидата Физиксккатеиатлмесккх наук. • .

Сарзтса - 1233

Диссертационная работа виполнекз б Саратовском государственном университете кй. й. Р. Чернышевского.

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

гкадешк РАЕН А.!?..Богомолов.

Официальные оппоненты - доктор технических наук, профессор

З-А-ТвердохлеОоз,

кандидат физико-математических наук, доцент В.В.Печенкин.

Ведущая организация - Московский государственный университет

им. 1Д. В. Ломоносова.

/-7 - ¿¿и)*Ц 1й33г. в^ч. && 1«я

Защита состоится " > т - 1533г. в ' ^ ч. ^ ^ кин.

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

С диссертацией. южно ознакомиться в СиЗлютеке Саратовского государственного университета лгм.: ;н.Г.Черньв®зского.'.

Автореферат разослан " " ¡¿/¿¡Л- 1333г.

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

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

кандидат физико-математических .

наук П.Ф.Недорезов

/

Г*

-и-

ОБПАЯ "/АРАХТ2РИСТЖА РАБСГЛЗ.

Актуальность темы. Работа поевлпена "сслэдок-низ устойчивости поведения автомата относительно заданного кдзсса неисправностей. Актуальность рассматриваемой задачи определяется сиротам использованием' дискретных устройств в разданных системах упрасления и повышения требования иадежоста к ним. В цело?*, проблемам надежности и контроля ■ посвлцались работы П. П. Пархоменко». а.л.Богомолоза, 3.А. Таердохледова.

Д. В.Сперанского. И.С.Грукского и -других.

Под надежность» з работе испишется устойчивость поседения дискретаого устройства пр« возникновении неисправностей. Чзгл всего неисправности возникает при сборке дискретных устройств из готовых компонент. При этом одни»' из сз' .ествекних классов неисправностей язд.атся "перепутываю',е" ее дошиия элементов схёш. В. этой связи возникает- вопрос, о выборе характеристика устойчивости поведения аатошта относительно ухазакгого класса неисправностей. В качестве такой характеристики в работе предлагается рассштривать спектри и группы инерции" автоматов.

Цел*. работы.. Цгльв работы является, списание спектров' и групп шзрцни. а также исгвхльзаванке их при построении экспержентоз е 'атавгеагаи.'-: 'У -^'У-^:'-, - [ --V-'

• : Научная новизна результатов^ В работе , введена " понятия* спектра и группу жедаогв качгйтг5 . хара1ггер>!(лжи устойчивости поведения . автомата отаосятс^гьно неисправностей типа "ткрепутцвания" входов--.. Иес-вгдовлш ккогообразие' спектров и груш инерции для всего ваю^тва- автоматов, а также для классов автомзтоз <3 ' . Зйл^кроззрншк:" *; парагЕ рога. : Установлена асситтитаческве. оценка'-'^ . автошзов>а"; иётрйвршыьш спэктраки и группами янерида. Зяеденл на гяюхзстов'

автокатов м шэжесгве групп .инерции и установлена сзязь ыезд;

. Показана возможность кспользоэан:'..я слзктроз и гругл Кп'ерци;', при построек;'.;-! Зг:спер;:кеэтоз с. автоматами.

Г'рд^тхчес.удл ценность работа. При определению; s разэт«: условиях. полученные результата позволяет строить контрольные зкспзрйЛ'ан'ш для указанного класса нзкспрззностей. дл;:ка которых значительно . л^ных* кзьосткой.-' Получзккые ' результата могут исподьасзатьсл при регзюги рлда задач ::сптродя к яипкхяийй дое»фгти1К. устройств прэгрзкяия . систем. . кздзльз которю: яэаязтся кокгчньй автомат со структурно» зходси.

?-!зтодика исследо^ан'л.ч. • 3 . диссертационной работе использовались алгебре- логические" аётоды-.'. теории кон-зчьи.« автоматов, а также катоды теории груш. .

Апробация работа к т;убдикащ-;и. По". ' темз диссертации «ораягзгавано. 5 рзбот. По :•'■ материалам работа ,<Зшй сделана сооОчЗКия и доклада кз И Всесоюзном - соз-зщажи. - секкнарз "Методы синтеза* • л . планирования ' .-развития , структур круцкошсшзаСши свете*"'. • ка .ш. .. зеезогзноа • секиваре по ' дискретной'. иатема*тж . я /ее " •приложения« / г.йэсква.. 28 января, - .1 февраля -1990г.л.- /на IX Всессавнойконференции по щюблекак- теоретической кибернетики т.Волгоград, сентябрь 1990г./. ка 1X1 Всесоюзном секикаре да исскустаенноку интеллекту / г.Москва, октябрь 1990г.л на г^аждукародной конференции по Интеллектуальным системам / - г.Москва 28 сентября - 4 октября 1992Г. /

Структура диссертационной; работы. Диссертация : состоит . кз воедвнкя» двух глав, ' заключения и списка литературы (57 наименования). OOsstfl объем диссертации - 115 страниц машинописного текста.

-S-

Содержзние диссертационной работа ■ Во введении переч;;слени •сиознгй результата, подученные в роботе, л та.тае представлен >яд понятая а обозначений, используемьа з диссертации. Под ;атоттои понимается конечный автогсзт.со структурным зходсм.

конечным таициальним автоматом со структурно входом -:азьзаетсл набор где А - f eu-----.ч'-1

в = { ь .ьг.....ь, }, Я - ^ .....% }• * - «уншм«.

определенная на множестве Q к л к ' пряикмзхлцзя значения из 0. v - Функция, определенная на аюгсстзе о * л и прин1:илйззя значения из з. ккожестаа A, Q, з 1из!азнтся соответственно входным алфавитом. алфавитом состойся и выходнш алфавитом автомата- v. ©/нкцнл ^ нззньлетсп йунадий пиеходеэ. 'а Фун:гц-;я i» - Функцией згиодоз автомата v. •

Входными еловая! автомата. т.: о-зшгем

произвольные конечное последоваталы'лсгл с:):.золоз .зл^ааита л. Бшоднинк сдеоама автомата' ? -»изсазае» шнвчшз псследсзательноси.. сюеодов ' ал;р,гита ' в» ■ crcjnsir ' соотолк^П - аензчгил , последовательноста с-сэолоэ ая5£:з:ггз fï. ,

Функции пнре'ходоа и '/а^одоз'. гзтс^тз естественный образом ' рзспрострдаа'атсл.. 'на . .'аножеетсо Q * а* ■ <с сохрйнгнкгм обозначений} Вязкно; • солзгаен го определении

Фы.за.) = ^t ГД2 q.c Q» в в •Я, а « Д.

Аналогично. = vi /где ; а - гг^оизве-гьное

«

состоянка зэтезата.' v,, , а ,' *.'« л. дм свозкачзкия сэслэдо2лт2ль;:остп ' - ¡плодтаг: ■ ■• гедзлл . : ?.. ' прсцзсое

"пзрерабсп£1 алзз- о сзод;с5 "ZKZ": агадуг^у» 5ук:згп?: »<«.»)=>( a.iï^WWq.sr^ -Ч«.«)- ЗДЙСЬ а в' Q, a в л"*.

'ГСЗЭДЫЯ ,50В1Ц83Г5«Й . -SOKBHHfcSt' СЭТКЗТ. ,

• реализует чвкоторуо : /<Зунвдш- • îj а*»';".'.îr с<»>

-Б-

нззнвзегдуз о.-л. СуккцмеЯ. О.-д. функция. .реализуемая автоаато

с а входам, -шзет п аргументов.

, + ■

Пусть .и - конечное.• непустое »асхество из п злзьйнтов. Бе:

ограничения обс-юста полагаем.' что н - ( 1,2.....я V

)

Совоггупкость всех взаигшо .однозначных 'отображений цкожаства к н; себя образует групцу. которув -будеи" назшаг« сикйетрмзакоС Группой sn саел-зни .» на акогестве - к. '-Прэиззолький элзизщ п « í?n млз'хзаотоп подстановкой. Производная подстановка >■■ записывается в ездс ■ " . , ■ - = ( ^ ).

ГДв ( -V г '•.( ¿IIÍM21.....crin)).

ш дая краткости rr = -с o-(i),c(2},„.,c(n> ). Единица с групп-

sn - тсхдёстзенкаг.' -подстановка « = U2...n). .Подстановка л

казызаетоя чел-юй, еслг сна кохет бать- приведена u е после

четкого числа персетат-говс:; кест ее элементов из втерой стро::::_ D

щ»-П'.вноа. одучаз'. г.. нечетная. Четность кз зависит ст выбора

перемен кест. Глохество. всех .• "четонк хюдотауозог образует'

зкахопер^мекнук . -группа* '• аи ' степени' .порядок- .которой

розен г.;/ 2. ' '

Произвольна* • содгрупзв. G группа .,зл •'. ".азизьстся группой

подстановок на' гзккаствв . К;' ..Грувпу,;. содгрргур' ¿язь. едоничний

элемент груши Sn, буден' казкрггй». ■ единичной йла тривиальной и

обозначать Е. Пусть .с - подтруелг . гтзуаян с. Прикез для-

подгруппа' ейозючен!^ ..G'£ с. Подгрухпа с £-с называется

собственной, есха, с* »»-.о, что - • зепившавтеа, 'как "с- < е.

рассмотри проговольнуа /группу подетапоеок G £ £л. Элементы

ю„ ,юе- к -называются G .-эквнвахгнтнши.- если существует такая £ £

подстановка п с-с. что п(ш4 /агкэ видеть. что

G -з;:зивалс1гшость ярля-зтея стноигниак .эквкгалаптносп;. Класс эквивалентности, порождекньй элементом юг н относительно группи

' а называется g -орбитой и обозначается гд. Стабилизатор элемента о-в группе подстановок. о . -это подгруппа 31()(п) - i 7ii.-G } | . itoEKOCTb' орбита mG равна индексу

- ПОДГРУППЫ StaCei) 3 ГрУППЙ G. ЧТО Записывается -сак j G:St0(ra) J .

Группа подстановок в называется транзитивной на тяюжестзе п, если see элемента тожества и. g -эквивалентны или. что разносильно, если с if имеется розно одна орбита -сагю кзю^.естзо ' £1. Группа подстановок G ¡шзизается к -кратно транзитивной на .етожестзе и, если сиз трагаитизна .на н -л «если лабое упорядоченное isicsecTSO. ссстоясес кз к различии эде»ентоз хкожества «. «жет curv переведено в лобог другое .упорядоченное ¡vaoxecrao различных' элементов . кногк.-стза .м некоторой

подстановкой из группы о. -

Пусть группа а язляется пэдгруппоЯ группа с*, тогда пглет место раззеглняе гругоы в*' на дззсстороннме смежные классы по подгруппе G:. С" = я с + я в.'я4в +...-» яг_„G + «в, где.

Г-J G'-.G I . Грг-^J ' C^-^G ¡Г*.- i....... . ЯЗЛЯЭТСЯ

еог^авеяинки групаааг гйгша с. -.=

Чзрсо Ci.^* сбоглтлчп:* пласс автожатсв с п входами

?. еэотояввези & зкоддагм. •'■ «гзаыа«*.' Х' скйзодзйи, па каждая входа., а эдхогэгьгг* 'сисогая^ •.

Определение'I: «зжктрся 'гкедога о'.-дл Фуюодм. *••:<■• <«*)', «®д*. •' реаайзуемеЛ автекато-з Ъ a входам.--назогец 'Гоедедавательность групп. пзрйстзнозез:'зходез ei аг-.ч'.г" ¿г.... ,где для' .

«л '• -if . * - »

B3a®OTO"ie'-M-e^s|'.«' br«r.dr;? -f {*»>'■ а..*. f»(»H J."

-8. Временем стабилизации спектра. инерции- - g^g^.. .s Gt>..., о.-д. функции f (аеи^*. * иазовев. шнималькое значение t. при котором для любого ,i>t G^= G(- - -

В дальнеRosm под о.-д^- функцией будеа поникать о.-д. Функция, рзализуекуа автогатои с ю ЕХодаии '

Будем говорить, что о:-д. <£?нкшя . f (*»), оед*,. имеет тривиальную группу инерции,. если для каждой подстановки я e.s^ , найдется сдою :.а'«2д*. такое, „ что * («»-) = f (п(а-у). О.-д. Функция £. >.а)„ йгз&т .тривиальный спектр. -если для

каудой подстановки я -s ve. найдется буква вед такая, что t (в) = i (в(аи. :

Определение 3: Последовательность групп a^g^g^...is^^G,.

Пусть о.-д. Функция г («). икает. спектр инерции

. с^ > 'Gt ■ со вреиенеи стабилизации t и

группу инерции, равнуа Gfc. Разхзззш грушу на левосторонние скэишз классы дос, . .вдяучод что -шеючу таксад.'"классу, , ис, где я е sn. будет-«оотсетсгхзать одна и .только одта' о.-д. йункция .."c'-f«l.. '..ое&*;'"' ••такаа." что доа.'.-ksssoto вед* g (a) s £{я(в)). ч -г'-..' . •

Каждая тзкая.о.тя/ фжаг» .с.(»j, цаье? спектр кизрдеи

Д. — я G пО . сО ■'Ь cG • it"* > nG в~" ,

« 4 £ : . .»' .4** t

состояний из груш.-ссрря^пш соот^зтстоуж^"-' Грушаг, спектра

Прл ЭТОМ, ЛСЛН ДЛЯ ыгииорего 1.'- isis t, ncGt, то nG.iT"1=Gi.

Пусть о.-д. £(«), «в&*. миеет'группу'инервди с. тогда

число о.-д. Су»:,<;цгЛ. ... сходязих в слаос. ' - порожденный неисправностями типа . перзкутшадаа входов» содсрглгг j s^g | элементов. ;'• .

Обозначив через $ (сt.ь"),s-..n,p) кножество груш инерции

о.-д. функций, реализуемых автоматами из класса к(<к,к"),га,я,р):

Ъ((к.к'Ьт.п* = У 5 С (к,к*) ,ш,п,р); рем

5 ((к.к'У.п) = из ((к.к" ) ,га,п) ; 5 (п) = и 3 ((к,к*),п)г

1е,к * »ОЧХЫ

А через аг ((>, к *),я, п,р) обозначим множество спектрос. ассоциированных о о.-Д. Функциями. реализуемыми автоматами '.'■:< класса цц^п.я.с.р)'

X ((к,к*) с и 3? ((к.к').п.п.р);

рея

X С (к,к*) ,п) =г и Я {(к.к-).п.п); -5? (п) = и С {к,к*) ,п).

Введенные множества з. 3. 5 (£?. я. аг, гг ) позволяет характеризовать многообразие ьможзстс групп (спектров) ккерцяи. ассоциировании* с. гможествамг д.-д. функций. . реализуемых автоматам! соответствутких кягессз.

Глаза 1 содержит пять параграфов и посвящена изучению свойств спектров и групп инерции конечных автоматов. . В первом. параграфе .приводятся результата . исследования многообразия кножеств спектров и групп ггкерцкт. Тёоргаа 1.1: 1* Для- ЛЮбСЙ. о.-д. фуНХЦИИ . £ (а), • аеД*.

реализуемой автоматом г .Из ' класса. ' ¡с'ць.к^.т.в.р),. вреггя ' стабилизации спектра инерции не. превосходит величина 2р-1. гГ Оценка.,тяученная.з путель г"..достазжа. Следствие 1.1: для. шюй .подгруппа а сикга. ричесхой' группы зп найдется о.-д. функция £ (а), '««а*,,' реализуемая автокатом с п входами. икр"кяая группу- инерции, равнуэ-о,-

Теоремз 1.2: для любой спектральной последовательности найдется о.-д. функция f (а). аед*. ииещая спектр инерции, равный дп.

В параграфе 2 рассмотрен вопрос о многообразии множества подгрупп группы Sn. порождающих на множестве

Ш<1.к->={ (о» »"г....."„ > I ISiin, {0,1,. .k'-l}1 J

различные орбиты.

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

"Теорема 1.3: На множестве и. .щи (к')Ь: п!, ла5ые две различные подгруппы G и G' симметрической группы sn порождает различные, орбиты.

Теорема 1.4: Если (k")l< ш, то существуют две различные подгруппы G и с группы sn. порождающие на множестве &iIkVa одинаковые орбиты.

Следующие утверждения устанавливают связь важду значенилки параметров класса автокатов К((Ь,к')гт.п,р) и KHosscusaEW s к к. а также множествам s, s, s и иг, а.1, и.

Теорема 1.5: Для .ЁоЗой подгруппы G грухшы sn в классе «втокатсЕ

K((n!,n),2,n,i) реализуема о.-д. функция £ .икзвзая

группу инерции равную, группе G.

. * е

Следствие 1.2: Для любого не н - s ((n!,n},2,n,l} - S (n). О-'СГТТВИе *. .3: Дяя любого ne к. для лвбого k<n. R7S, ЛЯбОГО ьч: N - (<к",к),»,п.1) с S ( (n! ,2,г., ,1 ).

.■ L-.: "v.r.:-'.'.с- гг;-;годятся н&обхег- и .саг-г-п^н^.

условия для сувдетвсвания автомата из заданного класса, реализующего о.-д. Функции с заданной группой инерции. Теорема 1.6: 2сли для произвольно заданной подгруппы а синжетрической группы s^ в классе автоматов Х((к,к'),ш,п,р) реализуема о.-д. Функция £ (а>, с®а*, с группой инерции о. то в этом классе реализуема о.-д. Функция со временем стабилизации спектра инерции не меньсе. чаи £ ios^n! J.

i -1

Теорема 1.7: Пусть v= i + ^ . где па-тарядок группы

G, r. = iSt(J(î)rl . ¿(а)>|. ««A1- (а)=2п, 1 = £ Юз^п! j,

тогда в классе автоматов KÇ{k,k')'для дабсй подгруппы а симметрической группы s реализуем - о.-д. фикция i (а), ав&*. с группой инерщм. р~зной G.

Следствие 1.4: Для лхйых значений парзкетроз 1г>2. ir>2, леы

— . ' 5

СПраВвДЛИВО- 3 {(k,J>:" ) ,п.г.) = 3- (п).

Следствие 1.5: Для лзбых значений параметров кг,' =¿2, ne в -

3 {(*",*>■,m.n) = '3 U(«t+l)'',(î=+l}.))K,a!.

Следствие 1.5: для любых значений параметров,ьгз, =£2, ¡я я -

Тагрема 1.В: Существует спектральная последовательность- л , кэ

—— , _ , .,. ... ^ ^

яздяючаяся спектрэа ¡яерзии кИкаггой о.-д. $унхции, реализуемой гвтсггзтаки из аласпа Kccît.i* ьа.п.гО,- при 2t<n произвольных, значениях сзр-ггетрсз ш я

Сде.сстпие 1.7: Ддя лгбсго ь<п, для лаобого se и

- « я « {&+!)),я,я).-

оладстзие 1.Э: лзбсго - » с{^\а>,2,я) = я. <«}. Тесту ж. 1.3 г Для ■ лябсго т,® я найдется спектральная пг-слецСвтгелы'-Лть а,, не, язляящаяся спэктрстя инерции никакой '

о.-д. функции f (а), <jca*. реализуемой -автоматами из класса

К((п! ,n).m,n,p). Где p<t И ni>2. ,

Б теореме i. 10 сформулированы необходимые и достаточнее условия, при которых для любой спектральной последовательности в классе автоматов кш-.,ь*),та.п,р) реализуема о.-д. функция, f (а), и*.??, со спектром инерции, равным дп. .. 1у;орзмз 1.10: Пусть \ - произвольная " спектральная последовательность длины t « s. В множестве автоматов К((к,}с'),п.г,р) реализуема о.-д. функция i «ел*. со спектром нкерцга тогда и только тогда, когда t* г п. :•: £ г.:.

п > 2. р i t.

Таким образе*:. ааожестаэ групп инорипи автоматов с п входами совпадает со ккозаствох подгрупп группа sn. множество епектроз инерции со враиэн-зм стабилизации t автоматов с п зходата совпадает со кнохсзтзои спектральных последовательностей длины t. . ■

В параграфе S. рассмотрена задача описания спектра инерции о.-д. функции по задаш;ы:л Функциям переходов и выходов автомата ее реализуэдего. Пусть

с ж *,

CGl=U4,<a')i 3ncS' .5аеА ö (s,.a)=q й fi {с .а) = е'К

С n ^ - ' ^ J

, г % '

К, si к |яе С 3at«Ä l«|£i Ф (с ,cr)=9 & ¿> (о ,в) =<;"..

" I 710 v * = V («"."(а))

о ( л с -

Полагаеп, что оз ~ | .) | и ч ,= sn.

Теорема 1.11: Если спектральнзя последовательность \ является спектрам инерции о.-д. функции f {<*>, &sa*. реализуемой автоматов; v=(а.с,б,то для кажвсй'о isi

с = г \ ( и к4"1 \ ь'" ]■ .

< ч.ч'>еоо

3 параграф 4 голоцены асс>::.сгрог;'.чеега:е сцента числа о.-д. йгнкциГ;, нкег^х нетривиальные группы и спектры инерции. 7еоте;;а 1.17: Азтскзти* ре2лкзуюз'.2 , о.-д. Зуккцка с нгтризиглъной группой инерции, образует ¡лаагестзо меры '.гуль в классе азтсмзтоз, рзглизусяда праяйОЕЬякз о.-д. Фунада. Теогомз а. 13: азтокзть:. рза;г,:зуктэ о.-д. функции • с нетривисльгалг спектром инерции, • образует кнокзстао кера нуль в ¡:лзеое аьтекатсз, реа.пкзутгс;о: произвольнее о.-д. £ук:ц'и;'..

В пзрггрз^э 5 звгдонн та г.-:ог.2Стпе подгрупп

симметрической группа зп и :таа«?стзе-. о;-д. Суккэдй. Подучены результат*;, устанавливав« их связь.

Пусть - ' ' ■

и \ п С*} .

и (с,су~ -■-гдз.а.5 з , в .

16 и "

Р.+-р.--и1я{ (Р,+ А'-"5

р с 5 (а) , ¿г-'сч) >= —-~

т> -+ р —1 --г 'с

где 1 являзтсл длиной , ккникзльного --сдаза. "ш котором о.-д.' $уккцйи .г <а), ретлйчзхяея.. л сзтсжтш. рзализудае

эти о.-д. фуигаз'.п. к?жаг числосостояния ? й р, созтзетствегаэ.

Будем говорить," что подгруппы с ил- -тг&зячеенсЯ группы зп «-блоке, есл:! (с.о*} Аваясгйчко, о.-д. .фгнкщю г <«) и.

асА*. с-бЛГ.ЗГ.К:. ССГ-ГР ( Г (о) , > £

Теорем 1.19: ■ Для добого « >о взЦдете-ч такое -пе к, что для .тгйих разл:!ч:-г.г: «-^йлгтезга подг^тш с й. с* сг'.гсатрическсЯ группы найдутся о.-д. функцта * <«) и оса*. :иакг;е

группы инерции о и с соэтзетстзе:п:о, "такие, что

Р ( f(a), f'(a) > =■ 1.

Теорема 1.20: Для произвольно малого с > о найдутся ¿-близкие о.-д. Функции f (а) и £*(«<>. а«А*, с группами инерции. равными группам g и g* такими, что и (g,g*) = i-(i/n<). Teopem l.21: Существуют группы g < sn и g"s sn, n«* и, не являющиеся группами инерции никаких о.-д. функций f (а) и ■f-(a), cusA*. С мерой бЛИЗОСТИ

S

о

Р ( f (а), £*«.) } =

. А . Л.

где я, ра« я, числа состояний автоматов, реализующих о.-д. Функции 5 (а) и г*(а), аед*. соответственно. Следствие l-.ll; Если подгруппы с и с* симметрической группы 8П. п в N. таковы, ЧТО 6 \ в' " в И' в* \ 8 е. и р^ Р2, р4е N. р2« N. то никакие о.-д. функции £ (а) и £ "(а). аеА*. реализуеше автоматами с' числю;,1 состояний р1 и р3 соответственно, не могут иметь меру близости

Р ( е'(а> )

Пусть о.-д. Функции f («> и £-(а),. сед*. реализуется автоматами с различным числом состояний. Приведем условие, при котором близкие в' смысле метрики р с-.-д. .Функции t (а) и f'C<2)> скзд*. могут «ижкть близкие в. смысле метрики и группы инерции.

Теосгча 1.22: Если подгруппы а и G* сишетричеекой группы о * s, таковы, что g*< а и р « р е м, р « t*,- то найдутся о.-д. фучКЦИИ j (а) II f-faj. cwA*. с ГРУХШЭШ ИНврЦЙИ <3 и О' реализуеше аетшаташ с числом состояний р . и р. соответственно» и с кароЛ близости

Р ( f(а), £'(а> ) = -i--/.

pt+pz-r

Во второй главе изучается связь между сложностью эксперимета по распознаваний автомата относительно заданного клзсса неисправностей и группой <спектром) Инерции. В перзов параграфе исследована зависимость между группой инерции о.-д. функции f (а), оел*. и сложностью зкспержзнтз по идентификации автомата относительно класса неисправностей типа перестановки входов.

Кратным безусловным экспериментом в 1 алфавите а • назовем произвольное конечное множество слов з этой ал4авкте. Результат применения кратного безусловного эксперимента л к автомату v из класса К((Ь,Ь').т,п,р), рэализукцеглу о.-д. функция f (а), аей*. есть КНОЖЙСГВО (а,£ (a)) | оиеЛ

Чараз rv= | vn { nesn | обозначим тслаес автоматов, порожденный

из автомата v.неисправностям; типа перепутазания входов. Классу

соответствует класс о.-д. фукпдаЯ-я , реалкзуетах автомата;?,'. КЗ гсласса такой, ЧТО Jlf= -Г í^í") ] ¿"„{а} г £ (п(а)), аеА*'

Пусть л - кратный - зюяаеримент. Бели результат щяизкекия эксперимента л к автомату v отллчан от .результата применения эксперим.знтэ -я к. лабоку друге:"/ ■ автомату- v* из -класса. я. . то говорим, что л - контрольный эксперимзит для v относительно класса л Если результате щйгаазккя л к дзум раздичнш

автоматам из класса различны. та л нгзьаа^м диагностическим экспериментом для класса siv. .

Укатан, яри какой ограничен:»? на. группу инерции .для автомата ~ ■: <:ств% jV пр-хяой ко»кт-'Л.->н1--'". ?¡;«r-i, cssk'X5 •

Нудей говорить., что1, группа б ^ предетавима нетривиальным пересечением., если существуют группы еи ± е {.'1.2 такие, что

а/ о и й = са- В., противной случае группа а. 5 непредставика нетривиальным: пересечением. ,.--...-Теорема 2.1: Существует подгруппа б симметрической группы б^.. не совпадающая с пересечение« кикахих групп в^'и сз, отличных от группы а.

о '

Теорема 2.2: Если автомат V из класса сс(к.к'),л,п,р) реализует о.-д. Функции £ С")', а« А*, с группой инерции, равной с. непредставимой нетривиальным пересечением и временем стабилизации спектра инерции и то для V существует простой конгрольдай эксперимент длины ь.

Следующее утверждение показывает, что существуют автомата, для которых имеется простой диагностический эксперимент длины, равной времени стабилмзацю! спектра инерции. Теогямз 2.3: Пусть азтомат ч га- кзасса К((к,к*),т.п,р) реализует о.-д. Функция £ (<=>}, оед*. с группой инерции б, непредставимой нетривиальный пересечением, и вредна« стабилизации спектра инерции тогда стеествует слово « а1, язлжцееся простым дистностаческик эксперименте« длины ь» где I £ :С I. : • •

"Я ■ <

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

Учитывая оценку Бремени стабилизации спектра инерции, получекнуя в теореме, 1.1. заметим, что длина контрольного эксперимента в этом случае, меньше известной.

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

инерции о.-д. функции £ (а>, ос а* , и сложностью эксперимента по идентификации автомата относительно класса неисправностей тула перестановки входов. '■.

Пусть автомат 7={А,<з,з.ф.у.^у из класса 20,3.3,?) реализует о.-д. '£#нкцкв £ (в), оед*. со спектром инерции д =• в ь. с & а- в > о

г> I 3 1-» I

Для любой подгруппы с симметрической группы спрзведлизо разбиение в = «с + л с + я о я й + я о .

Г п . * ЗГ г—л г

Следовательно, для каждой группы из спектра инерции о.-д. Функции г (а), аед*. где 1=1,...,1.. сяразедлпБО Б = вй + -я. & + п. С* ... +.п. я. С, .

Р» Ь-■ Л . I - 4

1 I ■ Т. ■

Обозначим через V для . .автомат.

и

полученный га автомата У перестггшгжсЗ яходсз. описизаекой подстановкой п.. ;-} груотм.з . Тогда с азтогатоп V ассоциируется последовательность .жохестз ' '

51чСГ.2СТЗО; я* для солсргс? сзтсггаг. '.ОГДИЧКИВЗ от евтокпз у »а 'сдзкя дл"-"-'« 4-гга ссггг.т^^ггл «зяздретиостсй ил

садпглсго класса. - а?то",тзтсз л* для

1=1.....г ■ ¿ргссез. -реалаумеих

ИГ.Г.1 О.-д. фуи-а;"'"! {<?.). г-д", ■■/'.'

Пусть - крггзй - ¿гСсго 1 = 1.....ь

полагаем. .-V'.:--.:

Последователь:-есть 3. -г .; гродстаэ.:

послзяоватегкюстъ крзгля гагг^гжт^Э'йЖз I.

Если для J2X»ro : - i.....t , результат применения-

эксперимента "д s автомату и - • отличая от результата применения

л любому другому аатс&ату.. из класса- то будем говорить.

что л - спектральной контрольный зксперикет- для автомата У

относительно заданного ■ ¡azoca шисцразнг-стей.,

Содер-хателыю. экспержеят л считается спектральные для

автомата V» когда зксяержкшту д. для £ = г,.... ,t принадлежит о ' *

слово, ка которой различается., гзтоюта v и уя . где

Ч

подстановка я не орик-здзехит группе а из спектра глирнда о.-д. .функции s" (¿0,. .

Если результата при^нспка акшмржента ■ к габыу дзум а;зто„'лтап из класса'различна, то будеа гооормть,. что -спектральный . дчагкаспячзскй.' зхвогрикент для азтасдта v относительно заданного класса неисправностей..

•я - простой схйктрадшгй эксаерлиент. • если 5 л fs г. Пусть > = | а | - простой савпрадькаЯ кшэдюльньЯ «сспарииен? .д.та

ггтс^та V, реализуш$его о.-д_ фукк'^ж f {«*); относительно

заданного класса нЕисаравностсп» тогда, для лхйсЯ' о.-д. Сункцкп f вел*, из класса'.ч1 справедяяво

Предтлсдкк,' ' что -а. = | ы | т. Х-рсстсй ■ .. спектральный

диагносткчёский •акашршеент. дл-л . автша'^ - уотносительно заданного- класса • нзисщаэнсктеп.' тогда- для- заВШ, дзух о.-Д-•¿•ГгКииП г*£а> и fía) íz¿ класса--спразеддва '•'

Теорета . Пусть. . - краю вольная- .' спектральная

последовательность дла-и и. Тогда . для лгссгс. азтгащта.' v\. реазиздазго. .фнадсз- f; .{^/«sá*:' '.«j- сраятгса '»мера«.

раая^м дп. существует крзтаг»! сп^гпк^нь^ воитреиа.нк.''. эксперимент относительно заданного алзссз нскзпгйаг.осте?.. 'Теорема 2.5: Для ляЗсй г-зтр:.-:«:з.лы;сЛ сзэктрсак-ой • позледозательноста д сугцеетзует г-лххст реа-теуг.сдЯ о.-д.

футхкэ £ (а), аеА*, со сззтярс:'. кьсргпи. разни д . для которого пе суосстзует простого ехкктргхьного ¡хзггезлького эксперимента атяозкгехьно зядсах.го кдмсз квйсп^коат-Л. Теор?."з £.?: Для ой споктрггм50« . позг»лсззтек;:э<,-гл супестзует автомат V, резхпгуътлЗ о. -л-' Яук'зу-Я со сц<зг:трг;. кнердез*, равны дп. для которого суг^этзует- урсзто." дкзг!»-л".!чзсгп1й экспзрикйкт отсэталзгь-. го. заданного ;:.г.£зс« неиспгозноетей.

ЧЪорзга. 2.6 я 2.7 17СЗВОДПЯ1* стлать 5!зол о тс:-:. г сСгз:-случае на скестзует зяпккаэтгл стнкпре-;: ы-ада о. -д.

Сункак*. 'л сдоакитьг» . гкзгё'ртептз ш р-.-з2сз15пг.аиаз «штогдгтз сспкжугехько заданного глэсса- ¡«г.гхгадзгзстей.,

В зтой связи".-расс1гггрг(|; Есярог „-сЗ ссг-:с.':!:ки структуру зэтокзтоз. для гзтс>р.й . суг,гс'™йт. сростсй сязктрагыай гксгарккзнт. • Спианя .-•азивз.' сзтс^тгг .• о.-д.

{утпсц!'« со спзктроя • лщ.' .тз'-сл.,. что вездого

лзтаи-п? 1;з зра^ су^гстзуст- г^оттс.Т- • г^сзтуэг.лг.гД ск^ггр^лииЛ эксперимент. , ■'.•*..-■_'

йс 'аракг.с»' чгсто .когда' гите-от

возвращается в исходное состояла .лкзяэ' -«г'-г^э ттктш работа.' кг превосходящее заданной. кс:кйг^гга..' . ¿г^т^'агйа спектра ююрциа следует, что сусесхзуе* «йксгрг^стг». пг пракалгется из

слозах длины, гзгньгоЛ вггиая-- йч с.тгпрз годоки, но

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

врежии стай&шзацда спектра инерции»' поведение автомата более устойчиво опюсительне ■ заданного клзсса неисправностей,. чем на

СЛОВаХ ЩИ!-.3 ЗОЛЬНОЙ ДЛИНЫ- .

1й теоре:.й1 1.1.. следует. что для произвольной подгруппы с с^златрический группы зп (в том часла тривиальной) су^естзует автомата "с у состояниями, ¿аащке группу -инерции, разнуи

устойчив?.«. относительно лвбнх неисправностей га заданного класса

- » - ■ ■

на лгй'иХ слова:', во входном алфавите длина., ¿'.гньсей 2р-1.

Из теореы 1.17. и 1.18. следует, что для почта всех автоматов существует эшоес>1кент , относительно заданного класса неисправностей длины, существенно ианъсзЛ, чем известная. Е заключении сумтруглхгя получен>ше результаты. 'Закдзчёнис к основные.'заводы. В диссертации зперана сведены характеристик;: устойчивости поведения аато'латов - спектры и группы инерции. Списана их сеойстза. Указана воза-озиостъ использования их при построении эгакрак^зе:;.

Перечисли:« полученные в это» плане результату диссертации. . -

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

2. Установлено взаиж^яюэначаое ссотаетствиз .вггду екяеееггвом спэктроз инерции. эре?, о.-д. функций, реазкзуакс автоматами с п Влодлж. и янохествоа спектральнщ послЬдозатальностс:.*..

3. Показано, что" каогество групп инерции с.-д. фунадй*.,\ реализуемых автоиатзкп_с. п входам, совпадает.со каожаствса Есаз, подгрупп симкзтрмческсй груши.- :

4. определены значенаа параметров 'класса автоматов с п входа»;, при которьк:

а) для лйбой подгруппы я сиагепзпеейоА .пиша»' в." задх-ггам. ¡сасса азтонатов реадауека .о.-д. фгтдая, шгвдо- задагшув

а --■

группу инерции G;

Ъ) для лэЗоП спектральной - последогатглъности л длины t найдется автомат, реализующей о.-д. фушддта, спектр

инерции, равней д .

5. Установлена газискиоать спектра ингрцта от функций пзрсхсдоз и зькодоз агтог.зтз задакнсгс клззса и вида :«;^ор:-зц::о:п,.ого дсрезз О.-д. фуНКЦ-.ОТ.

S. Подучены гсс'.аагготичвскшэ оценки чпелз о.-д. Функций, нг-ек^к нетривиздькке группы и -спектра инерции, рзализуегдг». гзтс:.'лт2Г5< заданного класса. Показано, ню почти ses о.-д. £ук::ции илииг тркаиадькн-э группу и трнзкалькггй спгкгэ пиаре», Слодстзиец зтого язлдетая то, что почти зее классы ашегдатоз. пороченные кенсдрззностя'й! заданного класса, s:crr ггклость л!. ?. ' Взадсиы некоторые естестве;!нкз метрики на 12Юл.-зстае о.-д. функция и множестве. групп кнзрцлк. йзедедозака ззанлдаезязь азр близости'о.-д. функций.я их груш инерции/ 3. Установлена связь- кзгду ■. группой 'инерции и. слдазюстья эксперимента по распознавай^ -езтоцата стнсситсльно заданного класса неисправностей.. Выделено'тзюгзегао.груш гае^двгл таких.' что для обладающих кал гвта&етоэ-- оусествувт простой яснтрс-ъний -экспериментдлину, разной вракгкя .ставмизаЦии -спектра. инерции.

Э. доследована связь гхъяу спгсгрзгз эксперимента . по распознавания.. автомата

инерции и сло-сюсть» относительно зад. нного

оасса неисправностей. Показано., "по..;з.!>лге"» спгктров и групп инерции позволяет уг'днызггь 'аедлёгагге..проверке .множество неисправностей заданного класса. Следовательно. группы а спектра инерции когут использозатьсл при анализе' тпраээпруоднрсти автоизта. - " -■'■'."■-'.".

Автор вираязет искреннпэ . si гдубокуо благодарность езоецу

научному руководатёло акадекку А.М.Богомолову:-к академику В. Б. Кудрявцеву за постановку задачи ;< пог,:рцъ. оказанну»*при. работа над диссертацией.

Стенок опубликованных по теме диссертации раЗот. î. Кахьлнов Л.В. О групповой характеризацщ автоматов. Тезисы докладов :с Всесоюзной конференции Волгоград 1S30 г. 41(2)

2. Кальянов Д. в.- о спектрах кнерийи автокатов: Б сб. fô-.тоди и систем» технической' диагностики. выл 15; 1S32 г. ч. 2. ..

3. Кальянов Л.В.- Цашин Q.C. Пакет прикладных программ тестового контроля и диагноза. - // Еетода и систеш технической диагностика. - Саратов „SSà'.-Buc 17. с.64-53,

4. Кальянов Л.В., Кузнецова C.B.. ' курнлов А.А., Папаев C.B. Программная реализация ыетода распознавания логических Функция. // Иетоды и систеш технической диагностики. -Саратов iSar.-Вш е. с.59-63- ."■ ..'.•' .-/У-.. '

5. Кальянов л.в., Цашмн О.С, Патт щх>гракь! Построеняя тестов. Тезисы докладов п Всессшзногч> ;совефния - сеышара " йетоды