автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Сеть автоматов для моделирования асинхронного взаимодействия процессов

I

I

1 11а правах рукописи

I

НОВИК КОНСТАНТИН ВАЛЕРЬЕВИЧ

АСИНХРОННОГО ВЗАИМОДЕЙСТВИЯ ПРОЦЕССОВ

Специальность -05.13.18 Математическое моделирование, численные методы и комплексы программ

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

1

Москва - 2006

Работа выполнена на кафедре информатики Московского физико-технического института (государственного упиверси га а).

Научный руководитель:

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

Ведущая организация:

доктор физико-математических наук, профессор Столяров Лев Николаевич

доктор технических наук, профессор, Массель Людмила Васильевна кандидат физико-математических наук Амосов Григорий Геннадьевич

Вычислительный центр имени А.А. Дородницына Российской Академии Наук

Защита состоится £<уг£€се.С_2006 г. в

часов на заседании диссертационного совета К212.156.02 при Московском физико-техническом институте (государственном университете) по адресу 141700, Московская обл., г. Долгопрудный, Институтский пер. 9, МФТИ, КПМ 903.

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

Автореферат разослан «¿^Г» ¿¿cybsrta^ 2006 г.

Ученый секретарь диссертационного совета К212.156.02 (J

к.ф.-м.н. (^^f-L^-^—y ФедькоО.С.

¿ее 6 А

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

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

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

Чем объяснить такой интерес математиков и практиков программирования к сетевой парадигме? Все исследователи, работающие по данной тематике, отмечают, что сети являются одним из самых мощных математических инструментов моделирования систем с ярко выраженными распределенными процессами, которые взаимодействуют между собой. В таких системах можно выделить специальные механизмы (асинхронное управление), позволяющие строить сценарии поведения систем во времени.

Цель работы - разработка новых математических методов моделирования асинхронных систем (в виде 1отег-сетей), построение соответствующих математических моделей конкретных систем и разработка комплексов программ для их исследования.

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

элементарных автоматов для моделирования асинхронных систем, которые названы Мпег-сетями.

Построена оригинальная теория .Готег-сетей, состоящая из следующих разделов:

1. Формальная система, порождающая правильно построенные формулы 1отег-сети.

2. .Готег-алгебра, которая используется для эквивалентных преобразований формул.

3. Стандартное представление формул (разложение), которое удобно для решения задач анализа и программирования.

4. Сети автоматов в виде систем логических уравнений.

5. Доказаны теорема о декомпозиции сети на множество процессоров и теорема о логической неразрывности цепочек событий для анализа семантической корректности.

Представление .1отег-сети в виде системы логических уравнений распространено на сети Петри и другие сетевые модели асинхронных систем.

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

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

Апробация работы. Результаты диссертации докладывались на следующих конференциях и семинарах: XLII и XLVII научных конференциях МФТИ (1999,2004 гг.); Байкальских всероссийских конференциях с международным участием «Информационные и телекоммуникационные технологии в науке и образовании Восточной Сибири», «Информационные технологии в энергетике, экономике, экологии», «Математические и информационные технологии в энергетике, экономике, экологии», «Информационные и математические технологии», «Информационные и математические технологии в науке, технике и образовании», (2001 - 2005 гг.); научных семинарах кафедры информатики МФТИ (2003-2005 гг.).

Результаты работы были использованы в следующих проектах РФФИ: № 01-07-90277, «Разработка систем распределенного мозгового штурма через Internet для сложных научных проектов РАН», 2001-2002 гг.; № 02-07-06064 и № 0307-06149, «Программа поддержки молодых ученых», 2002 и 2003 гг.; № 03-07-90356, «Исследование моделей ситуационной комнаты, управляемой событиями, которые передаются через Internet», 2003-2005 гг.; №04-07-90070, «Информационная система для искусствометрики памятников древнерусского искусства», 2004-2006 гг.

Публикации. По теме диссертации опубликовано 11 работ.

Структура диссертации.

Диссертация состоит из введения, четырех глав и библиографии. Объем диссертации - 120 страниц. Список использованных источников содержит 38 наименований. В работу включены 125 рисунков и таблиц.

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

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

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

В первой главе вводится понятие основного объекта исследования - Мпег-сети (Ж). Ж - множество взаимодействующих процессов, где события взаимодействия управляются автоматами и связываются в систему логических уравнений. Точное определение 1отег-сети будет дано во второй главе. Приведены и проиллюстрированы на содержательных примерах базовые понятия и свойства Ж.

Для иллюстрации системы управления, построенной на асинхронном взаимодействии процессов, выбраны следующие задачи:

1) Задача совместного вычисления двух функций, связанных между собой следующим образом:

= Л СА (^1»X Л (^2 . )) (1)

У2 =/з(/2(*2>*з)>*з) где х\, Х2, *з - входные переменные (не обязательно числовые), /ь /г, Л ~ функции, реализуемые некоторыми подпроцессами. Каждый подпроцесс вычисляет промежуточные переменные:

=/\(х\>хг)>г2 = Ь(хг>хъ)>У\ =/2(^1^2)^2 =/з(*2>*з) (2)

На рисунке 1 приведена информационная структура алгоритма вычисления:

п к

*2 ___ А ^^ г, (г ^

X} / — у г

Рис. 1. Информационная структура вычисления функций у\ и у г.

На рисунке 2 в нотации сетей Петри показана .Готег-сеть, управляющая процессом вычислений («|» обозначают вершины, называемые переходами, с которыми связаны процессы

вычисления промежуточных переменных, «о» - вершины, называемые позициями, в которых запоминаются события, происходящие в сети), а в таблице 1 приведены описания соответствующих процессов и событий данной сети.

у >•

ЗПз

Рис. 2.1отег-сеть управления процессом вычислений.

Таблица 1. События и процессы сети управления вычислениями.

Процессы Описание События Описание

ЗП, запись х\ а(х:) значение х1 для вычисления // подготовлено

ЗП2 запись х2 а\{х2) значение х2 для вычисления f¡ подготовлено

ЗП3 запись *з аг(хг) значение х3 для вычисления подготовлено

/. вычисление /, аКхз) значение х} для вычисления подготовлено

