автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.17, диссертация на тему:Проблемы и методы теории обобщенных математических моделей конечно-автоматного типа

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

р Г 5 -0-Д-

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

ЧИРКОВ Михаил Константинович

ПРОБЛЕМЫ И МЕТОДЫ ТЕОРИИ ОБОБЩЕННЫХ МАТЕМАТИЧЕСКИХ МОДЕЛЕЙ КОНЕЧНО-АВТОМАТНОГО ТИПА

05.13.17 - теоретические основы информатики

05.13.18 - теоретические основы математического

моделирования, численные методы и комплексы программ

ДИССЕРТАЦИЯ в форме научного доклада на соискание ученой степени доктора физико-математических наук

САНКТ-ПЕТЕРБУРГ 1994 г.

Работа выполнена на кафедре статистического моделирования математико-механического факультета Санкт-Петербургского государственного университета.

Официальные оппоненты:

член-корреспондент РАН, доктор физико-математических наук,

профессор В.А.ЯКУБОВИЧ, доктор физико-математических наук,

. профессор Р.Г.ВУХАРАЕВ, доктор физико-математических наук,

профессор В.В.КАЛАШНИКОВ.

Ведущая организация-Санкт-Петербургский электротехнический университет

Защита состоится " 4 1994 г. в 15 час. 30 мин.

на заседании специализированного совета Д 063.57.52 по защите диссертаций на соискание ученой степени доктора физико-математических наук в Санкт-Петербургском государственном университете по адресу: 198904, г.Санкт-Петербург, Старый Петергоф, Библиотечная площадь, дом 2, математико-механический факультет, ауд. 3536.

С диссертацией можно ознакомиться в Научной библиотеке им. М. Горького Санкт-Петербургского государственного университета по адресу: 199034, г.Санкт-Петербург, Университетская набережная, дом 7/9.

Диссертация разослана " ОКУиЛ&Я 1994 г.

Ученый секретарь специализированного Совета Д 063.57.52, кандидат физико-математических наук, доцент Л.А. КУБЕНСКИЙ

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

Актуальность темы. Уже несколько десятилетий продолжается интенсивное развитие различных аспектов теории математических моделей конечно-автоматного типа, нашедшее отражение в целом ряде монографий (Айзерман М.А. и др., Бухараев Р.Г., Глушков В.М., Кудрявцев В.Б. и др., Трахтенброт Б.А. и Бардзинь Я.М., Чирков М.К, [1-3], Яблонский C.B., Eilenberg S., Ginzburg A., Kan-dell А. и Lee S.С., Paz A., Salomaa A., Starke Р.Н. и другие). Существенное место среди таких моделей занимают различные виды обобщенных (нечетких) и стохастических (вероятностных) автоматов, которые изучали Бухараев Р.Г., Варшавский В.И., Мучник A.A., Хунядвари Л., Чирков М.К., Щестаков A.A., Carlyíe J.W., Chimel К., Ginzburg A., Kandel A., Lee S.C., Paz A., Salomaa А., Starke Р.Н., Topeiicharov V. Turakainen P., Wechler W., Dimitrov V. и многие другие. При этом существенным стимулом к развитию пового направления - математической теории обобщенных (нечетких) автоматов послужили основополагающие работы Л.А.Заде и некоторых других авторов (Kandel А. и Lee S.O., Dubois P., Prade H., Negoita C.V. и Relescu D.A. и другие) по теории нечетких множеств и ее приложениям. Однако, внимание, проявляемое к исследованию различных обобщенных и стохастических математических моделей конечно-автоматного типа, объясняется не только чисто теоретическим интересом к решению новых задач дискретной, в том числе "нечеткой", математики, но и тем, что конечные автоматы различного вида являются, как правило, весьма удобной математической моделью для описания определенного класса систем, устройств и протекающих в них процессов. В частности, понятие стохастического автомата широко используется в качестве математической модели целого ряда систем, устройств, процессов и явлений, которые содержат в себе элементы случайности (или, являясь по-существу детерминированными, подвергаются случайным воздействиям и т.п.) и допускают конечно-автоматную интерпретацию. Повышенный иятерес к изучению различного рода обобщенных (в том числе частотно определенных) конечных автоматов также обусловлен возможностью йх применения в качестве простых и удобных математических моделей дискретных процес-

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

Данная работа является итогом многолетних исследований автора в области математической теории (в общем случае частично определенных) обобщенных и стохастических конечно-автоматных моделей, проводившихся в СПбГУ в рамках плана фундаментальных госбюджетных исследований. В 1993-1994 г.г. исследования частично выполнялись при финансовой поддержке Российского фонда фундаментальных исследований (93-012-292),

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

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

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

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

Практическая ценность работы. Теоретические результаты исследования послужили основой для разработки под руководством автора на кафедре статистического моделирования СПбГУ и в лаборатории математических проблем информатики НИИММ СПбГУ комплекса алгоритмов и программ для ПЭВМ IBM PC/AT, практически реализующих теоретически обоснованные в работе методы анализа, синтеза и оптимизации обобщенных и стохастических кот нечно-автоматных моделей. Теоретические результаты исследований включены также в спецкурсы "Теория автоматов", "Стохастические автоматы" и "Автоматное моделирование", читаемые автором на математико-механическом факультете СПбГУ.

Аппробация работы.

Результаты работы были представлены на трех всесоюзных научных конференциях: 1. "Проблемы теоретической кибернетики", Иркутск, 1985 г. [47]; 2. "Планирование и автоматизация эксперимента в научных исследованиях", Ленинград, 1986 г. [48]; 3. "Применение вычислительной техники и математических методов в научных исследованиях", Киев, 1986 г. [49]; и двух международных научных конференциях: 1. "Third International Workshop on Model Oriented Data Analysis", St.Petersburg, 1992 [57, 58]; 2. "International Workshop on Mathematical Methods and Tools in Computer Simulation", St.Petersburg, 1994 {62, 63]; докладывались и обсуждались на научных семинарах в Университете им. Йожефа Аттилы (г.Сегед, Венгрия) [36] и в Будапештском университете им. Лоранда Этвеща

(г.Будапешт, Венгрия) [44,55], а также на семинарах кафедры статистического моделирования СПбГУ и лаборатории математических проблем информатики НИИММ СПбГУ.

По теме диссертации опубликовано 63 работы, в том числе 4 монографии.

СОДЕРЖАНИЕ РАБОТЫ

ГЛАВА 1. Основные определения и проблемы теории частичных обобщенных конечно-автоматных моделей

1.1. Обобщенные автоматы. Алгебраическая система И = (7?.,+,•), где Т1 непустое множество, а + и - - определенные на И. ассоциативные операции, называется полукольцом, если выполняются следующие условия: а) (И,+) - коммутативный моноид (его нейтральный элемент обозначается 0); б) (К, •) - моноид (его нейтральный элемент обозначается 1), для которого 0 является нулевым элементом ( вместо а • Ъ просто пишется аЬ); в) операция • двусторонне дистрибутивна относительно операции +.

Пусть X, А,У есть алфавиты входов, состояний и выходов и |Х| = п, '|Л| = т, |К| = к. Обобщенным конечным автоматом над полукольцом И (П-автоматом) называется система

_А=<Х,Д,У,г,{К(х,г/)},Ч>, (1.1)

где г - начальный вектор-строка, г 6 7£1,т; q - финальный вектор-столбец, q € 7£т'1; {Щх, у)} - матрицы переходов, Щх,;/) € Кт'т, х 6 X, у € У. Обобщенное отображение (Я-отображение), индуцируемое 7?.-автоматом Л, - это отображение Л" х У" в К, определяемое выражением

щ, если |ш| = |и| = 0,

(

Г П Щх» У{)ч, если |и)| = |и| = 4 > О, ¡=1

0, если |и>| ^ |и|,

где IV = Х1Х2 •. .х<, V = У№ •.. ¡Л, 6 X, у; 6 У, и |ги|, - длина слов

и], V.

' Абстрактный И-автпомат - это система Л = (X, А, г, {Щх)}, q), которая индуцирует ^-отображение Фд : А'* —> "Я, определяемое

выражением

ФЛ(„,)= / ГПВДЧ, если ^ О, rq, если Ь — О.

1.2. Частичные 71—автоматы. До середины 70-годов в известных работах по теории частично определенных (частичных) конечно-автоматных моделей, как правило, под частичным автоматом понималось такое обобщение вполне определенного автомата, при котором допускались неопределенные элементы в векторах или матрицах, описывающих функционирование автомата. Такая интерпретация была недостаточно общей и не охватывала многие интересные и в теоретическом, и в практическом плане случаи.

В работах [28, ЗС, 2] и основу введенных автором понятий о частичных векторах, матрицах, автоматах впервые был положен универсальный подход, основанный на том, что всякий частично определенный объект (вектор, матрица, автомат) при различных допустимых способах доопределения задает некоторое множество вполне определенных объектов (векторов, матриц, автоматов) и тем самым, возможно описывать эти частичные объекты посредством множеств объектов и свести исследование частичных автоматов к изучению множеств автоматов. Такой подход позволил не только исследовать наиболее общие свойства частичных автоматов независимо от конкретного способа их задания, но и ввести в рассмотрение и изучить принципиально новые классы частичных автоматов конкретного вида.

Частичным т.—мерным вектором-строкой г назовем любое непустое подмножество г С Л1'т. Любое непустое подмножество 5 С И1-'" назовем частичным т—мерным вектором-столбцом . Любое непустое подмножество II С 72.т'" назовем частичной (т х п)— матрицей. Частичным И— автоматом будем называть систему

А=< АГ,Л,Г,?,{к.(г,у)},ч>, - (1.2)

которая есть множество вполне определенных автоматов, такое, что А =< Х,ЛУ,г,{Я(х,2/)} >£ А ^ г е г,Щх,у) € И(а£ 5- Под частичным отображением Фд, индуцируемым

частичным 71—автоматом А, понимается множество отображений, индуцируемых вполне определенными 72—автоматами А 6 А.

При решении целого рада задач теории частичных автоматов не требуется оговаривать конкретный метод задания частичных векторов и матриц r,q, Щх,у), а можно ограничиться приведенными выше определениями. Это относится к изучению тех свойств и особенностей частичных автоматов, которые инвариантны относительно конкретных способов задания частичных векторов и матриц. Однако существует множество проблем анализа, синтеза и оптимизации автоматов, которые могут быть решены только в том случае, если такой конкретный способ задания r,q, R(x,t/) определен. В зависимости от определения метода задания автором были введены различные типы частичных векторов, матриц и автоматов частного вида [2, 28, 36]. Приведем некоторые из них.

1.3. /—автоматы. Пусть f„, v = 1,<7, есть параметры с допустимыми множествами значений <т„ С 72, i/ == 1,3, а /,■ = /¡({£„})>г = 1,ш, есть явно заданные однозначные функции от этих параметров, принимающие при допустимых значениях параметров значения из 72.

. Множество всех таких функций от конечного числа параметров обозначим через 5(72.). Частичный вектор г, определяемый как

г = {г|г = (ri,r2,...,rm), п = /,•({£„}) 6 ?(7г), ?„ 6 au,v = lTs}

назовем f-вектором и будем задавать в виде

г = г = (/ь/г,...,/га), где U = МШ), i« 6 5„,¡/ = (1.3)

Соответственно, f-матрицей назовем множество матриц

R = {R|R = (1и})т,п,Rij = ЫЫЛ) е 5(7г), £„ =

задаваемое в виде

В- = (/иШ))т,„, = (1.4)

Частичный 72.—автомат (1.2) назовем f—автоматом, если г и q есть /-векторы, а Щх,у),х € Х,у € У - /- матрицы; такой /-автомат индуцирует /-отображение Фд(и>,и) = гП'=1 ^(1'>!/>)Ч> € Vu, v = 1,3, являющееся частичным 72—отображением Фл : Л'' х F* —> 3(72).

В частном случае, когда 11 =< {0,1},У,& > и, следовательно, функции в 5(7?.) есть булевы (логические) функции от параметров с областью допустимых значений {0,1} , соответствующие /—векторы, /—матрицы и /—автоматы условимся называть Ь— векторами, Ь—матрицами и Ь—автоматами.

1.4. г—автоматы. Пусть 12. = К,- где Ж есть поле вещественных чисел. Введем следующие обозначения, где а, /3 £ {0,1},

) при/3 = 0, при /5=1.

А

