Книжка по сетям Петри (547616), страница 28
Текст из файла (страница 28)
Прммвр О-сети нв рмс. 7,3 хорошо иллюстрирует, а чвм состоит несоответствие мвжду синтаксисом н семантикой в не К.плотной сети, В соотввтатвми со структурой сати ° нвй сущастауют указаннью бесконечные со сечению Это означает, например, что все переходы сечения (гз, гч, г„...) взаимно параллельны и сущаствует конкретнал вре* меймвл реапимцил задаваемого сетью процессе. в которой все действия гз, гч, гз,... могут произойти одновременно. С другой стороны, фишке РвапРостРанлетслМольбесконечного Вьсечвнил '(Рм Гм Ры Гз,...) по* следовательно, и сюслазоавтвльно поступают фишки в места рз, Рз. Рз..., Этот прачзазю запмненнл всех мест рз, рз, рз..., фмнзками никогда не может завершнтыж, и поэтому потенциальный, "тмюлогвчвскнй" парвплв.
лизы действий гы гы гз,... не может ° дайстаиталыюстм раалмзоветьсл, Таким образом, О сеть на риа, 7,3 не описывает реальный параллельный знв, 7.2, знз, 7.3, за7 Ф Рис. 7.4, процасс. Ещв один пример О-сати, которая нв являвтся К.плотной, пока. зан на рис, 7,4, а, В этой сети результат нвсоотввтствия топорогнчаского сатваого параллелизма отношению параллвлизма в процвссвх яриаодит к тому, что переходу г нв соотеатствуат никакого двйствия.
Действительно, ПОСКСЛЬКУ 1!'СВЧВНМВ (Ры Гыры Гырт, Гы ° ° .) На ПВРаоамаатол С СО Сава. нивм (Ры Р4, Рз,... ), то никогда нв может случиться, чтобы всв входные маста пврвхода т имели разметку, отличную от О. Поэтому пврвход с мертв. В приввдвнных примврэх нв К.плотныа О.сати бесконечны. На рис. 7.4, а привадан пример также бвсконвчной сати, но эта сеть К-плотна. Сладующал творама говорит о том, что нв К.плотной сетью может быть только бвсконвчнал О сеть, Т во р в м а 72.
Любая ксначнал О сеть К.плотна, Д о к а з а т в л ь с т а о. Првдположим, что сущвстеувт коначнов со.свчвнив С и конечное П.свчвнив 1 такив. что СГ11 =Ф. Любой злвмвнт П.евчанпл 1 на можат быть параллвлан асам элементам со сечения С, так как в противном спучаа сущвстаовало бы со-сачлнив содвржсщав С. Разобьем 1 на два линии 1, и 1т так, чтобы в 1~ входили всв тв,злвменты х Е 1, для каждого иэ которых существует в С апвмант у такой, что хР'у, а в 1, входили бы всв тв злвманты к, дпя кюкдого иэ которых в С сущаствуат элемент у такой, что уР х. Другими словамн, в 1, входят элвмвнты, "прадшаствующив" сечению С, а е 1т входят зламвнты, "следующие за" свчвннвм С. Замвтмм, что 1, Н1, ФФ.
В 1~ н 1т элементы можно частично упорядочить в соотввтствии с отношвниам Р'. Гзк как 1, и 1, конвчны, то в 1, сущвствувт "максимальный" в этом упоря. дочвнии зламвнт х. а в 1т сущвствувт "минимальный" в этом упорядочании элемент к". Пусть 1, Ф Ф, э 1т ф, Тогда множество 1, О (у') 10(у'), гдв у'ЯС, и к'Р'у'образувтлннию, содержащую 1, и, слв. доватвльно, 1 нвявлявтся Псвчанивм, что противоречит првдположанию. Аналогичныв рассуждания приводят к яротиворвчию в случае 1тчьф. Еслм 1, чьй и 1т тьр, то а С существуют элементы у и у такие, что к'Р'у и у"Р'х".
Прн у' у у линия 1, О (у) О 1т 1 О(у) содэржит 1, поэтому 1 нв лалявтся 1)чючвнивм, что приводит к противоречию. Если жану чь у", то в 1 должэн существовать элвмвнт к такой, что хр'х и хР'х". Он нв принадлежит ни 1„нм 1,. н вновь образуатся линия, содвржащап 1, что противоречит условию првдположв. ния. (:7 1св Т а о р е м в 7.З. В К.плотной О-сети, камдыд переход котород имеет конечноа мнокгвстао екодоа, любод переход грабатыават роаео один рая До к а катал ьст а о.
Любое Н-сачаниа а О-сати содарентединстланную фишку при любой достижимой разметка. Действительно, а силу условия Аб пюбоз Н сечзниа начинаатся некоторым головным местом, содержащим фишку. При срабатывании некоторого парохода г в сети возможны рва случая: г принадлежитданному Н.сачанию Ь или г не принадпепит лму. В перлом случаа с обязательно параместит фишку из своаго входного ызста, принздлвжащего (., а слов выходное масто, также принадпвжащае Ь. Во втором случаа фишка остаатся в прежнем маете сечанил Ь.
Поэтому О.сеть безопасна. Разобьем множестао Т пареходоа сати на "ярусы" следующим образом: Ть (т) г~Н(Н)), Тз (т((уг Е'(2); с'Е Т ЛТ<з) л(Вг Е '('г): г Е Тз 1)). Яруе Тч ОбраэуЮт тэ ПаракпдЫ, ВСа ВХОдНЫВ Маота КОтОРЬщ яаляштая одновреманно головными мастами сети. Ярус Тк образуют те параходы, входныв места которых являются выходными местами переходов из ярусов с мвньшими комарами. причем хотя бы одно входное место яалявт. ся выходным мастом некоторого парахода из яруса Тк.
ы Заметим, что Т О Т,, так как для любого парахода гЕ Т сущаствуат комар З тат о кой, что Г Е Тк. Этот номер можно опраделить спвдующим образом. Пусть ((, .... 1.;) — множастао всех путай, ведущих из некоторого головного маста сати к пароходу с Кехдый из этих путей конечен, алли О пать К-плотна. Последний факт является следствием таорамы о Дискретности К.плотной О-сети, доказанной в работах (21, 23) .
Дискретной названа сать, не содержащая басконачных отрезков ! ьсечений, соединяющих даа зпамен. та к и у сати, т.е. на содержащая бесконечных поспапоаатальностай к, к„ к,,..., с, у, гдв к Е 'к,, к, Е к,,..., к Е у Наприьер, сать на рис. 7,4, а нв дискратнв, так как содержит бесконечный отрезок (Рн Гн Рз, гы Рт, гз, ° ... Л . Тогда 4 = ~пах()(.~ ),...,)А;))/2 — 1. Покажам тепарь индукцией по номару яруса, что любой пареход из любого яруса срабатывает ровно один раз. Легко ведать, что зто утаврждение спрааедлиао для всех г Е Ты Пусть оно справедливо для асах пароходов из ярусов Тр гда / < ». Тогда дпя любого р Е 'г, где г — пераход из пруса ТА, возможны следующие два случая.
8 перлом р Е Н(Н) и. следовательно, для любой достижимой разметки М такой, что М„(т)М и т несо. дэржит Г, имает масто М(р) = 1. Во втором случае В г' е Тр 7 < Д и р Е е(т)', Так как по првдположанию г может сработать, то сущаствуют т и М такие, что М„[ т')М'. т заканчивается пвреходом Гг и ' М (р) = 1. Замвтим, что измвнить разматку входных маст первхода с адиничной на нулевую не можвт никакой другой переход, крома савзого г, в силу условия АВ. Так как число к коначно, то по прадположеею достижима разметка М такая, при которой всв входные места яарехода получат по одной фишке и он можвт сработатгь причем только один раз, так как аго аходнью места не смогут больша получить фишки а силу условий А4 и АВ. П Проиплюстрируам на яримарах необходимость успоаий таоремы 7.З. На рис. 7.4, 6 приаедам примзр сати, каждый пароход которой имаэт конечное множество входных мает.
В данном спучаа причиной того, что пароходы Ь,, Ь,, Ь,„... не могут сработатгь является нв-Кчвотность исходной сети. Любой переход Ь| может сработать только посла выполнвмя после- доватепьностн переходов а„а,, аз,..., но эта последовательностьбесконечна. В )Гчзпотной сети на рмс. 7,4, е переход Ь имеет бесконечное множество входов. Переходы а и Ь в данной сети соединены бесконечным множеством конечных путЫ1.
Длина каждого отдельного мути ограничана, но не еущаствуат такого натурального числа )г, которое одноаременно ограничивало бы длины всех данных путей. В силу этогопроцаес запоя. пения фишкамн входных мест перехода Ь никогда не может быть закон. чен, н переход Ь не может сработать в данной сем, $73. Сетевое прелставлеппе послелователмю альтерввтмвпмх пропахав Дополним условия А1-А7 в общем определении сетей процессов епе.
дующими ограничениями, А9.(бб[)УЦ 1, сеть имеет адинетвенноа головное масто. А10. Ч т Е Т: (.г(-1Л(г(-1, те. любой переход сети имеет ровно одно входное и одно выходное место. Сети, удовлетворяющие перечисленным условиям. назовем пееледоеагю)ьно.апьтарнашенмми сетями дедегеид, ипи Знатями. В общем случае Зюети могут быть бееконечнымн, а конечные сети ярадетавпяют собой ацикпичеекие автоматные сати е единичной разметкой в единственном го.
поеном места (ем. % 42! . Из условий А9 и А10 следует, что 8 сати представляют связный граф. Точно тек же, как н в случае О сетей, 8 сати явпяютея некоторой еннтексической формой представления процессов, а именно — поспедоватапьноапьтернатмвных процессов. Отношение следования 11 выражается че(юз отношение Р' в 8 сетях так же, как н в случае О сетей, Отношение апьтерна. тнвы а1 выражается дпя элементов Зюети через отношение Р' следующим образом: х Ы у» э 1(х 11 у! Ч (х у1» ° 1(х Р«у Ч ур«х1 Ч (х» у1.
Дпя Зсетей можно определить понятие Неечения, и это определанна полностью совпадает с определением 11<ачання дпя О сетей, Множество Я элементов 8 сети назовем аньгернатианым разрезом, если Ч х, у Е А: х Ы у, т.е. пюбыа два апемента мз А альтернативны, В графнчаском представлении Везти все элементы, образующзм альтернативный разрез, попарно на соединены никаким путам.
В множестве всех разрезов 8 сети выделим макенмапьмые, т.е. такие, которые не содержатся ни в каких других, и будем на. зывать нх айеченинми. На рис.7.б,а показена 3 сеть. в которой мме. ются следующие 1!.сеченип: ( р„г „ Рз. Гз. Рз. т«. Яа. тз. Рб. ° ° З). (Р) ° тз. Рз. гы Рз ° ° ° 1 н епе д) дуюмзием.сечення: (т), гз(. ( Рз, а..(. (бз. гз(, (т,. тб(. (Р«. гз(. ( т,.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