Л вычисление /2 Я2О1) значение х3 для вычисления /} подготовлено

/з вычисление /3 значение г/ вычислено и подготовлено для

ьы значение г3 вычислено и подготовлено для/;

Ш) значение г} вычислено и подготовлено для

Фд значение у/ вычислено

с(у2) значение уз вычислено

Следует заметить, что а\(хг) и 02(^2) версии одного и того же „ события «запись сделана».

Запуск перехода (процесса) происходит тогда и только тогда, когда возникает некоторая совокупность событий,

называемая условием запуска. Например, процесс /\ будет запущен, если произойдут события «значение для вычисления /1 подготовлено» и «значение хг для вычисления подготовлено».

2) Обработка деталей на конвейере. Каждый станок является специальным процессором, на вход которого подаются объекты одного типа, а на выходе в результате обработки получаются объекты другого типа (рисунок 3).

Ло

о-

<1,

¿2

-х>

а-

-X)

5[, - станки, <Л0, с13 - детали. Рис. 3. Физическая схема конвейера. Для управления конвейером строится .Тотег-сеть, каждый из переходов которой связан с процессом обработки деталей одним из станков (рисунок 4).

1 .2 .3

Рис. 4. Сеть управления конвейером.

События 1, 2 и 3 сигнализируют о готовности соответствующей детали, а события 4 и 5 - о готовности соответствующего станка к обработке новой детали.

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

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

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

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

1. Формальная модель для порождения формул JN. Формулой JN называется направленный граф, который состоит из двух видов вершин («|» - переходы, «о» - позиции) и однократных дуг. Формальная система, порождающая все правильно построенные формулы JN:

FJN = (A,N,R), (3)

где А (аксиомы) - конечный набор формул вида:

Рта и Р«1ч

5, &

{5], ..., 5,, ..., - множество переходов (процессов), {Рх0М} - множество входных позиций,

{РУ(,)} -множество выходных позиций; N={«1,..., пг, ..., «/} -конечное множество имен событий; Я={РУ(])=РХ(,^) := пг) -конечное число правил отождествления и именования, «=» -операция отождествления, «:=» - операция именования. Я -правила склеивания.

Типы правил склеивания РЖ иллюстрируются следующими картинками: I. Правило В (вых./вх.)

[{РуХ=Рх2у-п}

ГЩ ЕМ2 РЖ

Р,\ Рух Рл . Р* Рл . п Руг

• >| >• » >| >• • >| >• >| >•

II. Правило/4i (антонимум) (вых./(вх.1, вх.2)) RAl(FJNlt FJN2, FJN^FJN- [{Ру1=Рг2):=и), ((/>,,^3):=")]

FJNi FJN2 FJNi FJN

P„ Pи Рл Руг Р,ъ Рл

• >1 >• • >| >• • >| >• />„

S, Sj s, • >| >»

s,

III. Правило Сi (синонимум) (вых./(вх.1, вх.2)) Ra(FJNu FJN2, FJN3)=FJN-, №y^Pi2):=nx\ ((Pyt=Px3):=n2)]

FJN^ FJN2 FJNi FJN

Р, 1 , гУ1 г* г,г "1

•Ч** ^ь^Г

5, 5з I Р>а

5, >|>•

&

IV. Правило А2 (антонимум) ((вых.1, вых.2)/вх.) Ял^Ии FJN2, FJN})=FJN^, [((^,=Лз):=«|), ((Л*г^з):="2)]

ЛЛУ, FJN2 FJN) FJN

Р* Ра РЛ . Р* Р,\ . "1

• >| >• • >| >• • >| >• • >| р*

5. Л 5, Рл ^ пг ^ГГ*"*

й

V. Правило С2 (синонимум) ((вых.1, вых.2)/вх) Яп^и FJN2, FJNy)=FJN\ [((Ру^Рх2У=п), ((Ру1=РхЪ):=п)]

FJN\ FJN2 РМ, FJN

Р„ Ри Рл . Руг Р* Ру> Рл

• >| >• • >| >• • >| >•

51 5з Р,1

Правило В. выходной сигнал о событии окончания используется как входное событие. Вообще говоря, это одно и то же событие, поэтому оно получает уникальное имя. Правило Л]: сигнал об окончании процесса 51 используется как событие для запуска & либо 5з, но не обеих сразу. Правило С1: сигнал об окончании процесса 51 используется процессами 5г и 5з для запуска, одно и то же событие, но с разными именами дает возможность одновременного запуска как 52 так и 5з. Правило

Аг. два разных сигнала об окончании процессов 51 и & являются причинами запуска одного и того же процесса £3. Правило Сг'. каждый из двух сигналов окончания процессов и может быть событием для запуска процесса 5з, но не оба вместе.