Любой /-вектор вида г = (£ь (2, ...,£„,), где е <т; = | а,-, Ь,- [ С К, » =

_ »1

1, тп, есть независимые друг от друга параметры и а; < 6,- при аД = 0, о,- < Ь,- при аД = 1, бу^гм называть г—вектором и задавать в

виде г = ( | а,-,Ь{ | ) . Соответственно любую /—матрицу Й. = / ¡=17

, Г ( при а = 0, ? Г 1 \[ приа=1, 1 \

такую, что {у 6 ац = | ау,Ьу |С г = 1,т, / =

есть независимые параметры и ау < 6у при ау/?у = 0, ау < Ьу при ау/Зу = 1, назовем г—матрицей и будем задавать в виде Л =

йА

ау,!>у | ) • Частичный V,—автомат (1.2) назовем г-автома- .

том , если И = К, г есть г—вектор-строка, 5 - г—вектор-столбец и Щг, у), х € X, у € У, - ¿—матрицы.

1.5. ¿—автоматы. Частичным детерминированным автоматом (У-автоматом ) назовем такой автомат А —< X, А, У, <1,

у которого начальный Ь—вектор <\ — (<1\, (¿2,..., (1т) удовлетворяет условию =,1 и при г ф ] ¿¡¿у — 0, г,} = 1,ш, Ь—матрицы переходов Г)(:г, у) — {рц{х, у))т,т удовлетворяют условиям: для всех Чу&гУ}Щ{х,у) = 1 и при г ф д бу(х,у)Д',(х,у) = 0, а финальный Ь—вектор-столбец фиксирован и равен вектору е; все элементы которого равны 1, и поэтому при задании автоматов опускается.

1.6. Частичные функции аЛгебры логики. Пусть Р" множество всех функций алгебры логики от п аргументов.. Число таких

функций равно 22". Частичной функцией / алгебры логики ox п аргументов назовем любое подмножество множества F",f С F". Любую частичную функцию / можно задавать в виде обычной вполне определенной функции с помощью введения параметров [2, 26]. Тогда / = f(xi,xi,...,xn,£i,£2,—,£k)- является функцией от п логических переменных .т;, t = 1,п, и к, к < 2", параметров (j, j = 1,к. принимающих значения из множества {0,1}. Такая функция при различных значениях параметров задае.т не более чем 2* различных вполне определенных функций алгебры логики, представляющих собой некоторое подмножество / С F".

1.7. Частичные обобщенные языки [2]. Обобщенным языком над полукольцом 7Z (IZ-языком) в алфавите X называется однозначное отображение Z = Фг X* —► 1Z. Значение Фг(ги) называется весом слова w в 7£-языке Л.

Обозначим через Z(1Z,X) множество всех TZ-языков в алфавите X и любое подмножество Z С Z(1i,X) будем называть частично определенным (частичным) Т1—языком в алфавите X. Из общего множества всех частичных It—языков выделим класс /—языков, а именно, /—языком в алфавите X назовем любое однозначное отображение Z = Фц : X' —> S(TZ). В /—языке вес слова w £ X' задается в общем случае функцией /„ £ 5(71) от конечного числа параметров, определяющей веса этого слова в различных вполне определенных 1Z— языках Z £ Z, которые получаются при различных допустимых значениях параметров. В теории 1Z—языков известно понятие регулярного TZ—языка. Частичный 72—язык Z будем называть регулярным, если регулярны все 7v—языки Z G Z.

1.8. Представление частичных 72-языков частичными ^-автоматами а задачи их анализа и синтеза [2]. Пусть задан 1Z-автомат А и выделено подмножество У'"' С У его выходных символов. Говорят, что 7£-язык £ = Ф^ : JV* —» 7J представлен в А подЛножеством (обозначим Z Ь A(Y^)), если для индуцируемого 72.-автоматом А TJ-отображсния выполняется

'iiev* „eyw

для всех w £ X*. 72-язык представленный в абстрактном 71-

автомате А, определяется соотношением =

Частичным 72—языком Z представленным в частичном Ii—автомате А подмножеством выходных символов У'к' С Y назовем множество 72—языков

Z = {z\ZbA(Y(")), А еД}.

Соответственно, /—язык Z = Фц : X* —> 3(7?.) будет представлен в /—автомате А подмножеством У'к', если

!/€У14

при всех и> 6 -Y*.

Согласно введенным определениям становится очевидным следующее обобщение известно.'! теоремы Клини: частичные регулярные 11—языки и только они представимы в частичных конечных Ii—автоматах. Для теории и се приложений особый, самостоятельный интерес представляют те типы частичных 72— языков, частичных 72—автоматов и те способы доказательства обобщенной теоремы Клини, которые позволяют ввести конкретные способы задания частичных 72—языков и 72—автоматов и предложить эффективные методы решения двух основных задач абстрактной теории автоматов: а) задачи анализа - построения по заданному частичному Я—автомату частичного регулярного Я—языка Z Ь *4(У'К') ; б) задачи синтеза - построения по заданному частичному регулярному 72—языку Z частичного конечного Я,— автомата А такого, что Z Ь _4(У'К').

1.9. Основные проблемы теории частичных Я—автоматов.

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

ные результаты, опубликованные автором в статьях [5-44] были затем им обобщены в монографиях [1, 2, 4], а часть результатов работ [45, 47, 50, 51. 53-55] нашла отражение (в переработанной, абстрактно-алгебраической форме) в монографии [3]. Перечислим прежде всего те проблемы и результаты, которые отражены в последующих главах доклада.

Абстрактный анализ автоматов. Сформулированная в п. 1.8 проблема абстрактного анализа исследована в работах [1, 2, 35, 58, 60] применительно к некоторым типам автоматов. Основные новые результаты, полученные автором в процессе исследований, представлены в главе 2 и состоят в решении этой задачи для введенного в п. 1.3 принципиально нового типа конечно-автоматной модели - /—автомата, в теоретическом обосновании и разработке соответствующих методов и алгоритмов и оценке их эффективности.

Абстрактный синтез автоматов. Сформулированной в п. 1.8 проблеме абстрактного синтеза посвящены работы [1, 2, 30, 43, 61]. Основные новые результаты, полученные автором в процессе исследования этой проблемы, отражены в главе 3 и состоят в ее решении для /—автоматов, в доказательстве ряда теоретических положений, позволивших обосновать новую методику синтеза /—автоматов, и в разработке, соответствующих методов и алгоритмов.

Оптимизация71—автоматов. Различные аспекты проблемы минимизации числа состояний %—автомата рассмотрены в работах [3, 45, 47, 50, 51, 53-55]. Главный результат в решении этой проблемы, представленный в работах автора [54, 55] и кратко изло-' женный в главе 4, состоит в доказательстве принципиально новых фундаментальных-теоретических положений, позволивших обосновать новый эффективный матричный метод полного решения задачи построения приведенных и минимальных форм для случая ^"—автоматов (см. п.4.2). Кроме того, в работах {48, 49, 52, 63] этот метод адаптирован к новому типу автоматов - .?"—автоматам с периодически меняющейся структурой.

Оптимизация стохастических автоматов. Проблеме минимизации числа состояний вполне определенного стохастического автомата посвящены работы [1, 2, 5, 18,. 56, 57, 59, 62]. Основные.ре-

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

Оптимизация частичных стохастических автоматов. Проблеме минимизации числа состояний частичного стохастического автомата общего вида посвящены работы [2, 25, 29]: Основные новые результаты автора в этой области, представленные в главе 6, заключаются в самой постановке задачи, в доказательстве ряда фундаментальных теоретических положений о свойствах стохастически замкнутых разбиений автомата и разработке общей схемы частного метода его минимизации.

Оптимизация стохастических г—автоматов. Этой принципиально новой задаче посвящены работы автора [2, 37, 44]. Основными достижениями автора в решении задачи минимизации стохастических г—автоматов, изложенными в главе 7, являются доказательство ряда свойств I—векторов и некоторых операций над ними и разработка на этой основе практической реализации общей схемы частного метода минимизации и соответствующего алгоритма минимизации применительно к стохастическим г—автоматам.

Помехоустойчивое доопределение частичных автоматов. Различным вопросам связанным с исследованием этой проблемы, посвящены работы [1, 2, 4, 7, 8, 10-17, 19, 20, 22-24, 31]. Основной общий результат .этих исследований, кратко изложенный в главе 8, состоит в разработке автором методов и алгоритмов, позволяющих находить оптимальное по помехоустойчивости доопределение частичных детерминированных автоматов при условии возникновения помех па входных каналах, и производить подробный логико-веролтностиый анализ помехоустойчивости логических схем автоматов к помехам, возникающим в элементах схемы. .

Помимо рассмотренных выше проблем следует также отметить проблемы, результаты исследования которых не включены в доклад, но имеют важное значение для последовательного построения цельной теории частичных автоматов. Это в первую очередь касается непосредственного обобщения на частичные автоматы ряда важных результатов теории вполне определенных автоматов, содержащегося в первых двух главах монографии [2]. и включающего, в основном, те положения о сводимости автоматов общего вида к автоматам частного вида, о представимости множеств обычных регулярных языков в автоматах и об операциях над языками, доказательство которых хотя и потребовало от автора некоторой изобретательности, но в принципе все же было основано на тех же методах.

Другой такой проблемой является построение автором в [1-3, 6] основ структурной теории стохастических автоматов, 71—автоматов и /—автоматов, которое заключается в определении операций образования композиций и понятия правильной композиции и позволяет решать для этих типов автоматов задачу структурного анализа - нахождения по заданной правильной композиции элементарных автоматов автомата, являющегося результатом композиции.

Для дальнейшего развития абстрактной алгебраической теории обобщенных автоматов может также представлять интерес разработанный в монографии [3] автором совместно с его учеником A.A. Шестаковым (внесшим в эту работу существенный самостоятельный вклад) специальный абстрактно-алгебраический подход к интерпретации проблем эквивалентности и оптимизации автоматов.

В практическую реализацию обоснованных автором подходов и методов (d том числе в разработку алгоритмов и программ для ЭВМ) и их использование для решения ряда конкретных задач существенный вклад внес ряд учеников автора (Буй Мин Чи, Л.В. Эглитис, К. Мачак, И.Д. Мирошниченко, Я. Наср, М. Кабаве). В совместной работе с ними автор играл главную роль в постановке задач, формулировке и математическом обосновании основных теоретических положений и методов и в написании совместных работ.

В заключение отметим также, что в работах [21, 39, 40] рассмотрены вопросы, связанные с использованием ЭВМ для реализации некоторых из разработанных методов, а в лаборатории математических проблем информатики НИИММ и на кафедре статистического моделирования СПбГУ группой сотрудников (И.Д.Мирошниченко, С.С.Выговский, Я.Наср, М.Кабаве, Н.А.Дегтярева) под научным руководством автора разработан комплекс алгоритмов и программ, реализующих предложенные автором методы анализа, синтеза и оптимизации автоматов на ПЭВМ IBM PC/AT.

ГЛАВА 2. Проблемы и методы анализа частичных обобщенных конечно-автоматных моделей.

2.1. Регулярные /—языки. Известное понятие регулярного К—языка было обобщено рчтором в работе [2] на случай /—языков. Элементарными /—языками и алфавите X ~ {г|,Х2, ...,:гп} будем называть элементарный Л—язык Z = е ("пустое" слово), определяемый значениями Ф,(ад) = 1 при и> = е, ФДю) = 0 при из ф с для всех w 6 X*, и элементарные 1Z— языки Z — х„ я = 1 , л, определяемые значениями Ф*,(ш) = 1 при w = х„ Ф*,(и>) = 0 при w ф х,.

Скалярным произведением функции /; € 5(71) и /—языка Z называем /—языки, обозначаемые ¡¡Z и Z/,• и определяемые, соответственно, соотношениями для весов слов Ф^.^го) = /¡Фц(и)), (,0) — Фдля всех ги е X*. Заметим, что поскольку /,■ ■ 1 = 1 • /,■ = /,-, то учитывая определение элементарных /—языков, /¡е = е/i, /¡х, = х,/(, при этом в выражениях типа /¡е, е/,- символ е будем опускать и писать /,е = с/,- = /,-. Дизтнкция /—языков Zj и ¿Tj обозначается Z = Zi U ¿г и определяется соотношением весов слов Ф2(») = Ф^(иг) + для всех u> € X\ Произведением /—языков

Zi и называем /—язык Я = Z1Z2, определяемый выражением весов слов Ф^(гв) = (и>1)Ф5 (^г) Для всех w 6 X*, где ft есть

■ п '

множество всевозможных таких пар слов 101,102 € X*, что u>iu>2 = w. Итерация /—языка 2 обозначается и определяется соотношением

Ф , f 1 при w — е,

для всех w 6 X*, где П есть множество всевозможных представле-

ний w в виде последовательности конечного числа и, 1 < v < t, t = |u>|, непустых отрезков w = ,.. ш„.

Всякий /—язык, который может быть получен из элементарных /—языков с помощью конечного числа операций скалярного умножения, дизъюнкции, умножения и итерации, называем регулярным /—языком. С использованием введенных обозначений для элементарных /—языков и операций каждый регулярный /—язык может быть задан его регулярным выражением Z = Z(e,xi,...,xn, fii fb • • • i /*)> допускающим различные эквивалентные формы представления, а также графом /—языка, который строится по заданному регулярному выражению как граф обычного регулярного языка в расширенном алфавите XU{/,} = {xi,x'2,... ,x„,fi, /2,... ,/t} путем введения ребер типа [2].

2.2. Формулировка задачи. Пусть задан /—автомат

Л=<Х,.4)У,г,{К(^1/)},д> (2.1)

и выделены d подмножеств У„'к' С У, р — \,d, его выходных символов. Для решения задачи абстрактного анализа /—автомата • (2.1). требуется найти регулярные выражения /—языков Z„, v = 1 ,d, представленных в /—автомате (2.1) подмножествами выходных букв yj"', и — l,d. В работах [2, 35, 58, 60] автором обоснованы приводимые ниже методы решения этой задачи.

2.3. Рекуррентный меход. Первый, так называемый, рекуррентный метод решения сформулированной задачи анализа со-. стоит в следующем;

1) используя /-матрицы R(i,,yi), е X, jи 6 У, найти /-матрицы

к

= (2.2) (=1

2) используя элементы /—матриц Щх,), s = 1,п, найти регулярные выражения /—языков

•=1

(здесь элементы 6 ЗС&));

3) последовательным применением рекуррентной формулы

- 7<») I ( ?(9) • V

найти регулярные выражения для /-языков = 1,3 = 1,т;

4) используя /-матрицы Щя«, ¡д), /-вектор 5 и подмножества У,!"', I/ = 1,(1, найти векторы

ч(».") = Ё.(х«Зй)Ч> « = 1Тп; (2.3)

»6У.М

5) найти искомые регулярные выражения /—языков, представленных в Л подмножествами , v — 1,(1, по формуле

п

где 2 = и Ец) , Ец - 1 при г =.- Ец = 0 при г ^ 7.

\ / т,т

2.4. Теоретические основы усовершенствованного метода.

Справедливы следующие два утверждения о решении уравнений в алгебре /—языков, аналогичные известным утверждениям (Бод-нарчук В.Г., Спивак М.А., Риякая С.Б.) для алгебры обычных (детерминированных) языков.

Теорема 2.1. Пусть 2, = гЭ и (¿Г = и £?) есть уравнение в алгебре /—языков, где - заданные регулярные /—языки, а 2 -неизвестный /—язык, причем для 5 и пустого слова е выполняемся Ф^(е) 5 0. Тогда это уравнение имеет единственное решение 2 = ОБ* (2, = Теорема 2.2. Пусть

т т

= (¿¡ = (у5Д)ид,), ¿ = (2.4)

есть система уравнений в алгебре регулярных /—языков, где 5,;, Qi, = 1 , т, - заданные регулярные /—языки, а г = 1,т, -неизвестные /—языки, и для всех ¿,]. = 1,т Ф^.(е) = 0. Тогда

система (2.4) имеет единственное решение, регулярные выражения которого могут быть получены методом последовательного исключения неизвестных с использованием теоремы 2.1.

Пусть А =< X, А, г, |Щх)|, 5 > есть абстрактный /-автомат. Введем следующие обозначения: = {^¡уЬ^Т^т гДе есть

/—язык, представленный в А конечным состоянием 6 А (т.е. при 5 таком, что д} = 1, дл = О при Л ^ /) при начальном состоянии а,- 6 А (т.е. при г таком, что г; з 1, гц == 0 при Л ф ¿); 2<ч) = где ¿¡ч} = Ц ¿¡щ есть /-язык, представлен-

ный в Л начальным состоянием о,- £ А при заданном финальном /-векторе 2<г> = где = У,-г,¿у есть /-язык, пред-

ставленный в .А конечным состоянием а^ € А при заданном начальном /—векторе г. Доказаны следующие утверждения:

Теорема 2.3 Для множеств /—языков 2'4', 2М, предста-

вленных в абстрактном /—автомате .А, выполняются следующие системы уравнений для г^' — 1 ,т

% = (и;=,ад,)и% = (и™,ад,)и%

= (иг=1 и Т„ ¿!ч) = (иг=, и й,

(2.5)

где

= У %(х.)х„. (2.6)

Теорема 2.4 Для /-языков I = 1,т, представленных в

/—автомате (2.1) подмножеством У,'"' С У при различных начальных состояниях а; € А, выполняется система уравнений

= (ии (у »('•. * = (2.7)

2.5. Усовершенствованные методы анализа. На основе теорем 2.1-2.4 автором предложены следующие варианты метода решения задачи абстрактного анализа /—автомата (2.1).

Алгоритм 1.

1) Найти Sij, i,j = 1,т (см.(2.2), (2.6)). 2) Найти q(s,i/), v = l,d, s — 1, n (см. (2.3)). 3) Решить одну из первых двух систем уравнений (2.5). 4) Найти искомые /—языки по формуле Z„ = U?=1rZq(s, v)xs, где Z = (¿¡¡)т,т.

Алгоритм 2.

1) см.алгоритм 1. 2) см.алгоритм 1. 3) Решить третью систему уравнений (2.5). 4) Найти искомые /—языки по формуле Zv — u;=1 u;"=1 Zj%(s, v)x„ v =

Алгоритм 3.

1) см.алгоритм 1. 2) см.алгоритм 1. 3) Для каждого v = l,d решить систему уравнений (2.7). 4) Найти искомые 72—языки по формуле Z„ = и^гД!"', v = ТД

2.G. Сравнение методов. Для длины (числа вхождений букв из X) регулярных выражений /—языка Z, найденных (для абстрактных /—автоматов) различными методами анализа, получены следующие оценки _

- рекуррентный метод: \Z\ < |(3m — 1)4ra-1mn,

- алгоритм 1: \Z\ < |(m + l)4""1mn,

т алгоритм 2 и 3: \Z\ < (4™"' - 2m"2)(m + l)n.

Сравнение этих оценок показывает, что с ростом m верхняя оценка длины получаемого регулярного выражения для рекуррентного метода примерно в три раза больше оценки для алгоритма 1 и в |т раз больше оценки для алгоритмов 2 и 3.

ГЛАВА 3. Проблемы и методы синтеза частичных обобщенных конечно-автоматных моделей.

3.1. Формулировка задачи. Задача абстрактного синтеза частичного 72—автомата Лрг заключается в его построении по заданному частичному регулярному 72—языку и методы ее решения в существенной степени зависят от конкретного типа частичного регулярного 72—языка и способа его задания. Ниже рассматриваются некоторые методы решения задачи, впервые предложенные автором применительно к /—языкам и /—автоматам [2, 30, 43, 61]. В общем виде задача абстрактного синтеза /—автомата формули-

руется следующим образом. Пусть задана система

= 2„{е,хихъ...,*„,/ь/2,...,/„), (3.1)

регулярных выражений /—языков, где /, £ 3(7£) (или графы этих регулярных выражений). Требуется построить /—автомат А представляющий /—языки системы (3.1) некоторыми подмножествами I/ = 1,«/, своих выходных символов. Для решения задачи синтеза /—автомата А в принципе достаточно уметь решать ее при й = 1, т.е. для одного /-языка 2 и подмножества У'к) С У, а далее, построив автоматы .4'"', представляющие 2„, и = 1.(1, объединять их в один автомат А. Причем при (1=1 задача синтеза сводится к построению абстрактного /-автомата А, представляющего /—язык 2.

3.2. Метод последовательного синтеза. В работе [2] автором определены правила построения:

1) абстрактных /—автоматов, представляющих элементарные /языки (лемма 2.1 в [2]);

2) по абстрактному /—автомату, представляющему /—язык абстрактных /—автоматов, представляющих /—языки и где

6 (лемма 2.2 в [2]);

3) по двум абстрактным /—автоматам, представляющим /—языки 2\ и 2а, абстрактного /—автомата, представляющего /—язык

(лемма 2.3 в [2]);

4) по двум абстрактным /-автоматам, представляющим /—языки 2\ и ¿2, абстрактного /—автомата, представляющего /—язык ¿[¿2 (лемма 2.4 в [2]);

5) по абстрактному /—автомату, представляющему^—язык 2, абстрактного /—автомата, представляющего /—язык 2* (лемма 2.5 в

И); . __

С) по абстрактным /—автоматам и = 1, г/, представляющим

/—языки I/ = /—автомата А с т = Е„пг„ состояниями, отмеченными буквами выходного алфавита У = {3/1,1/2, - • •»У^}» представляющего буквами этого алфавита /—языки 2„, и — 1,(1 (теорема'2.3 в [2]).

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

представляющих элементарные /—языки, а затем в последовательном построении автоматов с помощью сформулированных правил согласно определяемой выражением Zv последовательности регулярных операций. Затем строится автомат, представляющий систему /—языков Z„, v = 1,(1. При этом для упрощения процесса синтеза необходимо на каждом шаге производить, если это возможно, минимизацию получаемых автоматов с помощью соответствующих методов.

3.3. Производные /—языков. Для простого случая детерминированных автоматов и обычных регулярных языков в ряде работ (Berry G., Sethy R., Puskas C.S. и другие) используется понятие (левой) производной регулярного языка для решения задачи синтеза таких автоматов. Данное понятие было обобщено автором на существенно более сложный случай /—языков, а также введено новое понятие правой производной, что позволило обосновать другие, более эффективные методы синтеза /—автоматов.

Выделим какую-либо букву х, £ X и назовем левой производной f—языка Z по букве х, /—язык, обозначаемый x~lZ и определяемый выражением Фг-1^(ги) = Ф|(х,и>) для всех w е X*. Справедливы соотношения (где /,- € 5(72))

х^'Л = Л, х~1е = Л, х~'х, = е, x~lxt = Л, х» ф xt,

*~.\№ = Мх;12),.х:1(2ы = (x;lZ)fit х;1/.- = Л, x-\zx и z2) = x;lztu x;lz2, = (xj'z)z', x;l(ztz2) = (х:1гог2иФг1(е)(х:122).

Правой производной f—языка Z no букве x, назовем /—язык, обозначаемый Zx~l и определяемый выражением Ф^-^и») = для всех ut е X*. Справедливы соотношения

Кх~1 = Л, exj1 = Л, х,х~х = е, xgx~l — A, g ф s,

(f.z)x:1 = fi(Zx;% (Zh)x:x = (Zx-x)U, = Л,

(Zi и Z,)x;1 = Zix;' и ziX;\ (z')x;l = z\zx71), (zt ZjK1 = ¿¡(¿2х;1) и (Zix;1) Ф^(е).

Конечно-автоматная реализация операций х, 12 и 2х~х определяется следующим утверждением, дополняющим конструкции п.3.2.

Теорема 3.1. Если в абстрактном /—автомате А = (X, Л, г, |К(х)},ч) представлен /—язык 2, то в абстрактном /—автомате Л — (X, А,7, {Щх)},с[), где ? = гШх,), представлен /—язык х~12, а в абстрактном /—автомате А — (X,Л,г,{Щх)},5), где = Щха)ч, представлен /—язык 2х~1.

3.4. Теоретические основы нового метода синтеза. Условимся говорить, что система /—языков 2 = ^¡,2^, • • • , замкнута относительно левых производных по буквам алфавита А", если для всех х, £ X существуют такие Д/(ь') е 5(72), 1,/ = 1, т, что

Система /—языков 2 замкнута относительно правых производ-кихпо буквам алфавита X, если для всех х, 6 Л' существуют такие /■/(«) 6 5(72), = 17т, что ^х,"1 = ЕЛ/Ф)-

Любое представление /—языка Я в виде 2 = 1_1!=| /¡^ (2 = и™, 2} Л), где ¡¡,f¡ 6 5(^2), и регулярные /-языки ¿Г,^) образуют систему /—языков, замкнутую относительно левых (правых) производных по буквам алфавита X, назовем его ОЬ-разложением (ОЯ-разложением).

Любое заданное £>£-разложение (£)Д-разложение) /—языка 2 будем называть минимальным , если не существует такого ОЬ-разложения (£>Я-разложения) этого языка, которое имело бы меньшее число членов. Справедливы следующие утверждения.

Теорема 3.2. Система /—языков 2(-ч'> (см. п.2.4) замкнута относительно левых производных, а система - относительно правых производных по буквам входного алфавита.

Теорема 3.3. Для любой заданной системы т регулярных /—языков в алфавите X, замкнутой относительно левых (правых) производных по буквам алфавита X, существует абстрактный конечный /—автомат А с т состояниями, представляющий /—языки ¿¡,' = 1,т, {¿¡,} = 1,т,) этой системы своими начальными (конечными) состояниями.

Теорема 3.4. Любой /—язык 2 в конечном алфавите X регулярен тогда и только тогда, когда для него существует конечное по числу членов £)£-разложение (£)Л-разложение). При этом существует абстрактный /— автомат А, представляющий этот язык и имеющий число состояний, равное числу членов £> £ - р л з л о ж с пи я (ВЯ-разложения).

Теорема 3.5. Для любого регулярного /-языка ¿Г существуют минимальные £>£- и 1?Д-разложения, имеющие одинаковое конечное число членов, и абстрактный конечный /—автомат, находящийся в минимальной форме и представляющий /—язык 2Г при начальном и конечпом векторах, определяемых коэффициентами этих разложений, а /—языки, являющиеся членами этих разложений, 'своими начальными (конечными) состояниями.

Теорема 3.6. Для каждого регулярного /—языка 2, минимальное йЬ-разложение (23Д-разложение)-которого содержит гп членов, существует абстрактный /—автомат Д. имеющий не более чем т + 1 состояние и такой финальный вектор 5 (пачальвый вектор г), что /—язык 2 представлен в этом /—автомате одним из его начальных (конечных) состояний.

3.5. Алгоритмы синтеза. Синтез абстрактного /—автомата А по регулярному выражению /—языка 2 с помощью вычисления левых производных по буквам алфавита X может быть выполнен следующим образом:

1. В исходном положении множество введенных состояний А'0' и соответствующее ему множество /—языков 2(0' пусты. Если заданное регулярное выражение /-языка 2 имеет вид = }\2\. то в качестве множества введенных на первом шаге состояний .4'1' берется одноэлементное множество {01}, сопоставленное, соответственно, с одноэлементным множеством /—языков 2'1' = {/]}, и для синтезируемого /—автомата в дальнейшем определяется начальный вектор в виде г = (/|, 0,..., 0).

2. Пусть на /1-ом шаге имеем — {<»1,02....,й|} и дСО = {а»,ву, и соответственно ^С1-1' = £¡5,... ,5?/} и .2(Л) = ...,£*}, к > I, где ¿¡, г — Т^к, все различны. Тогда для добавившихся к 2*''-1* /—языков ¿Г;, г — / + 1, к, находим их

левые производные по каждой букве алфавита Л'. При этом, если х~х21 = то к множеству 2(/,) добавляются те 2^, ко-

торые не принадлежат .2''1', и для каждого такого 2^ в алфавит добавляется соответствующее ему состояние. В результате вычисления всех указанных производных будут определены множества 2(11+1) и дС'+Ч, Повторение данной процедуры заканчивается, если = и тогда алфавит состояний /—автомата А берется

равным А = Л<*> = АС'+Ч.

Заметим, что полученное множество 2 ~ = ¿С'+О замкнуто относительно левых производных по буквам алфавита X.

3. Элементы матриц переходов Л(х,) /—автомата А определяются следующим образом: если х~12{ = Ц,/;>(«).£>, то

Ду(*.) = /.;(«), «,/ = 17т, т = « = 1Тп.

4. Элементы финального вектора ц определяются соотношением = Фд(е), i = 17т, т = |А|.

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

3.6. Синтез по графу /—языка. Приведенный в п.3.5 алгоритм синтеза может быть интерпретирован в виде следующего алгоритма синтеза по графу /—языка.

1. Для заданного регулярного выражения /—языка 2 строится его граф (см. п.2.1 и [2]), причем выражения /„х, и х„/„ изображаются одной и той же стрелкой

•—«

и, кроме того, производится объединение его конечных вершин (если их больше одной) по правилам построения графа 2е.

2. Началу графа присваивается индекс 1. Всем вершинам графа, являющимся концами стрелок %х„ в - - 1,п, и не являющимся начальными вершинами заведомо тождественных подграфов графа 2 (начальным вершинам тождественных подграфов целесообразно присваивать один и тот же индекс) последовательно присваиваются различные индексы 2, ...,т, где (т — 1) - число таких вершин.

3. Каждый индекс «', присвоенный вершине, в которую входит стрелка /„х„, переносится на отмечающую эту стрелку букву, т.е.

пишется Хя'\ > = 1,т, .1 = 1,п.

4. Каждый индекс г с приписанной ему функцией /,■ непосредственно переносится через пустую стрелку в ее конец и переносится через стрелку, соответствующую функции /„, в ее конец с приписыванием индексу г функции /,■/„ (с последующим суммированием в вершинах функций, приписанных одному й тому же индексу).

5. Строится абстрактный /—автомат А = (А', Л, г, {П.^)},^), где А = {аьаг,...,ат}, г = (1,0,...,0), чТ = (91,92,...,(?т), причем д,- = /,, если индекс г с функцией /; отмечают конечную вершину графа,

_ I _ _

и д,- = 0 в противном случае, и Щ(х,) = Р*/^ У = 1« т< з — 1. п,

1/=1

где функция, приписанная индексу 1 в начале стрелки . •

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

ГЛАВА 4. Проблемы и методы оптимизации обобщенных конечно-автоматных моделей.

4.1. Эквивалентность 72-автоматов и их приведенные и минимальные формы. Пусть у 72-автоматов

Л=<Х,Д,У,г,{1г.(1,г/)},Ч> ,Л'=<Х,А',У,г',{й'(г,г/)},ч'>, (4.1)

|А| = т, |Л'| = т', зафиксированы финальные векторы q, q' , тогда вектор г в .4 и вектор г* в А' называем эквивалентными (обозначение: г.4^) ~ г'.Д'^')), если для этих векторов

Фл(и>, и) = Фл'(и>,1>) при всех и е А", и £ У*. (4.2)

72-автоматы А и А' инициально аквивалентны ( обозначение: _4(я) ~ Л'(ч') )> если для каждого г 6 72|т существует г1 € 721,ш', такой, что выполняется (4.2), и обратно. 72-автомат А инициально приведен, если

Ы(я) ~ г'Л(ц) г = г' для всех г, г* € 72|,га. Любой инициально приведенный 72-автомат А', такой, что А'(ч!) ~ А(я) называем инициально приведенной формой 72—автомата А (обозначение: ,4' = 11ес1.Л(я) ).

Если в 72—автоматах (4.1) зафиксированы начальные векторы г, г', то вектор q в А и вектор q* в А' называем эквивалентными ((r)Aq ~ (r')yl'q' ), если для них выполняется (4.2). А к А' финально эквивалентны ( (г).Д ~ (г')Д' ), если для каждого q £ Т1тЛ существует q' £ 71"''такой, что выполняется (4.2) и обратно. 72—автомат А финально приведен, если

(r)<4q ~ (r)^q' <=>• q = q'

для всех q,q' £ 72' '. Любой финально приведенный 72-автомат А', такой, что (г')А' ~ (г)Л, называем финально приведенной формой 72-автомата А (А! = Red (г)А ).

Пара векторов (г, q) в А и пара векторов (r\ q') в А' эквивалентна (r.Aq ~ г'.4'ч'), если для них выполняется (4.2). 72-автомат А находится в минимальной форме, если не существует 72-автомата А', такого, что выполняется (4.2) и |Д'| < |Л|. Минимальной формой 72-аптомата А называем любой 72-автомат А', находящийся в минимальной форме и такой, что выполняется условие (4.2) (обозначение: А' = Mm Л).

4.2 Проблемы оптимизации. В соответствии с приведенными определениями можно сформулировать следующие основные задачи оптимизации (по числу состояний) заданного 72—автомата А: а) построить 72-автомат В = Red.4(q); б) построить 72-автомат В = Red(г)Д; в) построить 72—автомат V = MinA Сама возможность решения этих проблем и методика оптимизации в существенной степени зависят от дополнительных условий, накладываемых на полукольцо 72. В работах автора [54, 55] дано полное и эффективное решение этих задач для случая 72 = J- (F— автоматы), где F - любое (не обязательно коммутативное) поле (иначе называемое ассоциативным телом). Основные результаты работ [54, 55] приведены далее в п.п. 4.3-4.5.

4.3 Базисные матрицы Т—автомаха . Правой базисной или £(q)-базисной матрицей Т— автомата А называем матрицу H(.4q) типа (m х dim£(.Aq)), состоящую из системы линейно независимых векторов пространства С(А<\) , порожденного множеством

векторов-столбцов

£(ЛЧ) = {Ь,(«1,»0|Ь}(1У,«) = l]R(x¡,.ji)q, w е х*, V е У*, М = и>.

¡=i

Левой базисной или С(т)-6азисной матрицей Т—автомата Л называем матрицу Н(г-4) тина (riim£(r.4) xm), состоящую из системы линейно независимых векторов-строк пространства С(тА), порожденного множеством векторов-строк

í

С(гА) = {hr(w,v)\hr{w,v) = Г JJ R(x;,y¡), W € X', V 6 1", N = |l'|}.

1=1

Для построения правой базисной матрицы автором предложена следующая упрощенная рекуррентная процедура [1-3]:

a) H0(v4q) =() - матрица не содержащая ни одного столбца, Н,МЧ) = (Ь(!>),гдеЬ(1)=ч;

.6) если Н3_, = (hW,h(2),...,h(»»-')) и Hs = (h"',h(2),...,h("')), и r.g-i < пд < m, д > 1, то матрица HJ+i получается добавлением к Н, таких векторов-столбцов h'"»+1', h'n'+2),чтобы векторы-столбцы матрицы H3+i = (h'1', h'2',..., Ып,+1') образовали базис в пространстве, натянутом на векторы-столбцы, входящие в Н5, и всевозможные векторы-столбцы вида у) = R(x, ;/)h'J',

х 6 X, у е У, j = ~ñ3-\ + 1 ,П~;

в) процедура оканчивается на шаге д = г, если H,_j = Н,- или

II ¡ = т.

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

Пусть H(.4q) = Н, есть правая базисная матрица размера (т х d), d — tliiTi /"—автомата А. Квазипсевдообратной ма-

трицей Hj к матрице Н, называем любую (d х т)—матрицу . удовлетворяющую условию: Н^К, = I(d), где I(d) есть единичная (d х ti)—матрица. Аналогично, квазипсевдообратной матрицей Н' к левой базисной (g х т)—матрице Н(г«4) = Нг назовем любую (т х д)—матрицу, удовлетворяющую условию: НГН' = 1(р).

Согласно определению правой Н, й левой Нг базисных матриц /"—автомата А они имеют бесконечное множество форм предста-

вления

Н, = Н,а, Нг = /Шг, (4.3)

где а,0 - любые невырожденные квадратные матрицы размера ((1 х ¿) и (у х д). Выделяя в матрице Н, любые (I линейно независимых строк Ь;,, I/ = а в матрице Нг любые д линейно независимых столбцов Ьа = 1,5, образуя матрицы а-1 = (Ь1,„ )„=тз> /З"1 = и находя обратные им матрицы а. (1, можно с помо-

щью преобразований (4.3) найти нормализованные формы представления базисных матриц Н?,НГ, такие, что в матрице Н, строки с номерами iu, V = 1,(1, имеют вид Ь,-, = Ь(1/) = (0,..., 0,1,0,..., 0), где элемент "1" стоит в |/-ой позиции, а в матрице Н,. столбцы с номерами ег — \,д, имеют вид Ь^" = Ьт(с).

В общем случае, в зависимости от выбора линейно независимых строк (столбцов) может быть построено несколько (не более, чем С\'п и ) различных нормализованных форм представления правой и левой базисных матриц.

Для базисных матриц Н, и Нг, находящихся в нормализованной форме, соответствующие квазипсевдообратные матрицы Н^, Н' можно определить из соотношений Н^Н, = 1(с/), НГН' = 1(д) тривиальным образом: матрица Н^ есть (г/ х т) - матрица, у которой все столбцы с номерами г ф ¡„, и = Л, нулевые, а столбцы с номерами ¿„, и = 1,«!, имеют вид Ьг(^), I/ = 1 а матрица Н' есть (т х у) - матрица, у которой все строки с номерами } ф о = 1,д, нулевые, а строки с номерами .у,* о = 1 ,д, имеют вид Ь(<т), а =

4.4 Некоторые теоремы о приведенных формах. Следующие утверждения, доказанные автором в работах [54, 55], указывают на некоторые важные свойства базисных матриц Нг, Н, и приведенных форм /"-автомата

Л=<Л',Л,У,г,ь{11л(*,г/)}^л>. (4-4)

Теорема 4.1. /"-автомат А финально (шшциальпо) приведен в том и_только в том случае, если гапкНГ = |Д| (гаикНу = |Л|.)

Теорема 4.2. Если ^-автомат А финально (инициально) приведен , то не существует /"-автомата

Р=< Х,В,У,Гв,{^-1>(х,у)},Чн >, (4.5)

такого, что (r,j)v4 ~ (ти)В (что ~ B(qn) ) и |В| < |.4|.

Теорема 4.3. /"-автомат А находится в минимальной форме в том и только в том случае, если rankHr = гапкН, = |Л|.

4.5. Методы построения приведенных форм. В работах [54, 55] автором доказаны следующие фундаментальные утверждения, дающие полное решение задач, сформулированных в п. 4.2.

Теорема 4.4. Пусть А есть /'-автомат (4.4) и H(Aq^) есть его правая базисная матрица. Тогда , если /"-автомат В (4.5) такой, что для всех х £ Л", у £ У

Ru{x,y) = H'(Aq.4)R.4(x,.V)HMq^), rtf = rAH(AqA), Ча = то: а) В = RetM(q^), |В| • • шв = rankHMcu), H(5qB) = I(mB);

б) Н(гдВ) ость матрица, которая может быть образована системой линейно независимых строк матрицы Н(г^ A)H(.4q/i), и rank H(rflB) = гапк(Н(глЛ)Н(Лс1л));

в)-для каждой пары (r,q), г £ J-l,m>, q £ С{Ас\а), существует пара (г', q'), такая, что г' = rH(Aq^i), q' = Hi(>tqJ4)q, r^q ~ r'Bq' и г £ С(таА) => г' £ £(гдБ);

г) .для каждой пары (r',q'), г' £ q' £ /га0,1 существует пара (г, q), такая, что г = г'Н'Ычл), q = H(AqA)q' £ C(Aq,\), rAq ~ r'Bq' и г1 £ £(гл5) =>r£ C(taA).

Теорема 4.6. Пусть А есть /"-автомат (4.4) и Hfr^A) есть его левая базисная матрица. Тогда , если /"-автомат В (4.5) такой, что для всех х £ Л', у £ К

R„(x, у) = ЩтаА)Ка(х, у)Н'(тлА),

тв = ГдН;(Г/1-4), Чп - H(r -iA)q.4, то: а) В = Red(гл)-4, |В| = тп0 = гапкН(глД), Н(гвВ) = I(m0);

б) H(6qa) - матрица, которая может быть образована системой линейно независимых столбцов матрицы Н(гд,Д)Н(.4^), и rank H(Sqp)=

гапк(Н(г,,Л)Н(Л1ы));

в) для каждой пары (г, q), г £ С(гаА), q 6 Jrm*,t, существует пара (г\ч')> такая, что г* = гН'(г^Л), q' = H(r^A)q, г/lq ~ r'Cq' и

q £ с{Ма) q' е C{BqB)\

г) для каждой пары (г\q'), г* G q' € существует пара

(г,q),такая, что г = г'Н(г^Л) £ £(гд.Л), q = H'(rAyt)q', r/lq ~ r'ßq' и q' 6 £(Bqa) q € C(AqA).

Теорема 4.6. Пусть А есть ^-автомат (4.4) и Н(г.4.Л), H(«4q.i) есть его левая и правая базисные матрицы. Пусть Б = Red*4(q,.t) (В — Red(r.i),4) есть ^"-автомат, построенный из Л в соответствии с теоремой 4.4 (теоремой 4.5) и V есть ^-автомат, построенный из В в соответствии с теоремой 4.5 (теоремой 4.4). Тогда :

а) V = Min А;

б) |Х>| = mD = гапк(Н(г„Л)Н(.ДЧд));

в) для каждой пары

(r,q), г € ДглЛ), q € £(ЛЧа), (4.6)

существует пара

(r',q'), г' 6 £ ТтпЛ , (4.7)

такая, что

lAq ~ r'Dq', (4.8)

и обратно, для каждой пары векторов (4.7) существует пара векторов (4.6), такая, что выполняется условие (4.8).

Изложенные в п.4.3 методы вычисления матриц ЩглА), Н(</Цд), их нормализованных форм H(r,i-4), Hi-Aq^) и квазипсевдообратных матриц Н'(гл-А), H'(^lqyi) и использование полученных нормализованных форм базисных матриц в конструкциях теорем 4.4-4.6 дают эффективные методы построения начально и финально приведенных и минимальных форм конечных /'-автоматов.

