Книжка по сетям Петри, страница 32

В то же время теорема 7Э остается верной и для случая примитив. ной сети е произвольной разметкой. Рассмотрим резвартку подкласса регулярных сетей, которые мы назовем гареллепьными сетями. Параллельная сеть л( представляет собой наложение последовательных сетей д(ы Иы..., гу„, каждал иэ которых лвпяется простым путем илн щюетым (регулярным) циклом. Примеры параллельных сетей показаны на рис. 7.12, е н 7.1З. е. Процедура развертки па. раллельных сетей включает трн этапа.

На первом этаяе в исходной сети (у (И,, Фы..., Э„) выделяются вса ае посладовательные составляющие, и каждая из них разворачивается по правилам резаертки примитивных сетей е произвольной разметкой (поелаювательная сеть явпяетел частным случаем примитивной сати) . Не втором этапе осуществляется специальная пареинлаксзция развернутой сети Щ для обеепечанил последующего наложения развернутых сетей. На третьем этапе развернутыа сети накладываются друг на друга с учетом индексации и образуют развернутую сеть (Ф,, Й,,..., Й„), которая затем приводится к "каноническому" аиду сети.процесса путем удаления мертвых переходов и связанных с ними дуг и мает.

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

Первый нарежу в первой сети (Йп г ) получает индекс \. Если первый переход в х й сати Щ «) на имщт одноименных еради первых переходов предыдущихх — !сетей (мг ы...,л)~ ь,), то он также получает индекс 1. в противном случае денйый переход получает индекс, на единицу больший максимального индекса среди одноименных первых переходов в предыдущих сетях Й,,,..., В, „ 1И е) Знв. 7.12. На К м щаге индексиру«тол А"е переходы а каждой из копий, Аналогично индекснрованм«на первом щаге, перещщексацил аадетсх "сверху вниз" с учетом пере«зле коей; А й пережщ в сети Фс) полу «ет индекс 1, есин сре.