2. .1отег~алгебра. Алгебра необходима для построения и эквивалентных преобразований строчных формул, которые задают Ж. Преобразования нужны для решения разнообразных задач анализа, использующих известные эффективные алгоритмы работы со скобочными формулами. Ж-алгебра представляет собой набор эквивалентных преобразований формул из правильно построенных цепочек в двусортном алфавите (цепочки обозначаются х, у, г и т.д.) и бинарных операций {*;У}.

Свойства Лотег-алгебры:

(х • у)*г = х»(уг)

1. Ассоциативность. ) / , ч .

(хУу)Уг = хЧ{у7г)

~ {х*у)*{ух)

2. Коммутативность: , ' . . .

(хУу) = (уУх)

(х • X ) Ф X

3. Идемпотентность: , /

(хУх)=х

^ „ „ х • (уУг) = (х • ;у)У(х • г)

4. Дистрибутивность: , ч . ' . '

\уЧг) •х = \у х У7(г • х)

хУ(у • г), «V» - не обладает свойством дистрибутивности.

5. Декомпозиция: (х • у • г) = (х • у)У{у • г) (обратное не верно).

х*0 = х

6. Свойства пустой цепочки «0»: 0 • х = х.

хУ0 = х

Производные свойства:

„ (х • уУу) = х • V

7. Поглощение: , '

(х • >"Ух) = х • у

t

8. Операция итерации («*» - звезда Клини): (х)' = 0УхУх • хУх • х • XV...Ух •... • хУ...

(хУу)* = 0У(хУу)У(хУу) • (хУу)У... 3. Рекурсивные формулы ЛЧ. Используя 1отег-алгебру, можно задавать сеть в виде рекурсивной формулы. Так, для сети управления конвейером (рисунок 4) построение рекурсивной формулы выглядит следующим образом:

1) Исходная формула есть композиция элементарных формул: К = ((4 • а • 2)У((2У5) • Ъ • (ЗУ4))У(3 • с • 5)).

2) Композиция рекурсивных цепочек (вместо символа «V» используется «[]»):

4»я*2

4*а*2 •£•',[ {

Ъ•

2 5

3*с*5

4 • д • 2~

?*с*5_

где |[ =

b»\ [ ]| - рекурсивная формула.

4 • а • 2 3 • с • 5 _

3) Корректирующая цепочка для внешнего события 1: (1*д*2)

4) Результирующая рекурсивная формула:

4] 1 1 *а*2 т I г "р

3 • с • 5

На рисунке 5 показана сеть в виде циклически повторяющегося фрагмента, которая соответствует приведенной рекурсивной формуле.

Рис. 5. Сеть конвейера с циклически повторяющимся

фрагментом.

4. Стандартные разложения ^тег-сетей, п-процессорное разложение, теорема о декомпозиции рассматриваются во второй главе. Так, разложение в ярусно-параллельную форму (ЯПФ) позволяет проводить детальный анализ сети на возможные сценарии развития событий. Кроме того, используя Мпег-алгебру можно представить сеть в виде, удобном для выполнения на нескольких процессорах (п-процессорное разложение), более того, можно добиться максимально возможного параллелизма. Теорема о декомпозиции доказывает, что произвольная Ж может быть разложена на сетевые фрагменты так, что каждый фрагмент выполняется только одним процессором и все фрагменты связываются внешними событиями. Доказательство теоремы конструктивно.

Для иллюстрации различных разложений сети используется пример отражения ракетной атаки (рисунок 6).

Рис. 6. Сеть управления отражением ракетной атаки. События: 1 - антиракетный маневр закончен, 2 - внешняя ситуация штатная, 3 - ракетная атака обнаружена, 4 - сигнал тревоги, 5 - антиракетный маневр закончен, 6 - внешняя ситуация контролируется приборами, 7 - действия по

отражению атаки закончены, 8 - сигнал тревоги, 9 - цель захвачена. Процессы: а - действия пилота при штатном полете, Ь - действия пилота при атаке, с - действия штурмана в штатном режиме, с1 - действия штурмана в режиме тревоги, е - действия штурмана при антиракетном маневре.

Пример разложения сети на два процессора (2-процессорное разложение) приведен на рисунке 7.

Рис. 7. Двухпроцессорное разложение сети отражения атаки.

5. Формальная интерпретация ЛЧ сетью автоматов, теорема о работающей цепочке. Каждому переходу 5 с

множеством входных и выходных позиций Р(р\..... р„)