4.6. Обобщенные конечные автоматы с периодически меняющейся структурой [48, 49, 52, 63]. Обобщенным конечным 1Z-автоматом с периодически меняющейся структурой над полукольцом К будем называть систему

Ava г =< X, А, К, г, {R(x, 2,)(г)} , q(r) >, (4.9)

где г 6 И1'т - начальный вектор-строка, q(г) е т = О, Т - 1, -

множество Т финальных векторов-столбцов, {R(r, ¡/)(т)}, Щх,у){т) 6 fcm'm, х е А', у £ У, т = О, Г - 1, - множество матриц переходов и Т есть период повторения структуры автомата

(матриц переходов и финального вектора). 72-автомат Avar индуцирует 72—отображение Ф : (Л" х У)* —• 72, определяемое выражением Ф(ш,и) = г П'=| Щ^Ь !Ji){i(n\odT))q(t(modT}), где w — х-,х2.. .xt, v = Vim ■••Vi, xi 6 A', yi (• Y.

Инициально (финально) приведенной формой 72-авгомата А„аг при фиксированной последовательности финальных векторов q(T), т = О,Г - 1 (фиксированном начальном векторе г ) назовем минимальный по числу состояний 72-автомат

М„г =< А', А1, У, г', {R'(*, y)(r)} , q'(r) > такой, что для каждого начального вектора г' (последовательности финальных векторов q'(r), т — 0,Т — 1)в A'var найдется эквивалентный ему начальный вектор г (последовательность финальных векторов q(i"), т = 0,Г-1 ) в Av„r и обратно. Минимальная форма 72-автомата AvaT (с фиксированными векторами г и q(r), г = О, Т — 1 ) - эхо минимальный по числу состояний 72-а.втомат А"аг, индуцирующий то же самое 72-отображение Ф.

Один из наиболее эффективных путей разработки методов решения задач анализа, синтеза и оптимизации обобщенных конечно -автоматных моделей с периодически меняющейся структурой основан на справедливости следующего, доказанного автором в работе [52J, утверждения.

Теорема 4.7. Для любого конечного 72—автомата с периодически меняющейся структурой. Avar, имеющего m состояний и период повторения струкхуры Т, может быть построен конечный 72— автомат с постоянной структурой В, имеющий не более тТ состояний и индуцирующий то же 72-отображение, что и А„аг.

Одним из способов построения 72-автомата В в теореме 4.7 является следующий:

в =< x, В, У, тв, {Rs(x, у)}, qs >, где |В| = тТ,тв •= (г,0,...,0), q™ = (q(0),q(l), ...,q(T - 1)) и Ri(i,y), х € x, у 6 У, есть Слочно-циклические матрицы перехо-доп, ненулевыми блоками которых являются матрицы R(х,у)(т), т = О,Г- 1.

4.7. Нахождение приведенных и минимальных форм /'-автомата Avar■ Пусть 72 = Т и задан конечный /"-автомат с пе-

риодически меняющейся структурой Avar- Требуется построить его инициально (финально) приведенную и минимальную формы. Согласно теореме 4.7 для Avar можно построить соответствующий /■—автомат В. Применяя к построенному /"-автомату В рассмотренную выше матричную процедуру оптимизации, основанную на построении его левой и правой базисных матриц и использовании теорем 4.4-4.6, и переходя затем обратно к коночному /—автомату с периодически меняющейся структурой, можно в результате предложить соответствующий матричный метод непосредственной минимизации самого /"-автомата А„„г [52, 63].

Построение левой базисной матрицы для В показывает, что она имеет блочно-диагональную форму и что для нахождения ее последовательных блоков Нг(т),т = О,Г— 1, может быть сформулирована достаточно простая рекуррентная процедура. Используя нормализованные формы НДт) матриц Н'(г), г = О, Г — 1, можно построить финально приведенную форму _4'1аг /" -автомата «Д^пг следующим образом: A'var =< А', А', У, г', {R'i.r, у)(т)}, q'(r) >, г' = гН^(О), К'(Х,у)(т) = нг(т - l)R(*,»)(r)Hi(r), q'(r) = HP(r)q(r), где Hj(r) -любая матрица, такая, что Hr(r)H£(r) = I.

Построение правой базисной матрицы Н, для В и специальное сведение ее к блочно-диагональной форме также позволяет сформулировать специальную рекуррентную процедуру для построения ее диагональных блоков Н,(г), г = О, Г — 1. Используя нормализованные формы Н,(т) матриц Н,(т),т = О,'Г -1, строится инициально приведенная форма /"-автомата Avar

л;;аг=< A',.4",y,r",{R"(x,!/)(t)},q"(r) >, г" = rHf(0),R»(®,»)(r) = Й,'{т - l)R(x,!/)(r)H,(r),q"(r) = H,'(r)q(r),

где Н'ч{т) - любая матрица, такая, что Н^(г)Н,(г) = I.

Минимальная форма /"-автомата Av„r строится с помощью комбинации данных двух процедур - построения финально (инициально) приведенной формы А'„аг для Атг, а затем инициально (финально) приведенной формы для А'тг.

ГЛАВА 5. Оптимизация иполио определецных стохастических кпнечно-аптоматяых моделей.

5.1. Стохастические автомаги. 7?—автомат (1.1) при И = R, где К - поле вещественныK чисел, будет стохастическим автоматом (р— автоматом) At,r =< X, Л, У, р, {Р(.т,;/)} >, если

г = р = (]>\,!>i, - --¡Рт) ~ стохастический иектор-строка (начальных вероятностей состояний), q = о - вектор-стол&ец, иге элементы которого единицы (и определении автомата Л,„. обычно опускается); {R(.c,i/)} = {Р(ж,2/)} - совокупность матриц вероятностей переходов