ди всех ренее нервно(ексированных переходов нет ему однонманйых, в про. тианом случае данный переход получает индекс, на единицу больщий макси. ь«и»ного индексе среди всех ранее занумерованных одноименных переходов. после пераимвексации асе переходы из множества сатай (Й»» ! 1 с л с гп! различны: нли переходы имеет разные имена (но могут имать одинако° ый индекс(, или если пареходы иммет одну и ту же метку, то их индексы (по построен«о! резличны.

Все сети Эг», 1 (А С лг, обьадннп«тол в одну сеть Йг путем наложении. При этом ни одна из пер переходов фектнчаски на накладыааетсл, так кек асе переходы различны, В случае, если число зкземпллров пт конечно (сеть Иг не содержит раз. метки с ьг! и И, не лвппетсп циклом, процесс перенндексзцни ааканчиезетсл за конечное число щагов. В противном случае процадура переиндаксации применлетсл к конечным префиксам резверток циклических сетей.

На рис. 7.12, е показана парвплепьнаж сеть И, предстзаллщщзп собой наложение двух последовательных сетей И~ и И» (рис. 7.12. б!. Начальнел разметка сети Иг помещает ° ее маета 3 фищки, сети Ит -2 флаки, поетому сеть Иг раещащлетсл не трн посладовательныесети Игл, Иг,з, Иг,з со стандартной раэмйткой сеть Ит - на две сети Из „Из д, Нз рйс, 7,12, е и з показаны сети И~ и !((Ь после пертнкйанаацнн ПЕРеходов н объаднненил разверток расщеплений в одну сеть. После того как асе составлпющна сети расщеплены, рзщвьрнутти ц пара.

индексованы, произаодитсл "выравнивание" числе накладываемых пере. 1И ходов, Если ° сети Юг мексимепьный индекс у перехода а равен 1ы а в сети ~~ максимальный икаакс у того же перехода равен 1з и [з <1ы то в сеть У~ добавляжтсп 1~ — (т копий сети ФГ с нулевой разметкой всех мест, Прн атом все вхождении перехода г индексируатсл описанным выще способом, начинал с индексе Цт + 11, Такое выравнивание числа вхождений перехо. дов произвадитсл длл всех пареходов, входлщих одновреыенно в сети Щ и Ир и длл асах пар сетей, составллещнх сеть 1д На рнс, 7,1 2, Ь показана сеть У~ меле выравнивании числа вхождений перехода с, В сеть лгз добавлена "пустел" копил сети Нт, и переходе получил ° ерхний индекс 3, Предпоследний зтап щстоит ° построении сети гт (Юы Йз..

° ° . Ю,) пу. тем обьадинанил выравнанных разверток ссставллжщих атей Фы Юз,... ,... 1тч в одну сеть с помощыс операции наложении, При выполйений опе. рации наложенил вхожденил одинаковых символов переходоа с одинако. выми верхнимн индексами совмещиотсл по общим правилам опереции на. поженил. 13зьжтнм, что алесь операцил наложения из % 6.1 обобщена на случей бесконечных сетей,] йа рнс. 7ДЕ, е показан ° сеть |т ~ 99„Жз), полученнал наложением се- тей1К нгт,, Последний степ состоит в приведении полученной ° результате сети к форме, удовлетвщинощей требоааннлм, праамвллемым к сеглы процес. Рмч. т,!3.

сем. Дело в том, что в результате наложения в результирующей сети могут появиться головные масте баз фищек. "Чистка" полученной сети состоит в удалении из сати таких головных мест и всех тех элементов сети, к которым можно прийти из головных мает по путям вдоль дуг. На рис. 7,12, ж показана сеть Ф = (Й,, Й, ) яоспе чистки. Эта сеть является О сетью и пред. ставляет параллельный процесс функцяонировения параллельной сети.

изображенной на рис. 7.12, е. На рис. 7.13 показана параллельная сеть с циклами, Осеть, являющаяся результатом развертки предыдущейсети, и некоторые промежуточные этапы развертки. Осеть на рис. 7.13. з не является К.плотной и поэтому не К. щетка и параллельная сеть на рис, 7,13,а (она является регупяризованной версией синхронизационнога графа) . Причиной не-К.плотности этой сати служит неограниченность мест рч и Рт, Анализ описанного преобразования развертки параллельных сетей позволяет сформулировать следующие два утверждения: Т а о р е м а 7.10. Результатом развертки параллельной сети является О сеть, Т е о р а м е 7.11.

(. Ю) С (В, Х), где (. (Ф) — свободный язык помеченной сети-развертки. е которой У г): Х (г) ) Процедура развертки произвольной регулярной сети здесь не описывается. Она состоит иэ тех же этапов, что и процедура развертки параллель. ной сети, но этап переиндексацин усложняется и требует топологических праобразований )юзверток составляющих примитивных сетей. На рис.

7.14 приведены примеры регулярных (и легко регуляризуемых) сетей, которые раэворачиаеются в Асети, рассмотренные в предыдущих параграфах. Например, сеть на рис. 7.14, а на является К-плотной, так как разворачивается а не-К.плотную Осеть, структура которой показана на рис. 7.3 (с точностью до именования переходов); сеть на рис. 7Л4, б разворачивеетсл в (, плотную 8 сеть на рис.

7.6, а; сеть на рнс. 7Л4, е разворачивается в не-(.-плотную 3-сеть на рис. 7.6, б; что же касаетсп сети, изображенной а) Рнь. 7.14. на рис. 7.14, д, то ома не является ниКч ни ). ч ни Мгппотной, так как таки- ми свойствами обладает А сеть на рис. 7.9, б н зта А сеть являетсп разаерт. кой предыдущей сети, $7.8. Сетевое вредсмвлювю паралледьцмх процессов с квцк)грещвюй Сети, предназначенные для описания параллельных процессов с конкуренцией, строятся на основа О сетай е добавлением в них специальных мает, называемых ресурсами, и дуг, связывающих зтн места е переходами особым способом. В сети )У (Р, Т, Е), удовлетворяющей условиям А1-АВ, назовем интервалом подсеть I (Рл Тл Ег), для которой вьмюлнемы следующие условия: 1) имеется переход Гь Е Т, который служит началом интервала; 2) имеется переход Г, Е Т, который служит концом интервала, причем гьЕ'г,~/гь =г,; 3) Тг (ге Т)гье'ТАтЕ'г,), т.е.

множество переходов интервала включает все переходы сети, а которые имеетсп путь от перахода гь и одновременно от которых ммеетея путь в сети до перехода г,„ 4) Рг (РЕ Р (гь Е РЛРЕ+г ), т.е. множество мест интервала включает все места сети, в которые есть путь па графу сети от перехода гь и от которых есть путь до перелаза г; б) Е, Е гт (Рт Х Тг О Тг Х Рг); В) для любого х Е (Р ц Т) ~ (Рг НТг) ме существует пути в сети М от х до у Е (Рг О Тт), не содержащего перехода гь, и не существует пути от у до х. ме содержащего перехода г,.

Таким образом, интервал образует подсеть, которую в теории графа на. зыаают гамаком, причем лри движении по графу внутрь гамака нельзя попасть. минуя аго начало, а из гамака нельзя выйти, минуя его конец. Если гь т„то нмтарвал состоит из единственного лерахода. Интервал г сати )У е начвюм Гь и концом Г, будем обозначать! (Гь, Г ). Тот факт, что ( является интервалом сети ЛГ, будем обозначать! ~)У.

Ясно, что в любой сети имеются тривиальныа мнтараалы, состоящие из единственного пера. ходе. Сеть ма рис. 7.4,а имеет единственный нетривиальный интервал с началом г, и концом г. птот интервал является бесконечной подсетью. В сетях на рис. 7.4,б,7.2и7.3 нет нетривиальных интервалов. й(ажно показать, что в Ф-платной О сети любой интервал конечен. Сетью действие с конкуренцией (или ОСсегью) назовем сеть виде )У (Р» О Р,, Т, Е» '»' Е, Мь), в которой: 1! Рг — множество мает, называемых расуреами, и Р» Г1Р, Ф; 2] Е» С (Р» Х ТН ТХ Р»), Е С(Р, Х Ти Т Х Рт) 3! подеетья)» (Р» Т,Е,.М»(Р»ЯпредстзвляетеобойОсетгн 4) ерЕР,,; Мч(Р) 1,т.е.

всеместаресурсыизР„имеютединичную раз. метку; б) ФРЕ Р,: ! Р ! )Р'! > 1, т.е. из каждого места ресурса выходит столька же дуг, сколько и входит, но всегда ресурс имеет минимум яо две входной и по две выходной дуги; 8! УреР;. (Уг, ер' Зг, еР:)Мыгт) — интервал в подсати дейстВмй )У т И Етз Е Р, В Г, 4Р: I(Г,, Гт ! — ИмтЕРаап В ПРВЕЕти ДвйетВИй Д)»). На рис.