Книжка по сетям Петри (547616), страница 20
Текст из файла (страница 20)
Целые неотрицательные числа. и в том числе О, кодируются признаками из бесконечного множества. В результате возникает возможность изобразить разметку я7 ~о! Мес~а р, в том числе нулевую разметку, фишкой с соответствующим признаком. Таблицы срабатываний задаются таким образом, что переход получает возможность реагировать на отсутствие "обычной" фишки э некотором месте за счет того, что в этом месте присутствует Фишка с признаком, соответствующим нулю.
75 Еща одна модификация сетей связана с изменанием правила функционирования со тей - смяхрюииью саги. В этом случае работа сети разбивается на такты. В начале каждого такта выясняется, какиа переходы могут А сработать (по стандартным условиям сраба. тываний), из них выбирается некоторое мак. симальное множество Т' взаимно наконфликтующих переколов, т,е.
для которых справедливо следущцюе утверждение: г 1ГР Е Р. 'Е Р(р, г) С М(Р). гв т' Затем все такие переходы срабатывают ° любом порядке, изменяя разметку сети обыч. гг ным образом. На этом закенчиааетсл такт, энс. в,т. после чего начинается новый такт яри новой. разметка. Подчеркнем, что внутри такта выбранное множество срабатывающих пгзтеходоа не меняется. Если посла срабатывания части из выбранных переходов появит. ся переход, который может сработать по стандартным условиям. он надобаа.ляется к выбранным.
(После срабатывания части пераходоа разметка не мо. жег изманитыж так, что для одного из выбранньж, но не среботевших переходоа перестанут выполняться условия срабатывания.) Другими словами, сребатыаания выбранных переходов внутри такта не мешает друг другу и не оказывают влияния на ситуацию других пареходов.
Такое изменение правил функционирования затей приводит к увели. чению их выразительной мощности до уровня машин Тьюринга. Чтобы убедиться а этом, достаточно похвать, каким образом аыражаетсл сред. ствами синхронных сетей оперетор условного вычитания единицы счетчике. ваго автомате. На рис Б.2 яокаэен соответствующий фрагмент синхрон. ной сати. Если М(Р,! 1, ° М(х~) ~ О, то после срабатывания яерехода гг маета р ~ и рз имеет единичную разметку, но может сработать только переход гз. Затем срабатывает с4 и окончательно фишка поступает ц место ру, Если М(рг) ° 1 и М(хг) 1, то после срабатывания парахода г~ могут сработать переходы гз и гз.
В обычных ~а~я~ Па~пи ~о~но раэревшть сребатывание перахода гт и затем перехода гч (пока не сработал лареход гз, ° масте рз остаетсл фишка). Но в синхронной сети вместе с гз должан сработать пареход ты Это приведет к тому, что пареход гч не сможет затем сработать (место рт лишилось фишки), но ~рабо~ае~ переход гт» поместит фишку в место РР. В сетях с приоритетами и в синхронных сетях наметился отход от чисто локального принципа управления функционированием сети, принятого ° сетях Петри, и переход к привлечанию болев глобальной информации о состолнии сети.
6 сервам случае это информация о статичаских прис. ритетех тех переходов, которые могут сработать по стандартным условиям, ео втором — о множестве всех переходов, которью готовы сработать при денной разметке. Именно в силу привлечения данных о глобальной ситуации а систаме и возрастает выразительная мощность сетай. Аналогичный подход просматрнвеетсл в смюмпдм4Ьнируамых сетя» Фалька (66, 66]. В сетях этого клеюа кахщой дуге (р, с) и (г, р) прн.
писана модифицируемал кюпюсгь У(Р, г) или УВ, Р). Если кратность дуги — число, то оно имеет тот жа смысл, что н кратность ° определении сатей Петри (см. $1.2), Но а качестве кратности может выступить символ 2Е ф Рис. ЬЗ л, вели хру л (г(х, у) ° л, где п-число, Рн(х,у) М(г(), вели эру л (Р(х,у) С, глас-симеон места, О, если "((хну). Введение модифицируемой кратности позволяет достаточно просто моделировать ингнбиторныв сети и сети с приоритетами. На рис. 6,6 показано, каким образом ингнбиторнал дуга и фрагмент сати с,приорнтатамн трансформируются во фрагменты самомодифицирувмых сегал. В первом случае использован тот факт, что переход с может сработать а том случае, вали его входное место р имеет нулевую разметку, но лри текущай разметке м значение Р„(р, т) М((Р(р, г) ) М(р') О, где р' — добавленное в сеть место с "фиктивным" переходом гг, без входящих в р дуг и с разметкой, постоянно(юа«ой О.
Во втором случае место рв вжжэет ипи не алияат на готовность перехода гэ к срабатыванию в зависимости от разметки маета р, и входного места "конкурирующего" пврехода г,. В результате на свмомодифнцируемыв сати распространяются утверждения из % 6.2, т.а. зтн сети порождают класс рекурсипно пвречислимых языков, и основные сетевые проблемы для них неразращнмы, С некоторого места данной св. ти. В этом случае кратность Р Р Р Р дуги паременна и рвана те. кущей разметке М(С) места С.
т О Поскольку разметка места С может динамически меняться в процессе работы сети, то н к(ютнссть тех дуг, которым ртг,нэпт сопостеелен симВОл о. дина. мическн мвнпвтсл. В результа. тв число фищек, пвремвща- А емых одним и тем же переходом от входных мест к вы. ходным местам, динамически меняется при разных срабатываниях этого перехода. Правило срабатывания перехода с изменяется следующим обрезом: ур б *Г: М(р) ~ (Г(р. Г). где У (и, г) е л, если дуга (р, г) помечена числом л > 1, н У (р, г) е М(С), если дуге (р, г) помвчана символом маета ф Правило изменения разметки сети посла срабатывание пераходэ Г вы. глядит так: СРЕР: ДГ(Р) - М(Р)-рн(Р,Г)+Рн(Г,Р), где ем — модифициРУемал фУнкциЯ ннцндвнтностн, опРеделЯамаа следУющнм.
образом (сравните с определением функции ннцидентности Р и $1.2): ГЛАВА 6 РЕГУЛЯРНЫЕ И ИЕРАРХИЧЕСКИЕ СЕТИ Сеть Петри определена в главе 1 как набрр, состоящий из множеств мест и переходов, отношения инцидентности и функции начальной разметки. Такой способ задания сетей обычен дпя постановки и решения теоретических задач анализа сетей. Графовую форму представления сетей Петри удобно применять в иллюстративных целях, Однако оба зти способа представления сетей не подходят для прикладных задач моделирования дискретных систем, например, для задач, включающих автомати.
ческий анализ, синтез и преобразования сетевых моделей с помощью ЭВМ. Болев удобным оказывается или матричное, или аналитическое представление сетей. В первом случае сеть Петри 7У (Р, Т, Р, Ме) задается двумя целочисленными матрицами: А, размерности (Р ! Х ! Т ), и В, размерности ! Т ! Х ! Р (, и вектором Мс длины ! Р !. Строка г', 1 ыг' ч ! Р (, матри- цы А соответствует местург Е Р, столбецу, 1 </ 4! Т(, матрицы А соответствует переходу т е т (множества Р и т строго упорядочиваются!.
Строка А 1. < г ч ! Т (, матрицы В соответствует переходу г; Е Т, столбец 7, 1 </ < ! Р ), матрицы В соответствует месту Р( Е Р. Элемент А (г', /! ыатрицы 4 равен Р ~оп г(), элемент В(г, 7) матрицы В равен Р(г,, р(). Вектор Мс — это вектор начальной разметки (см. % 1.2) . Аналитическое представление сети Петри задает ее с помощью формулы в некоторой алгебре сетей (8, 58!.
Эта формула построена из символов, задавших некоторыа элементарные сети, и сетевых операций, с помощью которых описываемая сеть может быть построена из элементарных сетей. Предложенная в работах (8, 887 алгебра сетей порождает класс регулярных сетей', для которых характерно топологически регулярное строение, и дает возможность расчленить процесс анализа и конструирования сетей на совокупность этапов, на каждом из которых достаточно иметь дело с более простыми фрагментами сети. Класс регулярных сетей формально является подклассом сетей Петри за счет топологичаских ограничений (ограничения на отношение инцидент- ности), которые возникают при аналитическом способе задания сетей. Однако будет показано, что этот класс эквивалентен по порождаемым языкам классу (ординарных] сетей Петри.
Во второй части главы рассматривается обобщение регулярных сетей— иерархические сети, предназначенные для адекватного моделирования иерархических динамических систем. Будет показано, что иерархические сети обладают такой же выразительной мощностью, что и ингибиторные сети или сети с приоритетами. ' К сожалению. термин "регулярные сети" был также неаееисимо использован (В7! длл обоенеченил классе сетеа Петри, пороноиюныл регуллрнью лэыки. В денноа книге он будет употреби лтьсл только е перлом смысла, 7В В главе 8 мы вернемся к алгебре регулярных и иерархических сетей кок к средству описании семантики структур управления асинхронных параллельных программ, не основе которого разреботвны прогроммные механизмы упревления вычислениями в языках параллельного прогреммировения.
5 бЛ. Алгебра регуларпых сетей Алгебра регулярных сетей строится е помощью операций над сетямн и классе элементарных сетей. Элементеризя сеть — это сеть вида — О где в — символ-переход, е — головное место элементарной сети,7 — ее хвостовое места В формульном представлении элэментарнел сеть обозначается символом перехода а. В классе регулярных сетей, который будет определен ниже, обобщено понятие разметки.
Множество всех целых неотрицательных чисел расширено за счет введения элемента ы (см. % 1.2), который используется кэк разметка мест сети и обозначает "неограниченное число фишек" в денном месте. Такое обобщение является формальным, ток кок место с разметкой со можно удалить из сети со всеми инцидентными дугами.
Нопример, следующие сати эквивалентны и обледеют одинаковыми свойствами: Введение мест с "бесконечной разметкой" позволит топологически структурировать сети Петри, не сужая, по существу, класс рассматриваемых сетей. Определим операции нед сетями. Пусть И(9) обозначает множество головных мест сети >У„а 1 (>У! — множество ее хвостовых мест. (Ниже указывается правиле изменения множеств И (1У) и 19У), которые могут считаться индуктивными определениями множеств головных и хвостовых мест сети.) Опереция наложения ", ". Это ояереция — обычное теоретико-множественное объединение графов, дополненное правилом формирования разметки; с помощью втой операции одна сеть ноклэдывается на другую.
Если)у> = (Р,, Т„Е,,Мо>) ийг (Рг, Тг. Ег, Мог),то )У " (>У>, Д(г ) "' (Р> Н Рм Тг О Тг, Е> О Ег. Мо ) .где 1 Мо>(Р) . если р Е Р,, где 1 = 1, 2, и Р р Р, Г > Рг, Мо(р) = ~ пнп (Мо> (в)ю Мог(Р) ) если Р ЕР> >1 Рг. Пример выполнения операции наложения показам норис.6.1,э. По определениюосерации,И(Ф) И()У>! >.>И((Уг),1(ЛП ! (>У>)>.>1()Уг). Операция Разьмтки "и( ) ".
Мы россматрнваем агу операцию кок укорную. Онэ представляет собой, по существу, множество операций, задаваемых параметром л — целым нчотрицательнь>м числом или символом со "бесконечного числе" фишек. Сеть Д( л(Д>) совпадает кэк граф с Мч (г! ~ Ме (хг) + Мз (у> ! и соответствующими инцидентными дугами. Пример выполнения операции слияния показан на рнс. 6,1, е. Продолжим определение операций над сетями.
Операция итерации "ь". Эте операцнл унарнел, она сливает множество головных и множество хвостовых мест сати и применима к сети И, асли множества головных и хвостовых мест не пересекеютсгн И' ч(Н) " л(И, Ь(Н), ((Н)), где Ь(И) (1 ((И! 6. По ояределанию множества головных и хвостовых мест сети И ° (Н) совпадают друг с другом и с множеством мест, полученных слиянием головных и хвостовых мест исходной сати. Пример аьюопнения операции итерации показен парис. 6,1, з. Риь 6.2. Оперж(ил лроооедилеяол "; ". Эте операция соединяет дее сети в одну, сливая множество хвостовых мест первой сети со мжииаством головных мает второй сети: И (И~; Из) Л((Иы Из), ((И~), Ь(Из)).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