Р(х, у) = (Р0{х, (/))„,,„„ Pij{x, у) = Pi(ajy\aix), х е А', у € К .

В этом случае '^„("M') = Pr(uju').

Поскольку для р—автоматов финальный вектор q = е фиксирован, а условия эквивалентности в п.4.1 должны выполняться только для стохастических начальных векторов, то в теории р-автоматов обычно рассматривают лишь их инициально приведенные (в смысле п.4.1) формы, являющиеся также ^-автоматами и называемые (стохастическими) минимальными формами. Соответственно, в теории р— автоматов обычно определяется только правая базисная матрица р— автомата, называемая С-базисной. Одной из основных задач оптимизации р— автомата Apr является построение его стохастической минимальной формы.

Далее в данной главе приведены основные научные результаты автора, содержащиеся в работах [1, 2, 18, 57, 59, 62] и посвященные проблеме минимизации числа состояний р—автоматов и построения их минимальных форм.

5.2. Свойства преобразованных форм ¿-базисной матрицы.

Отметим два простых свойства различных форм представления ¿-базисной матрицы р— автомата Арг.

Лемма 5.1. Если в ¿-базисной (тох^)-матрице Н р— автомата Apr строки hj,, V = 1 ,d, линейно независимы и а-1 = (h,,),,.^, то сумма элементов в каждой строке нормализованной формы ¿-базисной матрицы Н = Но р— автомата Apr равна 1.

Лемма 5.2. Если для строк ¿-базисной матрицы Н р— автомата

Apr выполняется

hs = cfe[0,l], (5.1)

то при любой невырожденной квадратной матрице а размером (dim£ х dim -С) строки преобразованной ¿-базисной матрицы Н = Но р— автомата Арг также удовлетворяют этому условию ha = Ее, h;. VI

5.3. Новый критерий минимальности р—автомата. Теоретической основой предложенного автором нового матричного метода минимизации р— автомата Арг являются следующие доказанные им два взаимосвязанных утверждения [57, 59], устанавливающие новый критерий минимальности р—автомата.

Теорема 5.1. Для того, чтобы в С -базисной матрице Н р—автомата Apr для строки ha выполнялось

= 6, е [о, 1], $> = i,

¥з

необходимо и достаточно, чтобы существовала такая нормализованная форма Н матрицы Н, в которой строка h3 неотрицательна (т.е. не содержит отрицательных элементов) и не входит в выделенное при построении Н подмножество линейно независимых строк.

Теорема 5.2. Для того, чтобы р— автомат Арг паходился в минимальной форме, необходимо и достаточно, чтобы не существовало такой нормализованной формы Н представления его ¿-базисной матрицы, в которой бы наш'лась хотя бы одна строка с неотрицательными элементами, не входящая в выделенное при построении Н подмножество линейно независимых строк.

5.4. Основы матричного метода оптимизации. В хорошо известных методах минимизации р—автомата А,,г, наиболее сложным для выполнения является нахождение строк матрицы Н, удовлетворяющих условию типа (5.1). Кроме того используемый обычно в этих методах процесс последовательного удаления состояний из

р—автомата также усложняет процедур}' мипимизации. Поэтому интересной задачей является построение принципиально нового метода, который сводил бы процесс минимизации р—автомата Арг к однократному применению матричного преобразования вида