сопоставляется автомат А(у/, <р, Р), где цКр\, рп) - пусковая функция, (р{р\, ..., р„) - флаговая функция. Пусковая функция у/ определяет условия запуска перехода и соответствующего ему подпроцесса. Условия запуска перехода суть наборы значений булевой функции у/(р\, ..., /?„)= 1, где значение позиции рг= 1 (истина), если соответствующее событие возникло, р,=0 (ложь), если событие не возникло либо было «стерто» из памяти позиции. Флаговая функция присваивает новые значения всем позициям (входным и выходным) после окончания процесса. Д(рь ..., р„) - память элементарного автомата (регистр памяти позиций), где запоминаются значения («О» или «1»), сигнализирующие о возникновении (невозникновении) соответствующих событий.

Работа элементарного автомата задается булевскими уравнениями для каждого перехода:

5 (<), • ■ •, Рп (0) -> <Р{Р\ (< + 0 М, • • •, РЯ (' + 0 •= {ОД})

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

«

О)

Содержательная интерпретация правил работы элементарного автомата: если вектор позиций Р(0 соответствует у/=\, то автомат запускает подпроцесс, по окончании его работы происходит изменение вектора Р((+1) в соответствии с флаговой к, функцией.

Теорема о «работающей» цепочке позволяет проводить алгоритмическую проверку существования цепочки событий между двумя переходами (проверка на достижимость): для произвольной Дотег-сети существует алгоритм проверки выводимости (построения цепочки) между заданной парой переходов (50,где 5о является началом цепочки, а - ее

концом. В теореме идет речь о построении и проверке работающей цепочки, т.е. такой цепочки, которая обладает следующими свойствами:

1) Цепочка имеет неразрывную последовательность связывающих дуг, выраженную формулой: 50 • 2•...•(/-1)*• ¡•...•(к-1)*^, т.е. переход достижим из 5о.

2) Каждая пара соседних переходов в цепочке (х,у) имеет <рх и

#

у/у такие, что <рх & * 0.

3) Для каждого перехода х не выполняется условие самозапуска <рх&у/х = 0.

Теорема доказывается конструктивно. Назначение теоремы - проверка логической корректности сети и ее соответствие содержательной задаче.

В третьей главе рассматриваются известные модели асинхронных систем и их представление в виде 1отег-сети. Оказывается, что эти модели имеют ограничения на вид

пусковых и флаговых функций, в отличие от Ж, которые таких ограничений не имеют.

1. Простые сети Петри (Р1Ч). Такие сети не допускают кратные дуги и наличие более одной фишки в позиции. Элементарный автомат для перехода 5 может иметь пусковые и флаговые функции только такого вида:

Пусковые функции Флаговые функции

где XI, ...,х„- входные позиции, ...,ут- выходные позиции. <ps :xhtt :=(),...,х„ж(/ + 1):=0, :=1>->>ч„:=l

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

2. Дискретные нейронные сети Мак Каллока-Питтса (УТЧ). Каждый нейрон в такой сети может быть описан автоматом со следующими пусковыми и флаговыми функциями:

Пусковые функции Флаговые функции

ДНФ - произвольная дизъюнктивная нормальная форма булевой функции от входных переменных. <PS :=0,...,x„+i(i + l):=0, У1н1 :=1>...,JV, :=1

Входы, имеющие отрицание, называются тормозящими.

3. Асинхронные цифровые схемы Маллера. В этой модели рассматривается сеть, построенная для двух объектов -поля операционных элементов и поля регистровой памяти. Фактически, операционные элементы являются устройствами для реализации пусковых и флаговых функций, а регистровая память используется для запоминания событий. Тип пусковых и флаговых функций соответствует РМ События поступают от

аппаратных блоков, преобразуются в асинхронной схеме Малера и возвращаются в виде управляющих событий обратно в аппаратные блоки. Фактически, асинхронное управление представляет сети Петри. Кроме этого, рассматриваются семантические сети Ван-Хао и алгебраические сети.

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

Модель физико-химических процессов разрушения фресок была сделана для музея фресок Дионисия Ферапонтова монастыря, который входит в список объектов ЮНЕСКО.

Значительное влияние на состояние фресок оказывает температурно-влажностный режим, поэтому в качестве «внешних» были выбраны события, связанные с колебаниями температуры и влажности.

Полотно фрески разбивается на отдельные участки, поведение каждого из них задается своей сетью. Сеть, описывающая поведение двух соседних участков фрески показана на рисунке 8.

Яз1 Рп

Рис. 8. Ж состояния двух соседних участков фрески в развернутом виде. 17

В таблице 4 описаны события для представленной на рисунке 8 сети. Пусковые и флаговые функции приведены в таблице 5.

Имя | Описание

Первый участок

Ри Наблюдается повышенная температура (больше Ттах).

Ргх Наблюдается пониженная температура (меньше Тт,„).

Л. Температура резко понизилась (с Т\ до Г2 за время менее Л1\).

Л» Температура медленно понизилась (с Т\ до Тг за время менее

Р» Наблюдается повышенная влажность (больше ата1).

Ап Наблюдаются трещины левкаса.

Л.„ Наблюдается отслаивание левкаса.

Л» Наблюдается разрушение левкаса.

Л41 Наблюдается шелушение красочного слоя.

/<51 Наблюдается разрушение красочного слоя.

Наблюдаются высолы на красочном слое.

А7, Наблюдается загрязнение красочного слоя грибами и плесенью.

Второй участок

Рп Наблюдается повышенная температура (больше Ттах).

Р» Наблюдается пониженная температура (меньше Т„1п).

Ръг Температура резко понизилась (с 7*| до Т2 за время менее Л1\).

РА2 Температура медленно понизилась (с Т\ до Т2 за время менее

Ры Наблюдается повышенная влажность (больше атах).

Ап Наблюдаются трещины левкаса.

Аг2 Наблюдается отслаивание левкаса.

Ап Наблюдается разрушение левкаса.

А 42 Наблюдается шелушение красочного слоя.

А 52 Наблюдается разрушение красочного слоя.

А 62 Наблюдаются высолы на красочном слое.

Ап Наблюдается загрязнение красочного слоя грибами и плесенью.

Таблица 5. Пусковые и флаговые функции для Ж двух соседних участков фрески._ ._

Пусковые функции Флаговые функции

Первый участок

<Ул„ V/»,,) 9 л» :Лц(' + 1):=1

9л,, :>11|(г + 1):=0М21(г + 1):=1

9Л), :Л21(/ + 1):=<М31(/ + 1):=1

9 л» М41(/ + 1):=1

V«, -Л41&Р„&Р„ 9л,, • А*\ (' + 0:= 0,^51 +

9-Аь\ (< + 1):=1

9а,, +

Второй участок

9АЬ :Л12(/ + 1):=1

9ли ■ Ап (' + !):= ОМ22 (/ + 0-1

¥Лп=Л1г&.Ап&,Рп&.Ра 9лп ^22 (' + !):= 0, + 1):= 1

9Ап ^42 (' + 0-1

9 А» :/Г«^ + 1):=0,^52(/ + 1):=1

9л* :Л2(' + 0:= 1

¥Лп ={А„чР1гчРа)&Р„ 9лп ■ Ап (' + !):=!

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

Рис. 9. Результаты моделирования состояния фрески Дионисия.

Кроме описанной модели в диссертации рассматриваются в виде Ж-сетей: модель удаленной Мегпе^атаки, модель информационной системы боевого подразделения, модель поведения стаи рыб, модель поведения биржи, модель системы связи канального процессора с двумя абонентами (фактически, модель сетевого коммутатора).

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

В диссертационной работе получены следующие основные выводы и результаты:

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

Разработана формальная модель асинхронной системы в виде сети (графа) с двумя типами вершин (позиции и переходы). Сеть строится из базовых элементов, соответствующих каждому процессу. Построены формальные правила порождения сети из базовых элементов, основанные на отождествлении вершин-позиций этих элементов. Для удобства моделирования сети сопоставляется система логических уравнений из пусковых и флаговых функций. Определена интерпретация базовых элементов сети. Позиции представляют собой распределенную память о событиях сети, а переходы интерпретируются элементарными автоматами, которые запускаются входными событиями (пусковыми функциями) и генерируют выходные события (флаговые функции). Каждый переход представляет собой отдельный процесс или его состояние (подпроцесс). Такие сети названы Мпег-сетями. Показано, что Мпег-сеть является обобщением известных моделей асинхронных систем. Построены 1огпег-сети для сетей Петри, семантических сетей Ван-Хао, диаграмм Маллера, дискретной нейронной сети Мак Каллока-Питтса. Построена теория 1отег-сетей, базирующаяся на специально разработанной Мпег-алгебре. Алгебра позволяет строить стандартные формы представления (разложения) сетей, удобные для анализа и программирования. Доказаны теорема о декомпозиции сетей на множество процессоров и теорема о «работающей цепочке», позволяющая порождать множество сценариев развития событий в сети.

Приведены примеры задач, для решения которых используются математические модели в виде Мпег-сетей и соответствующие комплексы программ. В частности, Ж-модель поведения стаи рыб, Ж-модель поведения биржевых игроков, Ж-модель «жизни» настенных росписей (выполнялась для Ферапонтова монастыря, который входит в список объектов ЮНЕСКО), Ж-модель Интернет-атаки и т.д.

Основное содержание диссертации опубликовано в работах:

1. Новик КВ. Струйный анализ временных рядов // Моделирование процессов управления и обработки информации: Сб. научных трудов/Моск. физ.-тех. ин-т. - М., 1999.-С. 198-212.

2. Новик КВ. Приложения струйной томографии. Анализ клиентской базы // Управление и обработка информации: модели процессов: Сб. научных трудов/Моск. физ.-тех. ин-т. -М., 2001. — С. 178-182.

3. Столяров Л.Н., Новик КВ., Бершадский А.В., Комаревцев А. Сценарное программирование риска: механизм коллективного принятия решений и его применение к оценке уровня энергетической безопасности региона // Информационные технологии в науке и образовании: Сб. научных трудов/СЭИ - Иркутск, 2002. - С. 14-35.

4. Новик КВ., Ситуационная комната для анализа и парирования Интернет-атак // Математические и информационные технологии в энергетике, экономике, экологии: Сб. научных трудов/ИСЭМ СО РАН - Иркутск,

2003. - Часть 2 - С. 267-277.

5. Столяров JJ.H., Новик К. В. Joiner-сеть для моделирования взаимодействующих параллельных процессов // Моделирование процессов управления: Сб. научных трудов/Моск. физ.-тех.. ин-т. - М., 2004. - С. 81-97.

6. Коновалова Л.И., Новик КВ. Применение сетей Joiner-net для мониторинга состояния фресок Дионисия Ферапонтова монастыря // Моделирование процессов управления: Сб. научных трудов/Моск. физ.-тех. ин-т. -М., 2004. - С. 88-94.

7. Столяров Л.Н., Новик КВ. Реализация параллельных процессов с помощью сетей Joiner-net // Информационные и математические технологии: Сб. научных трудов/ИСЭМ СО РАН - Иркутск, 2004. - С. 11-14.

8. Коновалова Л.И., Новик КВ. Мониторинговые возможности сетей Joiner-net // Информационные и математические технологии: Сб. научных трудов/ИСЭМ СО РАН - Иркутск,

2004.-С. 14-17.

9. Новик КВ. Исследование Joiner-net для управления синхронизацией данных // Процессы и методы обработки информации: Сб. научных трудов/Моск. физ.-тех. ин-т. - М., 2005.-С. 31-39.

10 .Новик КВ. Joiner-cera для моделирования взаимодействующих процессов // Информационные и математические технологии в науке и образовании: Сб. научных трудов/ИСЭМ СО РАН - Иркутск, 2005. - Часть 1 -С. 243-249.

11. Новик КВ. Сеть автоматов для моделирования асинхронных процессов // Вестник ИрГТУ / ИрГТУ - Иркутск, 2005. - №4 -С. 51-56.

Новик Константин Валерьевич

СЕТЬ АВТОМАТОВ ДЛЯ МОДЕЛИРОВАНИЯ АСИНХРОННОГО ВЗАИМОДЕЙСТВИЯ ПРОЦЕССОВ

Подписано в печать 10.11.2005. Формат 60*84 1/16. Печать офсетная. Усл. печ. л. 1.0. Уч.-изд. л. 1.0. Тираж 70 экз. Заказ № ф-038

Государственное образовательное учреждение высшего профессионального образования

Московский физико-технический институт (государственный университет) Отдел автоматизированных издательских систем «ФИЗТЕХ-ПОЛИГРАФ» 141700, Московская обл., г. Долгопрудный, Институтский пер., 9

¿¿GQàdX ¿seo

iß - g

300

ВВЕДЕНИЕ.

ГЛАВА 1 ВВЕДЕНИЕ В СИСТЕМЫ ВЗАИМОДЕЙСТВУЮЩИХ ПРОЦЕССОВ.

1.1 Сеть Петри для моделирования асинхронного взаимодействия процессов при использовании общих ресурсов.

1.2 Сети с накоплениями событий.

1.3 Сети с распознающими предикатами.

1.4 Вычислительные сети (CN).

1.5 Самосинхроиизирующиеся сети (SN).

1.6 Асинхронные преобразующие сети.

1.7 Высказывательная (пропозиционная) сеть для экспертных систем.

1.8 Выводы по главе 1.

ГЛАВА 2 ТЕОРЕТИЧЕСКИЕ ОСНОВЫ ТЕОРИИ JOINER-СЕТЕЙ.

2.1 Концептуальная интерпретация Joiner-сетей и взаимосвязей их элементов.

2.2 Формальная система, порождающая правильно построенные формулы JN.

2.3 Матричная форма представления JN.

2.4 Проблемы анализа сетей и формы их представления, удобные для анализа.

2.5 Joiner-алгебра (склеивающая алгебра).Ъ

2.6 Техника работы с Joiner-алгеброй.

2.7 Теорема о ярусно-параллельной форме Joiner-сети.

2.8 Многопроцессорное разложение сетей. Теорема о процессорной декомпозиции. Теорема о композиции локальных сетей.

2.9 Формальная интерпретация JN сетью автоматов.

2.10 Внутренняя структура элементарного автомата и правила его работы в сети.

2.11 Теорема о «работающей» цепочке.

2.12 Выводы по главе 2.

ГЛАВА 3 ИЗВЕСТНЫЕ МОДЕЛИ АСИНХРОННЫХ СИСТЕМ УПРАВЛЕНИЯ ПРОЦЕССАМИ И ИХ ПРЕДСТАВЛЕНИЕ JOINER-СЕТЬЮ.

3.1 Сети Петри (PN).

3.2 Асинхронные цифровые схемы (сети) Маллера (MN).

3.3 Дискретные нейронные сети Мак Каллока-Питтса (VN).

3.4 Семантическая сеть Ван-Хао (WN).

3.5 Алгебраические сети (AN). Исчисление Эрбрана-Геделя. Вычислительные модели Э. Тыугу.

3.6 Ринговые и роторные сети (RN, RoN).

3.7 Выводы по главе 3.

ГЛАВА 4 МОДЕЛИ РЕАЛЬНЫХ АСИНХРОННЫХ СИСТЕМ, ИСПОЛЬЗУЮЩИХ JOINER-CETH.

4.1 Модель, описывающая процессы разрушения древнерусских фресок

4.1.1 Описание модели.

4.1.2 Элементы модели.

4.1.3 Сеть, описывающая состояние фрески.7)

4.1.4 Пример работы сети.

4.2 Модель удаленной Интернет-атаки.

4.2.1 Описание модели.

4.2.2 Элементы модели.

4.2.3 Сеть для моделирования атаки.

4.2.4 Пример работы сети.

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

4.3.1 Описание модели.

4.3.2 Сеть, моделирующая систему связи канального процессора с двумя абонентами через адаптер.

4.3.3 Пример работы сети.

4.4 Модель информационной системы поля боя.

4.4.1 Описание модели.

4.4.2 Элементы модели.

4.4.3 Сеть для четырех подразделений.

4.4.4 Пример работы сети.

4.5 Модель группового поведения стаи рыб.

4.5.1 Описание модели.

4.5.2 Элементы модели.

4.5.3 Сеть для стаи из пяти рыб.

4.5.4 Пример работы сети.

4.6 Модель биржевой игры.

4.6.1 Описание модели.

4.6.2 Элементы модели.

4.6.3 Сеть для двух игроков.

4.6.4 Пример работы сети.

Работа посвящена моделям поведения сложных систем, в которых выделены элементы и их взаимосвязи. Элементы называются процессами, а взаимосвязи определяются поставками и потреблением отдельными процессами информации, энергии, вещества. Каждый элемент системы (процесс) «живет» по собственным законам и требует для своей «жизни» определенные ресурсы, например, каналы для передачи информации, хранилища для вещества, процессоры для выполнения действий и т.д. Говорят, что поведение такой системы асинхронно, в связи с тем, что взаимодействия (поставки и потребление ресурсов) не зависят от физического времени, а определяются событиями, которые генерируются отдельными элементами системы. События фиксируют результаты изменений в состоянии элементарных процессов, передаются (собираются) другими процессами, управляя изменением их состояния. В этом плане события являются синхронизаторами, инициаторами изменения состояний процесса. Сетевые модели в настоящее время весьма распространены, начиная с 80-х годов XX века, и насчитывают около тысячи публикаций.

1. Объект исследования.

Объектом исследования являются асинхронные системы (АС), которые задаются сетью Net = (S,E,R,I), где S = {S{,.,Sn} - конечное множество процессов, Е = {ех,.,ет} - конечное множество событий, R - правила, которые приписывают каждому процессу S, подмножества так называемых входных Ex(Si) и выходных Ey(Si) событий, правила имеют вид: : Ех (Si )Еу,

I- интерпретация (операционная семантика), связанная с инициализацией процессов, изменением и запоминанием событий. Обычно сети задаются графом с вершинами двух видов -EnS, взаимосвязи между событиями и процессами показываются дугами. Сеть используется в виде математической модели асинхронной системы в известной цепочке перехода «от содержательной задачи к программе»:

Содержательная Математическая модель Программа задача асинхронной системы

2. Проблемы моделирования асинхронных систем с сетевыми моделями.

1) Первая проблема возникает при переходе от содержательной задачи к модели асинхронной системы. Она связана с формализацией описания взаимодействия, или, как говорил Ч. Хоар в своей книге «Взаимодействующие последовательные процессы» (1980), в составлении протокола взаимодействия между парой процессов. Даже в самых распространенных сетях Петри нет четко сформулированного протокола, удовлетворяющего всем формальным требованиям для построения его программной реализации.

2) Вторая проблема возникает при переходе от математической модели к программной реализации и связана с распознаванием корректности (адекватности) сетевой модели. Модель называется корректной, если ее поведение соответствует законам, сформулированным исследователем. Заметим, что эта проблема вызывает особые трудности и не решена до сих пор. На самом деле, поведение системы определяется последовательностями событий, некоторые из них связываются в цепочки (деревья) событий, а некоторые возникают параллельно (независимо). Тот же Ч. Хоар как пожелание высказывает предложение по построению таких графических моделей, которые бы показывали фронтальное разворачивание событий от начальных воздействий (событий) в виде бесконечно повторяющихся циклов. Понятно, что в таком случае можно было бы строить различные сценарии поведения систем и, кроме этого, создавать тесты, доказывающие корректность сетевых моделей.

3. Какие проблемы решены в диссертации.

Собственно, решению двух вышеперечисленных проблем и посвящена данная работа.

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

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

4. Научная новизна работы.

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

1) Вводится понятие «картиночных» формул и строится формальная система порождения всех правильно построенных формул.

2) Вводится специальная Joiner-алгебра с двумя операциями: «•» -склеивание и «V» - композиция. Joiner-алгебра позволяет проводить эквивалентные преобразования формул. В частности, с ее помощью строятся стандартные разложения сетей.

3) Для каждого процесса вводится управляющий элементарный автомат с двумя видами функций: у/-пусковой (для запуска процесса) и (р

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

Сети, построенные на этих трех принципах называются Joiner-сетями.

Эти три результата получены самостоятельно (являются оригинальными), представляют научную новизну работы и выносятся на защиту.

5. История исследований.

Исследования по сетевой тематике начались с 1999 года, были отражены в бакалаврской диссертации «Струйная томография, теория и практическое применение» (2001) и в магистерской диссертации «Ситуационная комната для анализа и парирования Internet-атак» (2003). В основном исследования проводились в рамках грантов РФФИ № 01-0790277, «Разработка систем распределенного мозгового штурма через Internet для сложных научных проектов РАН», 2001-2002 гг.; № 03-07-90356, «Исследование моделей ситуационной комнаты, управляемой событиями, которые передаются через Internet», 2003-2005 гг.; № 04-07-90070, «Информационная система для искусствометрики памятников древнерусского искусства», 2004-2006 гг.; а также личных грантов РФФИ № 02-07-06064 и № 03-07-06149, «Программа поддержки молодых ученых», 2002 и 2003 гг., выделенных на проведение перспективных фундаментальных исследований. Большая часть результатов исследований вошла в диссертационную работу.

6. Логика построения работы и ее краткое содержание.

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

2) Во второй главе вводится понятие Joiner-сетей и строится их теория, состоящая из следующих разделов:

1. Формальная система, порождающая правильно построенные формулы Joiner-сетей (JN).

2. Joiner-алгебра.

3. Стандартные разложения JN.

4. Анализ циклических ярусно-параллельных разложений.

5. Интерпретация формул сети автоматами, автоматными пусковыми и флаговыми функциями.

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

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

Доказывается теорема о «работающей» цепочке и показывается применение этой теоремы для анализа корректности (логической неразрывности) сети.

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

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

3.7 Выводы по главе 3

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

2. Существуют сети с операционной семантикой, отличной от сетей Петри.

3. В Joiner-сетях может быть задана любая операционная семантика в виде произвольных булевых выражений для пусковых и флаговых функций.

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

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

JN

Заключение

В диссертационной работе получены следующие основные выводы и результаты:

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

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

3. Определена интерпретация базовых элементов сети. Позиции представляют собой распределенную память о событиях сети, а переходы интерпретируются элементарными автоматами, которые запускаются входными событиями (пусковыми функциями) и генерируют выходные события (флаговые функции). Каждый переход представляет собой отдельный процесс или его состояние (подпроцесс). Такие сети названы Joiner-сетями. Показано, что Joiner-сеть является обобщением известных моделей асинхронных систем. Построены Joiner-сети для сетей Петри, семантических сетей Ван-Хао, диаграмм Маллера, дискретной нейронной сети Мак Каллока-Питтса.

4. Построена теория Joiner-сетей, базирующаяся на специально разработанной Joiner-алгебре. Алгебра позволяет строить стандартные формы представления (разложения) сетей, удобные для анализа и программирования. Доказаны теорема о декомпозиции сетей на множество процессоров и теорема о «работающей цепочке», позволяющая порождать множество сценариев развития событий в сети.

5. Приведены примеры задач, для решения которых используются математические модели в виде Joiner-сетей и соответствующие комплексы программ. В частности, JN-модель поведения стаи рыб, JN-модель поведения биржевых игроков, JN-модель «жизни» настенных росписей (выполнялась для Ферапонтова монастыря, который входит в список объектов ЮНЕСКО), JN-модель Интернет-атаки и т.д.

1. Автоматное управление асинхронными процессами в ЭВМ и дискретных системах / Под ред. Варшавского В.И. М.: Наука, 1986. - 308 с.

2. Ахо А.,Хопкрофт Дж., Ульман Дэ/с Построение и анализ вычислительных алгоритмов. М.: Мир, 1979. - 535 с.

3. Варшавский В. И., Поспелов ДА. Оркестр играет без дирижера. М.: Наука, 1984.-208 с.

4. Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. СПб.: БХВ-Петербург, 2002. - 608 с.

5. Зайцев Д.А. Инвариантность модели Петри протокола TCP // Научные труды Одесской национальной академии связи им. А.С. Попова. 2004. -№2.-С. 19-27.

6. Клини С.К. Введение в математику. М.: ИЛ, 1957. - 526 с.

7. Коновалова Л.И., Новик КВ. Мониторинговые возможности сетей Joiner-net // Информационные и математические технологии: Сб. научных трудов/ИСЭМ СО РАН Иркутск, 2004. - С. 14-17.

8. Коновалова Л.И., Новик КВ. Применение сетей Joiner-net для мониторинга состояния фресок Дионисия Ферапонтова монастыря // Моделирование процессов управления: Сб. научных трудов/Моск. физ.-тех. ин-т. М., 2004. - С. 88-94.

9. Котов В.Е. Алгебра регулярных сетей Петри // Кибернетика. 1980. - №5 -С. 10-18.

10. Котов В.Е. Сети Петри. М.: Наука, 1984. - 160 с.1 \.Котов В.Е., Наринъяни А.С. Асинхронные вычислительные процессы над памятью // Кибернетика: Сб. ст. / АН СССР. 1966. - №3 - С. 64-71.

11. Мак-Каллок У.С., Питтс У. Логическое исчисление идей, относящихся к нервной активности // Автоматы, под ред. Шеннона К.Э. и Маккарти Дж. -М.:ИЛ, 1956.-С. 362-384.

12. Мальцев А.И. Алгебраические системы. М.: Наука, 1970. - 392 с.

13. Мальцев А.И. Алгоритмы и рекурсивные функции. М.: Наука, 1986. -392 с.

14. Медведский ИД., Семьянов П.В., Леонов Д.Г. Атака на Internet. М.: ДМК, 1999.-336 с.

15. Мендельсон Э. Введение в математическую логику. -М.: Наука, 1971. -320 с.

16. Минский М. Структура для представления знания // Психология машинного зрения. М.: Мир, 1978. - С. 249-338.

17. Новик КВ. Joiner-cera для моделирования взаимодействующих процессов // Информационные и математические технологии в науке и образовании: Сб. научных трудов/ИСЭМ СО РАН Иркутск, 2005. - Часть 1 - С. 243249.

18. Новик КВ. Исследование Joiner-net для управления синхронизацией данных // Процессы и методы обработки информации: Сб. научных трудов/Моск. физ.-тех. ин-т. М., 2005. - С. 31-39.

19. Новик К.В., Ситуационная комната для анализа и парирования Интернет-атак // Математические и информационные технологии в энергетике, экономике, экологии: Сб. научных трудов/ИСЭМ СО РАН Иркутск,2003. Часть 2 - С. 267-277.

20. Новик К.В. Струйный анализ временных рядов // Моделирование процессов управления и обработки информации: Сб. научных трудов/Моск. физ.-тех. ин-т. -М., 1999. С. 198-212.

21. Питерсон Дж. Теория сетей Петри и моделирование систем. -М.: Мир, 1984.-264 с.

22. Столяров JI.H. Структурный анализ численных алгоритмов для параллельных и конвейерных вычислений: Дисс. докт. физ.-мат. наук. -М.: МФТИ, 1987.

23. Столяров Л.Н., Новик К.В. Joiner-сеть для моделирования взаимодействующих параллельных процессов // Моделирование процессов управления: Сб. научных трудов/Моск. физ.-тех. ин-т. -М.,2004.-С. 81-97.

24. Столяров Л.Н., Новик КВ. Реализация параллельных процессов с помощью сетей Joiner-net // Информационные и математические технологии: Сб. научных трудов/ИСЭМ СО РАН Иркутск, 2004. - С. 1114.

25. Тыугу Э.Х. Концептуальное программирование. М.: Наука, 1984. - 256 с.

26. Холдин Ю.И. Сквозь пелену пяти веков. Сокровенная встреча с фресками Дионисия Мудрого. М.: Слово, 2002. - 420 с.31 .Bernstain P. Description problems in the modeling of asynchronous computer systems // Tech. Report / Univ. of Toronto. 1973. -N 48.

27. Dijkstra E. W. Cooperating sequential processes // Programming Languages / NATO Advanced Study Institute. Academic Press, 1968. - P. 43-112.

28. Petri C.A. Kommunication mit Automaten. Schriften fur des Rheinich-Westfalischen Inst. Fur Instrumentalle Mathematik. Univ. Bonn. - Bonn, 1962.

29. Xudong He, John A. N. Lee A methodology for Contructing Predicate Transition Net Specifications // Software Practice and Experience. - 1991. -V. 21, N 8. - P. 845-875.