р' = рН. Р'(.<\ ;</) = Н'Р(х, у)Н, (5.2)

где Н - некоторая матрица, получаемая из ¿-базисной матрицы Н. Заметим, что для того, чтобы преобразование (5.2) не нарушало стохастичности автомата, достаточно, чтобы матрицы Н и Н' были стохастическими.

Пусть Н = Н] есть ¿-базисная (т х г/)—матрица /»-автомата А11Г и = 1,11, - любая система ее линейно независимых строк.

Пусть а есть (</ х с!)— матрица, такая, что а-1 = (Ь,„),/=р^. и матрица Н| = Н,гу есть нормализованная форма матрицы Нь где строки = 1,(1, образуют единичную ((I х а')—матрицу. Вве-

дем обозначения = {Ь;|1 е {'Л^т/} ■ Щ = $ > О,

г £ {17'»}, J = M}, = |П.|Ь, £ «1 иП1. г£{ТТт}}. Если

"Н.^ — 0. то выбирается другая система линейно независимых строк матрицы Н; и находится другая матрица Нь Если Н* ф то строится специальная матрица следующим образом. Каждая строка Ь, £ Н^ в матрице Н| заменяется нулевой строкой и за,тем для каждой строки Ь; 6 (такой, что г*„ < г < ¿¡,-¡-1, £ И\) ь

матрицу вставляется столбец Ь(г'), Л;(г) = 0, ) ф г, 1ц(г) = 1, между столбцами с номерами и и и-(-1. Новая матрица Н? для следующего шага анализа находится путем удаления из Н| всех строк, таких, что Ь,- £ . Затем анализ повторяется для Нг и так далее. В результате будет получена последовательность матриц Нь Нг,..., Н„ Справедливо утверждение [62].

Теорема 5.3. Пусть -4,,г--=< Л', А, У, р, {Р(./, у)} >, конечный р—автомат, Н - его ¿-базисная матрица и Н|, Н^, • ■ ■, Н„ - последовательность матриц, построенных в результате последовательного анализа матрицы Н для различных систем ее линейно независимых строк. Тогда матрица Н = П"=1 Н, находится в нормализованной форме и в,,Г =< Л', В, У, р', {Р (х, у)} >, где р' = рН, Р'(х,у) = Н'Р(х,у)Н, х £ Л', у 6 У, и Н' - любая матрица, такая, что

Н'Н •= I, есть стохастическая минимальная форма р-автомата Арг.

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

1. Для р—автомата Арг находится ¿-базисная матрица Н.

2. Из р—автомата Apr удаляются эквивалентные состояния (см. п.п. 5.9. 5.10) и получается р— автомат А'рг. Этот этап в принципе

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

3. В соответствии с изложенной в п.5.4 процедурой строятся преобразующие матрицы Н„, ч = 1,?», путем анализа поэтапно преобразующейся ¿-базисной матрицы Н р—автомата А'рг.

4. Строится единая преобразующая матрица Н и, поскольку она находится в нормализованной форме, обычным тривиальным образом находится квазипсевдообратная к ней матрица Й'.

5. С помощью преобразования (5.2) находится Врг - стохастическая минимальная форма р— автомата А,,г-

5.6. Оптимизация р-автомата Арг при заданном начальном векторе р. Поскольку р—автомат Арг есть специальный частный случай обобщенного конечного автомата над полем вещественных чисел, то при заданном начальном распределении вероятностей состояний р для него также может быть определена левая базисная матрица Нг Справедливо следующее утверждение, позволяющее при определенном свойстве левой базисной матрицы производить редукцию (уменьшение числа) состояний р—автомата Арг [62].

Теорема 5.4 Пусть задал р— автомат Apr с т состояниями и Нр есть его левая базисная матрица . Тогда, если столбцы матрицы Hp = (hi, h2,..., hm) обладают свойством h,-„ = a„h,, а„ > 0, v = м, то можно построить р— автомат Арг, имеющий т — d состояний и такой, что для каждого начального распределения вероятностей состояний р автомата Apr, обладающего свойством р,, = а„рч, найдется эквивалентное ему начальное распределение вероятностей состояний в автомате А

5.7. Особенности матрицы Нг. Следующее доказанное автором утверждение содержит необходимые и достаточные условия того, что любая заданная вещественная (т х d)—матрица Н с линейно независимыми столбцами является ¿-базисной матрицей некоторого /»— автомата [50, 02]. При этом его доказательство дает один из вариантов решения новой оригинальной задачи синтеза. Пусть задана такая матрица Н, удовлетворяющая требуемым условиям. Необходимо для заданных алфавитов X, |ЛГ| ; п, и Y, |К| = к, построить какой-нибудь /»— автомат Арг, имеющий т состояний и заданную ¿-базисную матрицу Н.

Теорема 5.5. Если Н = (hi, h-2,.... hj) есть (m х <i)—матрица, d < т. над полем вещественных чисел R, столбцы которой hj, j = 1,</, линейно независимы, и ¿, ¿С R'", есть векторное пространство, порожденное этими векторами-столбцами, то для существования и построения /»—автомата Арг с входным алфавитом Л', |Л'| = п > 1. выходным алфавитом Y. |У| > 2, т состояниями и ¿-базисной матрицей Н, необходимо и достаточно, чтобы е € С.

5.8. Нестохастические минимальные формы Арг. Прямое применение метода, изложенного в главе 4, к /»—автомату может приводить к нестохастическому автомату, находящемуся в инициально приведенной форме и инициально эквивалентного (в смысле обобщенных автоматов) исходному /»—автомату. При этом, если в стохастической минимальной форме р—автомата Арг ¿-базисная (т х <7)-матрица имеет d < т, то обобщенный коночный автомат, полученный из Арг с помощью этого метода, будет иметь d состояний, т.е. меньше, чем стохастическая минимальная форма. Такие нсстохастическис минимальные формы, представления стохастических автоматов, впервые исследованные автором, также могут представлять определенный интерес как специальные нестохастические математические модели стохастических систем конечно-автоматного типа. Основной результат здесь сформулировав автором в следующем утверждении.

Теорема 5.6. Для любого, сколь угодно большого целого т, и любого целого d, 3 < d < m, существуют /»—автоматы, стохастические минимальные формы которых имеют гп состояний, а нестоха-

стичсские минимальные формы - d состояний.

5.9. Проблема редукции эквивалентных состояний. Для

зпотне определенного автомата Арг еще одной задачей оптимизации, обычно предшествующей построению минимальной формы, является редукция (удаление) эквивалентных состояний. При этом состояния (i,-,(!j 6 А р-автомата Apr считаются эквивалентными, если в Apr эквивалентны вырожденные стохастические начальные ректоры р и р', имеющие элемент "1", соответственно, в г—ой (вектор р ) и j-ой (вектор р' ) позициях, а остальные элементы "О". Говорят, что р—автомат Арг находится в приведенной (по состояниям) форме, если он не имеет ни одной пары эквивалентных состояний.

Два р— автомата Арт и А'рг с одинаковыми входным X и выходным Y алфавитами называются эквивалентными по состояниям, если для каждого вырожденного стохастического начального вектора р в Apr найдется эквивалентный ему вырожденный стохастический начальный вектор р' в А'гг и обратно. Любой р—автомат Арг находящийся в приведенной форме и эквивалентный по состояниям р—автомату Apr, называют приведенной формой р—автомата Арг.

В теории р— автоматов хорошо известен общий метод удаления эквивалентных состояний в р—автомате Apr путем построения его ¿—базисной матрицы.Н, выделения в вей подмножеств равных строк и "склеивания" соответствующих этим строкам эквивалентных состояний, который позволяет сводить любой р—автомат Apr к его приведенной форме. Однако, учитывая сложность построения ¿—базисной матрицы Н при большом числе состояний, весьма желательной является разработка иных методов хотя бы частичной редукции эквивалентных состояний р— автомата А,,г , не связанных с построением ¿—базисной матрицы Н. Рассмотрим кратко один из таких методов, теоретически обоснованный и детально разработанный автором в работах [1, 2, 18].

5.10. "Частный метод минимизации р—автомата Apr- Эквивалентным разбиением р— автомата Арг называют разбиение его состояний на классы эквивалентных состояний по следующим правилам: а) все состояния, принадлежащие одному классу, эквивалентны; б) среди состояний, не принадлежащих какому-нибудь из

классов, нет состояния, которое было бы эквивалентно какому-нибудь состоянию этого класса; в) каждое состояние входит в один из классов. Любую приведенную форму »—автомата Арг, которая может быть получена из А,,г с помощью "склеивания" его эквивалентных состояний будем называть естественной приведенной формой р—автомата Л11Г-

Пусть и - любые два подмножества состояний р— автомата А),г- Говорят, что подмножество стохастически замкнуто относительно подмножества и»2, если для любых состояний «¡i,a,2 6 uii выполняется S„j€uj АДх. ?/) = E„,£>J, ДгДж,!/) Для зссх х е У £ Y-

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

Разбиение в состояний р—автомата Арг на непересекающиеся классы, удовлетворяющие условиям: а) все состояния, принадлежащие одному классу, эквивалентны; б) любой класс разбиения стохастически замкнут относительно каждого класса этого разбиения: в) каждое состояние входит в один и только в один из классов; г) не существует разбиения состояний на классы, удовлетворяющего условиям а), б), в) и содержащего меньшее число классов, чем разбиение Ö; назовем стохастически замкнутым эквивалентным разбиением р—ивтомата АрГ.

Справедливы утверждения.

Теорема 5.7. Для того, чтобы р— автомат А,Т имел только одну естественную приведенную форму, необходимо и достаточно, чтобы его эквивалентное разбиение было ого стохастически замкнутым эквивалентным разбиением.

Теорема 5.8. Если 0 = {i?t, i>2, } , Ц " = есть стохастически замкнутое разбиение р—автомата то либо i> ссть стохастически замкнутое эквивалентное разбиение в этого автомата, либо в может быть получено из д объединением в каких либо из классов ¡>[,х>2_____ 0Ч.

Пусть w = {u>i,w2,...,u>,, }, Ц,"« = А* егть какое-либо разбиение состояний р-автомата Арг на непересекающиеся классы. Рассмотрим каждый класс шг. г = l.q, и выделим из него все возможные

подмножества (классы) состояний, удовлетворяющие условиям: а) если о-v,- - выделенное из класса шг подмножество состояний, то uir¡ стохастически замкнуто относительно каждого класса Uj, j = 1 ,<7; б)ссли uT¡ выделено из uir и удовлетворяет условию а), то среди выделенных подмножеств нет подмножества и>г, С uir такого, что оно также удовлетворяет условию а) и ит, Э wrt. Нахождение таких подмножеств путем разбиения каждого класса иг, г = 1,гу, будем называть операцией "расщепления" классов разбиения и.

Теорема 5.9. Стохастически замкнутое эквивалентное разбиение р—автомата Лрг в единственно и может быть построено с помощью применения к начальному разбиению состояний автомата Apr на классы ú>(0) = |wi(0)}, где u.'i(0) = А, конечной последовательности операций "расщепления" классов, приводящей к последовательности разбиений w(0),u(l), ...,cj(/i + 1), h > 0, такой, что если ui(h) = ui(h + 1), то u(h) = ui(h 4- 1) = в.

Согласно теореме 5.9 может быть предложен следующий частный метод минимизации р—автомата Apr : 1) с помощью операции "расщепления" классов из и(0) находится о>(1), затем из ц>(1) находится и>(2) и т.д., пока не будет получено oj(h) = ui(h + 1) = в = {0|,02,...,- стохастически замкнутое эквивалентное разбиение р—автомата Арг', 2) в каждом из классов $„, v = 1 ,</, состояния "склеиваются" и в результате получается новый р—автомат Врг, эквивалентный по состояниям исходному и имеющий д состояний.

Следствие 5.1. Если стохастически замкнутое эквивалентное разбиение ^—автомата Арг содержит д классов, то применение к Арг частного метода минимизации приводит к построению однозначно определяемого р-автомата Bp,, эквивалентного по состояниям автомату Apr и имеющему д состояний

Следствие 5.2. Если р—автомат АрГ имеет только одну естественную приведенную форму, то применение к Арг частного ме-юда минимизации приводит к построению этой естественной приведенной формы.

ГЛАВА G. Оптимизация частичных стохастических конечно-автоматных моделей

Наиболее общее понятие о частичных р— автоматах впервые было введено автором в работах [28. 36]. Проблема оптимизации автоматов этого типа впервые исследована автором в работах [2, 29], где обоснован один из возможных методов редукции состояний.

6.1. Частичные стохастические автоматы (2, 28, 36]. Обозначим V"' - множество всех стохастических т— мерных векторов и Р'"" - множество всех стохастических (т х п) матриц. Любое непустое подмножество р множества 'Рт, р С Т'", назовем частичным стохастическим/ вектором (частичным р—вектором), а любое непустое подмножество Р множества J""'" - частичной стохастической (in X /г) - матрицей (частичной р—матрицей).

Частичный стохастический автомат, (частичный р— автомат) есть система Л,,г =< X, Л. У, p. |p(j', у) J- >, где р— частичный р-

вектор, |Р(х, í/)J-, х £ Л', ц £ У, - совокупнос ть ¡ik частичных (т х т)- матриц переходов, такая, что образованная из них клеточная матрица "Р = (P(x¡, Ui))n,k является частичной /»—матрицей. Система Арг задает множество вполне; определенных р—автоматов, такое, что А],,. =< Л',.4,1",р, (Р(х,у)} >е Арг р € р. Р(х,у) 6

Р(х,у), х € Л', у б У. Под частичным стохастическим отображением <I> j , индуцируемым частичным /»-автоматом Арг, понимается

множество отоб]>ажений. индуцируемых автоматами Арг С A¡,r-

6.2 Проблема оптимизации частичного />—автомата. Два

частичных /»—автомата А,,г и .4¡,r, имеющие одинаковые входной Л* и выходной V алфавиты, назовем эквивалентными по состояниям, если для каждого /»—автомата А,„■ 6 А,,г найдется эквивалентный ему по состоянием /»-автомат А'рг 6 А'рг и обратно. Будем говорить, что частичный р— автомат Арг находится в приведенной форме, если все /»—автоматы Арг € АрТ находятся в приведенной форме. Принед/ иной формой частичного /»—автомата Арг назовем любой (в общем случае частичный) /»—автомат, находящийся в приведенной форме и эквивалентный по состояниям какому-либо

автомату А'р, С ,4?г.

Одна нз основных задач оптимизации р— автомата Apr состоит в построении (в общем случае частичного ) р—автомата В„г, имеющего по возможности меньшее число состояний и эквивалентного по состояниям какому-либо автомату А'рг С А,,г, (в том числе приведенных форм автомата Apr-)

6.3. Совместимые разбиения частичного ^-автомата [2, 29]. Совместимым разбиением частичного р—автомата Арг называем такое разбиение П его состояний на классы, когда найдется р—автомат Apr 6 Apr, для которого О будет эквивалентным разбиением, причем нет автомата ,А!?Г 6 Арг, для которого его эквивалентное разбиение может быть получено из О с помощью объединения в О каких-либо классов.

Стохастически замкнутым совместимым разбиением частичного р— автомата Арг назовем такое разбиение в его состояний на непересекающиеся классы, которое является стохастически замкнутым эквивалентным разбиением для какого-либо частичного (возможно вполне определенного)р—автомата А'рг С Apr, и нет такого автомата Apr Q Apr, стохастически замкнутое эквивалентное разбиение которого может быть получено из б с помощью объединения в в каких-либо классов. Стохастически замкнутое совместимое разбиение частичного р—автомата Apr в общем случае существует и может быть не единственно, но число таких разбиений конечно.

6:4. Операция "склеивания" состояний. Пусть Apr есть частичный р—автомат, имеющий т состояний, такой, что в каждом вполне определенном автомате Apr 6 Арг состояния а,-,, о,-„ ...о,-, эквивалентны. Тогда результат операции "склеивания" эквивалентных состояний в частичном р—автомат Арг - это частичный р—автомат А'рг, включающий в себя те и только те р— автоматы, которые получаются чз всех Apr € APr путем "склеивания" этих эквивалентных состояний известным в теории р—автоматов способом.

Если в Apr какие-либо состояния а,,,а,,,...а|( совместимы, т.е. существует подмножество Арт С Арг р— автоматов, в которых эти состояния эквивалентны, то частичный р—автомат В^,, получаю-

щийся в результате "склеивания" эквивалентных состояний в А'^., назовем также результатом "склеивания" совместимых состояний а,,,о,,, в частичном р—автомате Арг-

6.5. Операция "расщепления" классов [2, 29].

Пусть w = {¡¿i,uj-2, ...,^'д}, U„a/„ = А, есть какое-либо разбиение состояний частичного р—автомата Apr на непересекающиеся подмножества (классы). Будем говорить, что разбиение

и' == {u>ii,...,W||,.,Wji,...,U2/„...,W4/t}

состояний частичного р—автомата Apr на непересекающиеся подмножества (классы) есть результат операции "расщепления" подмножеств (классов) разбиения и, если выполняются условия: а) ш,- = 14,0^. 1 = 1,5; б) существует Арг € Арг, такой, что в нем каждый из классов j = 1,/,-, г = 1 ,q, стохастически замкнут относительно каждого класса разбиения в) если

О = {«?„,..., 1?1в„ дп,..., О,..г} ¥> ^

есть разбиение состояний частичного р—автомата. Apr на непересекающиеся классы, такое, что и, = t = 1,17, и для каждого класса и = 1,4,, i = 1,17, существует такое подмножество индексов сг;„ С {1,2,...,/,}, что i);„ = Ujg»,, ^o'i т° Для каждого р—автомата 6 Apr найдется такая пара классов (i?„,,uv), l?,«. S t?, шг £ a;, что не будет стохастически замкнут относительно иг. В общем случае результат операции "расщепления" классов разбиевия и) неоднозначен и может существовать конечное число различных разбиений, удовлетворяющих условиям определения операции.

6.6. Метод редукции совместимых состояний [2, 29]. Справедливы утверждения.

Теорема 6.1. Если и есть такое разбиение состояний частичного автомата Apr на непересекающиеся классы, что разбиение и>', являющееся результатом операции "расщепления" классов разбиения и, удовлетворяет условию а/ = uf, то либо и есть стохастически замкнутое совместимое разбиение в автомата Apr, либо разбиение в может быть получено из ш путем объединения в ui каких-либо классов.

Теорема 6.2. Пусть Apr есть частичный р— автомат и в - какое-либо его стохастически замкнутое совместимое разбиение, тогда найдется такая последовательность tf'0', i)'1', ...,i)(h\ h > 1, разбиений состояний автомата Apr на непересекающиеся классы, что = |i/|0)| , = Л, каждое разбиение есть результат операции "расщепления" классов разбиения й'1-1', i = l,h, и =

tfW = в.

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

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

1. Применяя конечное число операций "расщепления" классов к начальному разбиению = • = А, где А алфавит состояний частичного р— автомата Арг, найти всевозможные последовательности разбиений t)'1',..., й'4', такие, что tf'1' есть результат " расщеяления" классов разбиения сЗ'1"1', i = 1,/t, и = (значение h в разных последовательностях может быть разным).

2. Из полученных в п.1 окончательных вариантов разбиения оставить те, которые путем объединения в них каких-либо классов не сводятся ни к одному из окончательных вариантов разбиения и согласно теореме 6.2 являются различными стохастически замкнутыми совместимыми разбиениями частичного р—автомата Apr-

3. Для каждого^оставленного в п.2 разбиения построить частичный р—автомат Врг, являющийся результатом "склеивания" всех совместимых • состояний внутри каждого класса разбиения. При этом будет построена некоторая конечная совокупность частичных р-автоматов Врт, i — 1,</, для каждого из которых найдется эквивалентный по состояниям частичный р—автомат С Apr, i =

4. Среди частичных р—автоматов Bp), i = l,g, выбрать автоматы с наименьшим числом состояний (при необходимости п.п.З,

4 можно объединить и строить только те автоматы 1Ур} , которые имеют наименьшее число состояний, выбрав для этого в п.2 те разбиения, которые включают наименьшее число классов).

Справедливо следующее утверждение относительно эффективности подобного частного метода.

Теорема 6.3. Если г = 1,о, есть всевозможные частичные р—автоматы, полученные применением п.п. 1-3 частного метода минимизации к частичному р-автомату Арг, то:

а) для того, чтобы среди них нашелся автомат, имеющий т' состояний (i)i' < т), необходимо и достаточно, чтобы существовало стохастически замкнутое совместимое разбиение частичного р—автомата, Арг, содержащее т' классов;

б) если Bp), г - 1,<?, имеют соответственно по m„ i = 1, гу, состояний, то min m; = min d(ApT), где d(Apr) - число классов в етохасти-

елрг

чески замкнутом эквивалентном разбиении вполне определенного р—автомата .4рг;

в) для того, чтобы среди автоматов

i = l,g, нашелся хотя

бы один автомат, являющийся приведенной формой частичного р—автомата Арг, необходимо и достаточно, чтобы нашелся такой вполне определенный р—автомат Арг 6 Арг, который имеет только одну естественную приведенную форму; при этом его эквивалентное разбиение есть одновременно стохастически замкнутое совместимое разбиение частичного р—автомата Арг;

г) автомат Bp'J, i £ , не будет приведенной формой исходного частичного р-автомата Apr в том и только в том случае, если найдется вполне определенный р—автомат

т

6 не находящийся в приведенной форме, причем в этом случае р—автомат flj? имеет более чем одну естественную приведенную форму.

Для практической реализации предлагаемой схемы в каждом конкретном случае применительно к частичным р—автоматам какого-либо вида необходимо дать конструктивные методы выполнения операции "склеивания" совместимых состояний и операции "расщепления" классов автоматов этого вида (аналогично тому, как это сделано в п.5.10 для вполне определенных р—автоматов).

ГЛАВА 7. Минимизация частичных стохастических ¿—автоматов.

7.1. pi—автоматы. В работах [28, 36] автором были впервые определены частичные р—автоматы следующего специального вида. Частичным стохастическим г—вектором (pi—вектором) назовем подмножество стохастических векторов р С Р'", такое, что

Р = |р|р = (ры>2.....рт), Pi 6 = I Oj,bi I С [0, l],5j ф 0, ]Гр, = l|.

Такой р«-вектор задается в виде р = (ст|, cr2l ...,сгт), где

А _

5, = | а¡,6, |С [0,1], ¿г; ^ 0, i 1,т, а условие ^¡р, = ] опущено

и,

как очевидное. Считается, что р»—вектор корректно задан, если для каждого pj 6 Oj найдутся pi 6 ст,. i ^ .7, такие, что YZs=iP> ~ 1 (j = 1, m). Соответственно pi—матрица есть подмножество Р С такое, что

р = |р|р = (Pij)m,n, P,J е дц = \ ац,Ъц "\с [0,^ = i J,

и задается в виде P = (j,j)m,„, где <7(J = | | С [0,1],5у ^ 0,

__<м

.и условия Pij = l,i — 1,7«, опущены как очевидные. Считается, что pi—матрица корректно задана, если все ее строки есть корректно заданные pi—векторы.

Частичный р—автомат Луг =< X, Л,У,р, >.такой, что

р есть корректно заданный pi—вектор и матрица P = yt))n,t

есть корректно заданная pi—матрица размера пт х km, назовем pi—автоматом. В работах [2, 37, 44] автором обоснован способ практической реализации рассмотренного в главе 6 частного метода минимизации применительно к pi—автоматам, для чего исследован ряд свойств pi—векторов.

7.2. Операция корректировки. Следующее утверждение устанавливает необходимые и достаточные условия корректности задания рг-векторов (и соответственно pi— матриц, /»¡'-автоматов).

Теорема 7.1. Для того, чтобы pi—вектор р = (cti.uj, ...,?„,), где

Д 0. _

<7; = | а., Ь, | ф 0, | а;, 6,- | С 0,1, 1 = 1, т, был корректно задан, необ-

«,■ а,-

ходимо и достаточно, чтобы для всех j = 1,?п выполнялись условия: а) ау > 1 - причем

а, = 1-]ГЬ; к ßi = 0=^^=0;

■'¡У

б) bj < 1 - 12,¿j "п причем

= & Эг-.гф^, <Yi = Ö=i-/3j=0.

■W

Процедуру нахождения корректно заданного ^¿-вектора р, содержащего все те и только те стохастические векторы, которые принадлежат заданному t—вектору г будем называть операц ией корректировки вектора г и обозначать р = Cor t. Для построения данной процедуры существенны следующие утверждения.

__ 7.

Лемма. Для того, чтобы в ¿-векторе г = (| a,d{ |),-т^> содер-

<г,

жался хотя бы один стохастический вектор, необходимо и достаточно, чтобы выполнялись условия:

а) < 1, причем = 1 => crj = 1, где <~| = с,-, п\ = сг, при с,- > 0 и cj = 0, сг- = 1 при с,- < 0;

б) dj > 0 для всех t, ^ причем = 1 ъ — 1.

7.

Теорема 7.2. Пусть t-вектор г = (| с,-, d,- | удовлетворяет

<fi 1 1

условиям леммы и пусть ? = (|u,,v; |)Т77Г есть t—вектор такой,

что

(I «i,W| |) = (к,-,4 |')П[0,1], i =

тогда pt—вектор

p=»(|«,.M)bU, (7.1)

А А'_

где | «,Д | aj, Ь,- |С [0,1], i = 17", будет р = Cor г в том и

только о том случае, если при всех j = 1,п

bj — min(i.'j, 1 — ^ "¡)i aj = max(uj, 1 — ^ 6,), W W

ßj = 0 (6,- = Vj) к (£j = 0) V (by = 1 - ¿2 «,) <k 3« ф j : <5, = 0,

¡fi

a}- 0 <=* (aj = Uj) Sc (6j = 0) V (a; = 1 - 6,-) & 3» # j : Д = 0.

Используя лемму и теорему 7.2 можно для заданного г—вектора г найти pi-вектор р = Согг.

7.3. Редукция рг-векторов. Пусть р = (pi,p?, •■■,/'„) есть вполне определенный стохастический вектор и П = (П],П2,...,Пд), д < п, есть разбиение множества индексов {1,2, ...,п} на q непересекающихся непустых классов Ujfly =г {1,2,...,п}. Тогда стохастический 9-мерный вектор р' = (Eigßj Pi)j=T^ ®УДем называть результатом редукции вектора р по разбиению П и обозначать р' = Red р. Результатом редукции частичного р—вектора по разбиению П условимся называть частичный р—вектор

р' = Red р = |р'|р' « Red р, р 6 р} .

Справедливо следующее утверждение.

Теорема 7.3. Если р есть pi-вектор (7.1) и О = (QUQ2,...,Q,), Ч й есть разбиение множества индексов {1,2,..., п} на q непересекающихся непустых классов, UjQj — {1,2, ...,п}, то

v

р1 = Red р = Cor (| cj,dj I

где су = S "(> di — X) '>•> ai ~ & «» 7i ~ & A-¿en, 16% iesij .'en,

7.4. Метод минимизации. Для того, чтобы построить практическую реализацию рассмотренного выше частного метода минимизации применительно к pi-автомату Лрг, достаточно дать конструктивные методы выполнения операции "склеивания" совместимых состояний и операции "расщепления" классов для рг-автома-тов, для определения которой важно следующее утверждение.

Теорема 7.4. Если

есть корректпо заданные рг-векторы, то для того, чтобы существовал р£-вектор р, такой, что р С р'"' для всех и, необходимо и достаточно выполнение условий

(") ^ • 1 (у) * 1 таха- ' < ттк , I — 1 ,п;

I/

^таха^ < 1 < ^ттЬ^;

I I

(<4'> = шаха'"') & = штЬ?"' V ^таха)"' = 1) = 1;

(b\'} = inin b\v)) к (bf = max а;"' V ^тщ^1 = 1) :

Операция "расщепления" классов. Пусть состояния автомата Арг разбиты на непустые непересекающиеся классы иi,ui¡¡, U¡u¿ =

A, {oíi,a?2, •••!= w. При этом будем считать, что в соответствии с и в подматрицах Р(s,l) = P(x,,yi) выполнена симметрическая перестановка строк и столбцов так, что сначала идут строки (столбцы), соответствующие состояниям класса u>¡, затем и т.д., а также произведено симметрическое их разбиение, т.е. подмножества строк (столбцов), соответствующие классам j = 1,ij, отделены друг от друга пунктирными линиями. Обозначим pî-вектор

P,(s) = 1). Ра(», 1), - . Ч. 2), -, fe;;

и найдем pi-векторы P!(s) = RedP¡(s), « = l,m, s = l,n.

w

Определим различные Способы " расщепления" классов u>¡ на максимальные непересекающиеся подмножества состояний по правилу: состояния ait,an,...,au е uj¡ могут включаться в одно подмножество, если для pí-векторов P^(s), v — 1, ci, выполняются условия теоремы 7.4 при каждом s. Из различных комбинаций способов "расщепления" классов ui¡, j = исключим лишние согласно п.в) общего определения операции "расщепления". Оставшиеся

варианты и будут различными разбиениями, которые являются результатом "расщепления" классов разбиения и. Для каждого такого варианта производится симметрическая перестановка и симметрическое разбиение подматриц P(s, /).

Операция "склеивания" состояний. Пусть для Лрг получено какое-либо разбиение П = {fii.iîj, ...,ПГ} его состояний на непересекающиеся классы совместимых состояний, и в подматрицах P(s,i), s = l,n, I = l,k, в соответствии с П выполнены симметрическая перестановка и симметрическое разбиение строк и столбцов. Построим pi—автомат BpT =< X, В, У, р', |q(s, ¿)| >> являющийся результатом

"склеивания" в Арг совместимых состояний в каждом из классов fl„, v = 1,г. Для этого в матрицах P(s,i), s = l,n, î = l,k, группы строк (столбцов), соответствующие классам разбиения Cl, обозначим символами b\,l>2,...,br, и в каждой клетке, образованной разделительными линиями групп, вместо входящих в нее элементов запишем один элемент Qij(s,l) (для строки 6,- и столбца bj ) вектора Qj(s) = (Qij(s, O)j=T7,î=0) который определяется по правилу '

Q;(S) = Cor( п

где есть элемент pi-вектора P'}(s) = Red P„(s), соответ-

ствующий Пу и у/. В результате получим подматрицы Q(s,l), s = l,n, / = 1, k, pi-автомата Bfr. Начальный рг'-вектор p' находится из соотношения p' = Red р.

Введенные операции "расщепления" классов и "склеивания" состояний определяют способ практической минимизации pi—автоматов. Пример использования этого метода дан автором в работе [2]. Подобная прикладная интерпретация общей схемы частного метода минимизации может быть построена и для некоторых других «-пециальвых типов частичных р—автоматов, например, для d~автоматов [2, 42].

ГЛАВА 8. Проблемы и методы помехоустойчивого доопределения частичных конечно-автоматных моделей.

Среди прикладных задач математической теории конечно-автоматных моделей существенное место занимают вопросы их надежностного анализа и синтеза. В работах автора [1, 2, 4, 7, 8, 10-17, 19, 20, 22-24, 31] исследованы два типа задач подобного рода, основанных на понятии "помехоустойчивости" автомата, и предложен ряд новых, оргинальных подходов, методов и алгоритмов.

8.1. "Внешняя" помехоустойчивость автомата. Задачи первого типа связаны с исследованием "внешней" помехоустойчивости детерминированного автомата Ам < т.е. с учетом тех нарушений в функционировании этого автомата, которые происходят из-за внешних помех, воздействующих на его вход и искажающих поступающие на автомат входные символы, пе затрагивая его внутренней структуры.

Общая формулировка задач подобного рода следующая.

Пусть задан частичный детерминированный автомат

- Aiet=< А',Л,У,а,{б(«,о} >,

где X = {¿го.хь — ,Xn-i}, А = {а0,вь...,am_i}, У = {уо>Уь—>î/*-ib такой, что для каждого состояния a¡ g А множество номероз его входных символов разбивается на два непересекающихся класса: {*<') и {.5('»}0 - соответственно классы номеров допустимых и запрещенных для а,- входных символов, причем элемент D¡j(s,l) полностью определен, т.е. равен 0 или 1, если s 6 > и не определен, т.е. D¡j(s,¡) = {0,1} , если s € {«(,'}0- Пусть для символов из X заданы распределения вероятностей их поступления при различных состояниях автомата

= .....#42-«). («л)

где /х!'' = Рг(х,|а,) , причем символ х, считается запрещенным для состояния а,- , т.е. я G . если = 0.

Предположим, что заданный частичный автомат Ajei доопределен каким-либо образом, в результате чего получился вполне определенный автомат Adet =< X,A,Y,d, {D(s,Z)} >€ Aja.

Пусть между источником символов х, £ X и автоматом А,ы включается ненадежный канал связи Uw =< А', Л', U >, тогда суперпозиция Urr и A,ui окажется вероятностным автоматом

A„r =< X,A,Y,d,{P(s,l)} >, где PtJ(s:l) = YZ'J^Ms',1).

Полученный автомат Лрг при сравнении с автоматом Ada можно оценивать по степени его "схожести" с Ам, которая и будет характеризовать "внешнюю" помехоустойчивость автомата Ada в заданных условиях. Условимся оценивать качество доопределения автомата Ам при заданном канале связи Ufr с помощью величин Рср (средняя вероятность "правильного" срабатывания автомата Ayr в течение одного такта) и Р,„ш (наименьшая из возможных вероятностей "правильного" срабатывания автомата Apr в течение одного такта) и будем их называть соответственно средней и минимальной помехоустойчивостью автомата Adet в данных условиях.

Тогда рассматриваемые задачи можно сформулировать следующим образом. Заданы частичный автомат Adet и ненадежный канал связи ирт\ требуется найти автомат Ajei в Ajtt, характеризующийся в данных условиях максимальной величиной РСр (при заданных вероятностях (8.1)) или максимальной величиной Р„„„.

8.2. Доопределение частичных автоматов без памяти по мак-симомуРСр [1, 2, 15]. Рассмотрим сначала частный случай первой задачи: заданы частичный автомат без^памяти Cd,_t —< X, У, D >, такой, что Da £ {0,1} при s £ {я}(1 и Ä; = {0,1} при s £ {б}0, и ненадежный канал связи Upr =< Л', Л', U >. Для символов из X заданы вероятности их поступления р, , s = 0, п — 1 , где ц, = 0 в том и только в том случае, если s £ {s}0. Требуется найти автомат Cda —< X, У, D >, Cdti € Cdch имеющий максимальную среднюю помехоустойчивость в заданных условиях. Решение данной задачи дается следующим утверждением.

Теорема 8.1. Для того чтобы при'заданных выше Cjei, Upr, и ц автомат £ Cdet имел наибольшую величину Рср среди автоматов множества Cdet , необходимо и достаточно, чтобы для каждого а' 6 {s}„ выполнялось: если Оц* = 1, то при всех '

MO« Е ^и.,>mi) = Y,

*№))„ «е(»(0)„

где WO}„ = {»|«e W„.JD./ = l}.

Алгоритм доопределения автомата С da , приводящий к шах Р,р в заданных условиях, будет следующим: а) множество определенных строк {л}1( матрицы D разбить на классы одинаковых строк {4C)}(ii ! = 0, к — 1; б) для каждой неопределенной строки «' £ {s}0 матрицы D найти величины А.,>(/) для всех I, которым соответствуют непустые классы {•«(')},,, и положить J9,.;. = 1 для любого одного из /', дающих тахА^(/), и Д//'= 0 для всех остальных /, в результате будет получена матрица D искомого автомата C,iet; в) с помощью выражений Psi = l0U„'Ds'i, Л"ая = Д/Af найти величины для всех s € {.s}(1 и затем из выражения Рср = «Р"ал определить Рср автомата C<ie(.

8.3. Почти надежные двоичные входные каналы [1, 2, 15]. Рассмотрим практически интересный частный случай задачи, когда автомат С,;е1 имеет конечное Число д элементарных Двоичных входных каналов и ненадежный канал связи состоит из отдельных независимых двоичных каналов. Для каждого 1-го двоичного канала связи задана вероятность ;>,-„ правильной передачи символов, зависящая от номера канала i и от поступающего ва него символа я,- £ {0,1}. При этом считается, что вероятности р,„, i = 1,д, Si £ {0,1}, очень близки к 1, а символы х, £ X перенумерованы так, что в двоичной Записи s = (sg, Sj_j, ...,si).

Представим вероятности ри, в виде />„,. = 1 — titiS, г = 1 ,д, si £ {0,1}, где 6 - величина, близкая к 0 и одинаковая для всех г и s. Оценим среднюю помехоустойчивость автомата С,ш £ при 6, близких к 0, для чего рассмотрим величину Тч, = lim1 "fcp, учитывая, что в этом случае

Рср « 1 - Гср<5, (8.2)

и будем искать автомат Cid 6 Cjet, имеющий minTtp, Решение данной задачи дается следующим утверждением.

Теорема 8.2. Для того чтобы при заданных выше C</„(, ft и £/рт с. почти надежными двоичными каналами автомат С ¿а üCje t имел минимальную величину Тср среди автоматов множества Cj,i, необходимо и достаточно, чтобы для каждого s' £ {.?}0 выполнялось:

53

если D^t — 1, то при всех I

пАП= /'Л«, ^ пЛ1) = v.tj,,,

где o(s',/) есть подмножество всех s из {«(Ol^i двоичная'запись которых отличается от двоичпой записи s' только в одном из разрядов, и j = ](з) номер этого разряда^

Алгоритм доопределения автомата С,ut в случае почти надежных двоичных каналов связи будет следующим: а) множество определенных строк {в} матрицы D разбить на классы одинаковых строк {•Ч')}р> ' = О, А: — 1: б) для каждого s' 6 {s}0 и каждого класса {«(i)}^ найти подмножество cr(s',f), такое, что s е <r(s',i), если s 6 {«(')},, и двоичная запись s отличается от s' только в каком-либо одном из разрядов; в) для каждого s' 6 {s}0 найти величину 'ls{l) для всех I, которым соответствуют непустые подмножества <r(s',i), и положить Dg'p = 1 для одного из V, дающих laax^(i), и D,n = 0 для всех остальных I; г) С помощью выражений

T'V = Ц Ya »¿»I

J6(«)„ » ееф',1)

и (8.2) найти Тср и Рср.

8.4. Доопределение частичных автомахов общего вида по максимуму Рср. Справедливо следующее утверждение

Теорема 8.3. Задача доопределения рассматриваемого частичного автомата Adel =< X, |d(s,/)| >, |Д| = т, при заданных l/рт, ß с целью получения тахРср сводится к задаче независимого доопределения m частичных автоматов без памяти = < А', А х У, G(t') >, г = 0, !.. — 1, с матрицами переходов

G(.') = (Ö,(s,0)^, (8.3)

где Di(s,l) - строка матрицы D(s,f), соответствующая а,- € А.

8.5. Доопределение частичных автоматов без памяти so максимуму Pmj„. Пусть для частичного автомата Cjei =< X, У, D >, (см. п.8.2) требуется найти автомат Cjrl € Cjrll имеющий максимальную величину РтЫ в заданных условиях.

В работах [1, 2] показано, что данная задача сводится к следующей частично целочисленной задаче линейного программирования: найти значения элементов Д,;, « 6 {•■»}(,, / = 0, к - 1, максимизирующие функцию Рт-,„ = у при ограничениях

XI я^ми* -у>-Р., яе {«}„, д., = 1, д, е {о, 1},

где = I, при котором Д,| = 1, и величины

и„. 52 АчД,, * € {*}„ ,

«'<И»)„ 1

не зависят от способа доопределения автомата .

В случае почти надежных двоичных каналов Р,пш ¡а 1 — Ттлх6 и задача доопределения автомата С,ц сводится к задаче целочисленного линейного программирования: найти значения элементов Д„/, з £ {¿"}0, / = 0, к — 1, минимизирующие функцию Ттах — у при ограничениях

У Г Ц - * 6 {в},,>

УелМ ¿-1

32 Д, = 1, Д,(€{0,1},

/=о

где и

Л(») = 0> © € {«)„} ,>„(•) = {Л* в е {*}„}.

8.6. Доопределение частичных автоматов общего вида по максимуму Ртш [1, 2]. Справедливо следующее утверждение.

Теорема 8.4. Задача доопределения рассматриваемого частичного автомата Аны —< X, Л, У,<1, >, = т, при заданном и^ с целью получения тах Рт;„ можно свести к задаче независимого доопределения тп частичных автоматов без памяти = < А',Л х У,ё({) >, I г= 0,т~ 1, где матрицы (¡(г) имеют вид (8.3).

8.7. Доопределение частичных функций алгебры логики. Пусть заданы частичная функция алгебры логики / = /(х], ..-,х„, ••■,£*) от п аргументов и к параметров, распределение вероятностей различных комбинаций правильных значений аргументов

Рг(Л'5) = /!5, 5 = 0,2"-1, = (х„ = ...,х, = «,),

П ¡=1

и Рщ - вероятности сохранения правильных значений аргументов х;, I = 1 , п, зависящие от номера аргумента и его правильного значения х; =

_ Пусть / = {/ьЛ,— ,/т} и рассмотрим какую-либо функцию / 6 /. Пусть Лг.9 есть совокупность правильных значений аргументов, а Х& - совокупность искаженных значений аргументов. Будем считать, что значение функции / на наборе Х$> является правильным, если оно совпадает со значением хотя бы одной функции из / на правильном наборе А'.у. Помехоустойчивостью (средней) Рср частичной функции алгебры логики / назовем вероятность сохранения функцией / 6 / правильного значения при заданных /15, 5 = 0,2" — 1, и рип «,• € {0,1}, г = 1 ,п. Естественно, что Рср есть в общем случае величина переменная, зависящая от выбора функции / из /, т.е. от способа доопределения функции /.

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

которые дают Рт&х — я^&гсгРср, РтЬ = нип^.Рср, и определить величину Л'ср = |~р'"Г1, показывающую, насколько чаще при наихудшем варианте доопределения будет возникать ошибка значении функции по сравнению с наилучшим вариантом доопределения.

В работах [2, 16, 22, 31 ] автором с помощью метода вероятностной "логики [1, 14] найдено общее аналитическое выражение для Рср, зависящее от параметров {у, ] = 1, к и предложен следующий алгоритм решения сформулированной задачи:

а) Найти с.д.н.ф. функции /

7= V ыь.ь.

s=о

где х- = Xi, х? = х,-, и разбить множество всевозможных наборов значений аргументов {5} = {0,1,..., 2" — 1} на следующие три подмножества:

{5},-= {S|5 g {S} , const},

{s}0 = {SIS е {S}, .....(,) = fl},

{5}, = {S\S 6 {5} , ps(f,ft) si}.

б) Найти

pi= 'is+ E £ £ ^çs'/'y-

в) Для каждого S' £ {S},, подсчитать величины

то = tWs, CTi = 51

отметив их функциями и соответственно.

г) Построить логико-арифметическое выражение

■«•ад»

упростить его с помощью преобразований

о/+ 6/= (п + Ь)/, a(fVV>) = afVaftp,

fa + (b — «)i3, еслн а < b, aip + bç — i , ; , ' Г,

I 6 -f (a - 6)v, если a > &,

где a, 6 - арифметические коэффициенты, f,<p,(p - логические функции парметров j = 1, к, и привести Рг к виду

^ = ^ + (8-4)

У

где Pj - часть постоянной составляющей, выделенной из Р2 в результате преобразований, Ф„ - элементарная конъюнкция параметров, а d„ - арифметический коэффициент при Ф„.

д) Используя (8.4), найти значения суммы d> = ФЛ ПРИ Разных значениях параметров.

с) Найти Pm„ = Pi + l^+maxcij, Ртт = Py+P^+mmdf и, подставив i _ i __

соответствующие значения параметров в /, найти /тах и /,„;„ из

выражений

/тах= V

/т.п= V /О1!.---,*..,6, {£{„„„

где ?„,„ = |f'|i' € {0,1.....2* - 1} , d(. = max^j ,

£„;„ = ji'li' С {0,1, ...,2* - 1} , dc = miii^l.

ж) Найти A'c,.

8.8. "Внутренняя" помехоустойчивость автомата. Проблемы второго типа связаны с исследованием "внутренней" помехоустойчивости автомата, т.е. с учетом тех нарушений в его функционировании, которые происходят из-за помех, воздействующих на внутреннюю структуру автомата. Это воздействие проявляется в возникновении случайных "сбоев" при функционировании элементов, образующих структурную схему автомата. Задачи этого типа в общем виде формулируются следующим образом.

Пусть задан детерминированный конечный автомат Ada и его структурная схема в виде некоторой правильной композиции конечного числа q детерминированных конечных элементарных автоматов Аj^j, v = l,q. С учетом возможных случайных "сбоев" функционирование каждого элементарного автомата будет уже носить не детерминированный, а вероятностный характер. Пусть каждому детерминированному элементарному автомату сопоставлен вероятностный конечный автомат Арг\ описывающий соответствующий ненадежный элементарный автомат. Заменим в композиции детерминированные элементарные автоматы А^ на ав_ томаты .Apr\ v — 1 ,q. При этом исходная композиция детерминированных элементарных автоматов преобразуется в соответствующую композицию вероятностных автоматов, результатом которой

является некоторый вполне определенный вероятностный автомат Лрг. Сравнивая автоматы А^г и А,,г, можно оценивать по степени их "схожести" "внутреннюю" помехоустойчивость автомата Аы при заданной его структурной реализации. Учитывая же, что для каждого автомата Ам. как правило, может Сыть предложено несколько вариантов его структурной реализации, равноценных по другим критериям (например, по числу элементов), подобный анализ позволяет решать задачу выбора более оптимальных вариантов.

8.9. Анализ "внутренней" помехоустойчивости автомата.

Пусть структурная схема автомата без памяти С',;г( построена из к логических элементов, имеющих по одному элементарному выходному каналу, упорядочена по ступеням и описывается ступенчатой системой функций непосредственных связей

где У] соответствует j—му выходному элементарному каналу автомата. Пусть для каждого логического элемента //, = //,(«/,, , "/¡,, ..., заданы вероятности его правильной работы в данном такте при различных комбинациях входных сигналов на элемент

где г = 2""'г„, г„ 6 {0,1} и оЛ е {0,1}, причем щ = 1 соответствует событию "элемент fi, в данном такте работает правильно". Требуется найти матрицу вероятностей выходов Р реализуемого этой схемой вероятностного автомата С,,г, и соответственно величину Рср (при заданном /< ).

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

Vj = fk+i-j, j - Mi,

h = 1Д-,

енной из к логических элементоз, приводит к выражению вида

Г-1 2'-1 к

s=o j=о Л=1

где J = X^Ji-i Ja 6 {0,1}, причем j/, = 1 соответствует пра-

вильному срабатыванию элемента /л , а jh — 0 - его неправильному срабатыванию (сбою); г = r(S,h,J) соответствует входной комбинации на элементе /а, получающейся при комбинации S входных сигналов на входных каналах схемы F и комбинации J правильной и неправильной работы ее элементов; применено обозначение (р)1 = р, (р)° = 1 -р; Dsj 6 {0,1}, причем Bsj = 1, если схема F при данных 5 и J выдает правильные сигналы на всех своих m выходных каналах, и Bsj = 0в противном случае.

Надежностный анализ структурной схемы автомата позволяет оценить влияние случайных ошибок элементов схемы на ее работу в целом. Однако практическое применение общих методов решения этой задачи встречает ряд трудностей, среди которых отметим сложность (громоздкость) процедуры полного вероятностного анализа "широких" схем, что делает необходимым применение ЭВМ [21, 40], и отсутствие требуемых вероятностных характеристик элементов, учитывающих зависимость надежности срабатывания элемента от поступающих на него входных сигналов. В то же время при решении целого ряда задач синтеза автоматов бывает достаточно лишь указать, какой из предложенных вариантов построения структурной схемы характеризуется большей устойчивостью по отношению к случайным сбоям элементов без подсчета абсолютной величины Рср.

8.10. Приближенный "равнительный анализ вариантов структурной реализации автомата [1, 2, 17]. Пусть заданы два варианта структурной реализации некоторого автомата без памяти в виде структурных схем F и F\ имеющих до п входных и ш выходных двоичных каналов и построенных соответственно из к и к! логических элементов. Представим вероятность р/,г правильной работы элемента в виде p/,r =г1 — где S еАгь величина, близкая к 0, а thr - отношение вероятности ошибки элемента fh при входной комбинации г к выбранной величине 6. Пусть для эле-

ментов схем F и F' известны эти относительные величины и для схем F и F' задано распределение вероятностей /i.s', 5 = 2" — 1, поступления различных комбинаций входных сигналов xi,xi,...,x„. Требуется определить, какая из схем в заданных условиях имеет большую вероятность правильной работы (отсутствия ошибки на выходе) и каково отношение вероятностей возникновения случайных ошибок на выходах этих схем.

В этом случае, с учетом (8.5), в работах [1, 2, 17] для искомой величины Л'ср при 5 —* 0 получено выражение

СР ESVÄ'UI -в>яу

где г = r(S,l,2k - 1) = r(S,0, г' = r'(S,i,2fc - 1) = r'(5,Z), а = BSj при J = 2к - 1 - 2'"1, В5-, = B'SJ при J = 2*' - 1 - 2'-'.

Величина Д'ср позволяет определить, во сколько раз чаще в заданных условиях будет ошибаться схема F по сравнению со схемой F'. Для практического вычисления Л"ср без проведения полного логико-вероятностного анализа в работах [2, 17] предложен специальный табличный метод.

Приведенные в работах автора примеры практического решения рассмотренных в данной главе задач (например, см. [1, 2]) показывают, что применение предложенных методов помехоустойчивого доопределения и сравнительного анализа позволяет (без привлечения специальных способов повышения надежности) снижать вероятность ошибки (сбоя) автомата (схемы) на 25% — 40%.

По теме диссертации опубликованы следующие работы :

Монографии

1. Чирков М.К. Основы общей теории конечных автомат з. Л., 1975. 280с.

2. Чирков М.К. Частичные автоматы. Л., 1983. 2С0с.

3. Шестаков A.A., Чирков М.К. Обобщенные конечные автоматы: поведенческая эквивалентность и проблемы оптимизации. Апатиты. Изд. КНП РАН, 1992. 160с.

4. Чирков М.К,, Шауман А.М. Основы функциональной структуры вычислительных машин. Л., 1974. 268с.

Статьи и тезисы докладов

5. Чирков М.К. Эквивалентность вероятностных конечных автоматов // Вычислительная техника и вопросы кибернетики, Л., 1968, вып. 5, с. 3-30.

6. Чирков М.К. Композиции вероятностных автоматов // Вычислительная техника и вопросы кибернетики, Л., 1968, вып. 5, с.31-59.

7. Чирков М.К. Вычисление вероятностных характеристик комбинационных схем // Методы вычислений, Л., 1968, вып. 5, с.85-102.

8. Чирков М.К. К анализу устойчивости функций алгебры логики при искажении аргументов // Методы вычислений, Л., 1968, вып. 5, с.102-120.

9. Чирков М.К., Шилкевич Т.П. О реализуемости вероятностных автоматов автоматами со случайными входами // Методы вычислений, Л., 1970, вып. 6, с.127-136.

10. Чирков М.К. Некоторые задачи анализа устойчивости схем при случайных сбоях // Вычислительная техника и вопросы кибернетики, Л., 1971, вып. 6, с. 44-55.

11. Чирков М.К. К задаче об оптимальном восстанавливающем элементе // Вычислительная техника и вопросы кибернетики, Л.,

1971, вып. 6, с. 56-67.

12. Чирков М.К. К анализу композиций ненадежных автоматов // Вычислительная техника и вопросы кибернетики, М., 1970, вып. 7, с. 87-102.

13. Чирков М.К. К анализу помехоустойчивости функций алгебры логики // Вычислительная техника и вопросы кибернетики, М., 1970, вып. 7, с. 103-118.

14. Чирков М.К. О методе вероятностной логики // Вычислительная техника и вопросы кибернетики, Л., 1971, вып. 8, с. 52-66.

15. Чирков М.К. Вероятностные задачи доопределения частичных автоматов без памяти // Вычислительная техника и вопросы кибернетики, Л., 1971, вып. 8, с. 66-81.

16. Чирков М.К. О помехоустойчивом доопределении переключательных функций // Теория и применение математических машин, Минск, 1972, с. 3-7.

17. Чирков М.К. Сравнительный вероятностный анализ логических схем // Теория и применение математических машин, Минск,

1972, с. 94-100.

18. Чирков М.К. О минимизации вероятностных автоматов // Вычислительная техника и вопросы кибернетики, М., 1972, вып. 9, с. 89-99.

19. Чирков М.К., Буй Мин Чи. К задаче о помехоустойчивом доопределении частичных автоматов // Вычислительная техника и вопросы кибернетики, М., 1972, вып. 9, с. 100-114.

20. Буй Мкн Чи, Чирков М.К. Об оптимальном по помехоустойчивости доопределении абстрактных автоматов // Методы вычислений, Л., 1973, вып. 8, с. 130-143.

21. Мороз Д.З., Чирков М.К. О вычислении вероятностных ха-

рактеристик схем с помощью ЭЦВМ // Методы вычислений, Л.,

1973, вып. 8, с. 144-153.

22. Буй Мин Чи, Чирков М.К. Алгоритм помехоустойчивого доопределения функций алгебры логики // Вычислительная техника и вопросы кибернетики, JI., 1974, вып. 10, с. G6-7S.

23. Чирков М.К. Надежностный анализ комбинационных схем, построенных из элементов типа " ИЛИ-НЕ" // Вычислительная техника и вопросы кибернетики, Л., 1974, вып. 10, с. 61-GG.

24. Чирков М.К.,Буй Мин Чи. О помехоустойчивом доопределении частичных автоматов с почти надежными входными каналами // Вычислительная техника и вопросы кибернетики, М.,

1974, вып. 11, с. 94-108.

25. Чирков М.К., Буй Мин Чи. Приведенные формы частичных вероятностных автоматов // Вычислительная техника и вопросы кибернетики, М., 1974, вып. 11, с. 80-93.

26. Чирков М.К., Эглитис Л.В. Обобщенные частичные функции алгебры логики и их минимизация // Вычислительная техника и вопросы кибернетики, Л., 1975, вып. 12, с. 114-124.

27. Чирков М. К.,Эглитис Л.В. Минимизация систем обобщенных частичных функций алгебры логики // Вычислительная техника и вопросы кибернетики, М., 1976, вып. 13, с. 113-124.

28. Чирков М.К. Обобщенные частичные векторы, матрицы, автоматы // Вычислительная техника и вопросы кибернетики, Л., 1977, вып. 14, сг 86-111.

29. Чирков М.К. Об одном методе минимизации обобщенных частичных вероятностных автоматов // Вычислительная техника и вопросы кибернетики, Л., 1977, вып. 14, с. 129-153.

30. Эглитис Л.В., Чирков М.К. Синтез частичных автоматов по частичным регулярным событиям // Вычислительная техника и вопросы кибернетики, Л., 1977, вып. 14, с. 175-1S3.

31. Чирков М.К., Эглитис Л.В. Помехоустойчивость обобщенных частичных функций алгебры логики // Вычислительная техника и вопросы кибернетики, М., 1978, вып. 15, с. 85-95.

32. Чирков М.К. О простых импликантах системы обобщенных частичных функций // Вычислительная техника и вопросы кибернетики, М., 1978, вып. 15, с.96-103.

33. Мачак К., Чирков М.К. О соотношении между дискретными каналами связи с конечной памятью и вероятностными автоматами // Вычислительная техника и вопросы кибернетики, М., 1978, вып. 15, с. 112-118.

34. Чирков М-К. О числе событий, представимых с интервалом сечения // Методы вычислений, Л., 1978, вып. 11, с. 174-178.

35. Чирков М.К. К абстрактному анализу частичных автоматов // Методы вычислений, Л., 1978, вып. 11, с. 178-184.

36. Chiricov М.К. On some types of incompletely specified automata //

Acta Cybcruetica, Szeged, 1978, Tom 4, Fasc. 2, p. 151-165.

37. . Чирков M.K. О минимизации частичных pi-автоматов // Вычислительная техника и вопросы кибернетики, Л., 1979. вып. IG. с. 109-137.

38. Сысоева Н.Б., Чирков М.К. К анализу энергоемкости переключательных схем из элементов ИЛИ-НЕ // Вычислительная техника и вопросы кибернетики, Л., 1979, вып. 16, с. 190-196.

39. Мирошниченко И.Д., Чирков М.К. О численном моделировании автоматов с переменной структурой // Методы вычислений, Л., 19S0, вып. 12, с. 201-213.

40. Генин М.А.. Егорова A.M., Чирков М.К. К расчету надежности комбинационных схем // Методы вычислений, Л.. 1980, вып. 12, с. 213-221.

41. Мачак К., Чирков М.К. О представимости регулярных языков вероятностными автоматами // Вычислительная техника и вопросы кибернетики, М.. 1980, вып. 17, с. 87-92.

42. Чирков М.К. К минимизации обобщенных частичных ¿-автоматов // Дискретные устройства, теория и приложения, Л., 1982, с. 172-179.

43. Чирков М.К. К синтезу частичных автоматов // Вычислительная техника и вопросы кибернетики, М., 1982, вып. 19, с. 17-25.

44. Chirkov М.К. On the embedding of a pi-automaton into an i-automaton // Anuales Universitatis Scientiarum Budapestinensis de Rolando Eotvos nominatae. Sectio Computatorica, Budapest, 1982, tomus 3, p. 53-62.

45. Чирков M.K., Шестаков A.A. Подобие частичных обобщенных автоматов // Роботы и робототехнические системы, Иркутск, 1985, с. 95-101.

46. Чирков М.К., Мирошниченко И.Д. О некоторых свойствах i-автоматов // Проблемы обработки информации, Л., 1Q85, с. 108116.

47. Чирков М.К., Шестаков A.A. О минимизации обобщенных автоматов // VII Всесоюзная конференция " Проблемы теоретической кибернетики"'. Тезисы докладов. Иркутск, 1985, часть 1, с. 201-202.

48. Мирошниченко И.Д., Чирков М.К. Алгоритмы оптимизации конечно-автоматных моделей с периодически меняющейся структурой // VIII Всесоюзная конференция " Планирование и автоматизация эксперимента в научных исследованиях." Тезисы докладов, секция 1. Ленинград, 1986, с. 22.

49. Мирошниченко И.Д., Чирков М.К. Обобщенные конечно-автоматные модели с периодически меняющейся структурой и их оптимизация // Всесоюзная научно-техническая конференция " Применение вычислительной техники и математических методов в научных исследованиях." Тезисы докладов. Киев, 1986,с. 22-23.

50. Шестаков А.А., Чирков М.К. Оптимизация внутренней структуры обобщенных автоматов // Роботы и робототсхнические системы. Иркутск, 198G, с. 128-135.

51. Чирков М.К.. Шестаков А.А. Подобие и минимизация обобщенных конечных автоматов // Математические проблемы информатики, Л., изд. ЛГУ, 1987, с. 158-173.

52. Мирошниченко И.Д., Чирков М.К. Минимизация обобщенных конечных автоматов с периодически меняющейся структурой // Проблемы оптимизации дискретных систем. Л., 1990, с. 7-21.

53. Чирков М.К., Шестаков А.А. Проблема редукции входного алфавита автоматов // Проблемы оптимизации дискретных систем, Л.. 1990. с. 33-12.

54. Чирков М.К. О матричных методах оптимизации обобщенных автоматов // Дискретные системы и их программное обеспечение. Л.. 1990, с. 3-1S.

35. Tchirkov М.К. On matrix methods for optimization of generalized automata. Aunales Uuivcrsitatis Scientiarum Budapestiuensis de Rolando Eotvos noininata.s. Sectio Computatorica, Budapest, 1991, Toiims 11, p. 175-191.

5G. Hacp Я., Чирков М.К. Об относительной сложности приведенных форм стохастических автоматов // Вестник Ленинградского ун-та. Серия 1. 1991, вып.4(Х 22), с. 73-75.

57. Nasr Y.,Tchirkov М.К. On optimization of stochastie finite automata // Third International Workshop on Model Oriented Data Analysis (MODA-3). St.Petersburg, 25-30 May, 1992, p. 24.

58. Ka'bawe M., Tcliirkov M.K. On automata methods for transformation of generalized language expressions // Third International Workliop on Model Oriented Data Analysis (MODA-3). St.Pet.ersburg. 25-30 May, 1992, p 14.

59. Hacp Я., Чирков М.К. О матричном методе оптимизации стохастических автоматов // Вестник С.-Петербургского ун га. Серия 1. 1992, вып. 3(N 15), с. 44-49.

60. Кабаве М., Чирков М.К. Об одном методе анализа обобщенных автоматов // Вестник С.-Петербургского ун-та. Серия 1. 1992, вып. 3(N 15), с. 95-97.

61. Кабаве М., Чирков М.К. О новом методе синтеза обобщенных абстрактных автоматов // Вестник С.-Петербургского ун-та. Серия 1. 1992, вып. 4(N 22), с. 106-108.

62. Tchirkov М.К. Modelling and optimization of finite state systems // International Workhop on Mathematicul Methods and Tools in Computer Simulation. May 24-28, 1994, St.Petersburg. Preprint MM-94-01, p. 95-97.

63. Miroshnichenko I.D., Tchirkov M.K. On reduced forms of generalized automata with a periodically variable structure /f International Workhop on Mathematicul Methods and Tools in Computer Simulation. May 24-28, 1994, St.Petersburg. Preprint MM-94-01, p. 99-101.