Книжка по сетям Петри (547616), страница 27
Текст из файла (страница 27)
Процесс назыаеется гюследоаагельным, если все аго элементы связаны отношением следования, т.е. 'Ф (к, у) Е Х Х Х: х Ну, где Х вЂ” множество элементов процесса. В последовательном процессе отношение следования является ОтнОшением пОлнОГО упорядочения. Процесс мазывается лдоаллельным, еслм любая пара его различных элементов свяэама либо отношением Н, либо отношением со. Процесс наэываетсл последоаагельноальгернагиеным, если любая пара его различных элементов связана либо отношением Н, либо отношением а[.
Процесс называется параллельно-альтернативным, если любая пара его различных элементов связана одним иэ отношений Н, со, а!. Процесс называется параллельным с конкуренцией, вели любая пара его раэлмчных элементов связана одним иэ отношений Н, со, соп. Ниже мы рассмотрим сетевые представления для введенных типов процессов. 5 7.2. Сетевое яредставлевме параллельных процессов В главе 1 .(% 1.2) было введено общее определенна сети, на основе которого строятся различные классы динамических сетей, а том числе сети Пег. ри и сети, представляющие введенные выше типы процессов.
Напомним, чтосеть — это тройка (Р, Т, Р), где Р— непустоа множаство мест, Т- непустое множество переходов, Р— отношение инцидантности. Кроме того, для сетей выполнены следующие условия. 104 А1. Рст Т" ф. А2. (Етьр) Л (тухЕРЦ7, ЗуЕРО Т; хру ЧуРх) (любой элемент сети инцидантен хотя бы одному эламанту другого типа) . АЗ, урырт ЕР: ['рс ~'Рт) Л (р) р)) 'ь Всс рз) ° Для всех рассматриваемых нижа типов сетей, ярадстааляющих процассы, понадобятся общиа дополнение ограничания. Владам вспомогатальныа обозначания: 0[х) — путь а сети, начинающийся элементом х, т.а, конечная или баско. печная посладоватальность (х,, хз...
4 такая, что х х, и Уl й 1: хсрхс+,, 0 ' (х) — обратный путь в сети, заканчивающийся аламантом х, т.в. конечная или басконачная посладоватальность (х„хы ..,) такая, что х х, и ч(>1: х,р 'хс+ы гда Р ' — обращениеотнощанил Р; 0(х, у) — отразок пути, начинающийся элементом х и заканчивающийся у~ 0 ' (х, у) — отрезок обратного пути, заканчивающийся алемантом х и начинающийся элементом у; Н(М) — множество головных мест сети, не имеющих входных ~араходов, т.а. Н[Н) "' [Р !'Р "()) А4. 'Фх,уЕХ~ РОТ: хр'у ь Иур'х), если х чьу, т.а; откованна Р' (транзитианоазамьсканивотнощения Р) не симметрично, свть на содержит циклов. Аб. Н((У) чэ () ЛухЕХ, 1(О '[х): 0 '[х) — коначан.
Зтоограннчанив требует, чтобьс любая сать прадстааляюц[ая процесс, имела иапустоэ множество головных мест и на содержала "бэсконачных влево" путай. Аб. 'багет: стью л с Ф(), т.е, любой переход имаат хотя бы одно входнов и одно выходноа место, / 1, эсли р Е Н(ЛС), ~ О а противном случаа. Сети-процассы имеот начальную разматку, причем стандартную: только головные места содержат по одной фищке. Владам сати, прадставляющиа парэллальные процессы.
Т(враллельноб сетью дайствий нли О сэгье (от английского тармина "оссцггапса пас" [74)) будем называть сеть (со стандартной начальной разметкой), которая наряду с перечисленными еыща условиями А1-АУ удовлатворяат еща одному условию. АВ. ~ДЮРЕР: 1'р((1 Л )р )<1, т.е. кахщоамвотосатиимватнаболвв одного входного и не болаэ одного выходного парахода. Места, на имеющие выходных пераходов, будэм называть хвостовыми маетами сети.
Все места, на входящие в множаство головных или множвстао хвостовых маст, имают ровно по одному входному и одному выходному парвходу. В общем случаа Осэти ьюгут быть басконечными, а сради басконачных сетвй могут быть сати, не имеющие хвостовых мест. легко видать из опрэ. деления О сети, что в случаа, асли сеть конечна, она прадставляат собой частный случай сати Петри, а с учатом структурных ограничаний. она являатся некоторым вариантом ацикличаского синхрониэационнбго графа.
В отличив от посладнаго, гда трабуатся, чтобы )г'Р ЕР. ('Р ! (Р'[ 1, в О.сати каждоа место инцтщантно не болев чам одной входной и выходной дуге. Если казати действий пвранвсти определанна безопасной сати [% 2.1), то ясно, что любая О сать безопасна за счет стандартной начальной разметки и ограничений на топологию сети, задаваамьсх условиями А4, Аб, АВ. Для того чтобы продемонстрировать, что О.сати могут использоваться в качества сетевых представлений параллельных процассов, свяжем поня.
тия, с помощью которьж оярадалялись процассы, с сатевыми понятиями. Бу. !И дем считеть, что имменты процесса прадстевлены в О сети ее элементами, при этом действмл представлены переходами, а изменанил условий — места. ми, Отношание прадшестаовеннл представлено а сети отношением Р'. Тогда отношение сладовенил Н выражаетсл через отношениа Р' следую. щнм образом: «йу ч» (»Р'уогуР'х) Ч(х ~ у), гда х,уЕХ Рц Т. С учетом того, что О сать ациклична ( (»Р'у) )(УР'х) ) отноше.
ние й можно следующим образом выразить чарва отношанне Р: кйу» ь (»Р'у иуРх)' ~у (к ~ у), где х, уЕХ Рц Т, Отношение параллелизма переноситсл на алементы О сети следующим образом: хсоу«» Н(»1(у) ~/ (» у!»» И(«Р~у ~/УР'к) ~/(х у). Например, переходы О сети, показанной на рис, 7,2, неходлтсл между собой в следующих отношенилх: ее В силу рефлексивностиотношений й и ео любой зламент следует сам за собой и параллелен сам себе, Естественным обрезом отношенил И н ео мажду парами элементов обобщмотсл на произвольныа наборьь Пусть У й Х - непустое модмно.
жество множества элементов сати, Множество У наэываетсл пинией, если (ук, у Е У: кйу, те.любыедаа элемента иэ У находлтсл в отношанми следовании. Множество У неэыааетсл Раздлзом, если Ух, у Е У: капу, т.е. любые два элемента из У параплальны, В графнчаском представлении О еетм любые ее зпементьь прннадлежащме некоторой нинин, лежат на на. котором пути а графе сатй, Наоборот, аса элементы, образующие разрез, попарно не соединены никаким путем. В множестве асах пиний О сети вы. делим максимальные, т,е. такие, которые не содержатсл ни в каких других линилх, Их будам называть 1»сеченипми.
В множестве всех разрезов также выделим максимальные и мх будем называть аосаюиипми. В сати на Рис, 7,2 имеотсл следУющие йюечанил (Ры гы Рз. гз. Рз) ° (Рз. гз. Ры гэ Рз) (Рз гз Рч г» Рт) линии (гз Р» гз ) содержнтсл а пинии (Рз гз Рч, Гз, Рз ) И ПсзтОМУ На Лаппатап (ЬСЕЧЕМИЕМ. В атей жс Сатн МНОГО СО СЕ. чаний, поэтому мы не перечисллем асах, только некоторыа: (Ры Рз). (РыРыра). (Рз,лытч) ° (Гытч) Т е о р е м з 2,з, В О сети В «!Р, у, Р, Мч) любав й сеченое и любое свсечелие пераспкаолсв ле бпзме чам пп о0иому зпемзлзту До к а з в т ел ° а та о, Предположим противное: существует!гсаченне А и со сечение С такие, что 1А г'1 С~ > 3.
В этом случае нвйдутсл два зпе. мента к,уЕХ такие,что «,уб1. м к,уЕС По опредмюнию сечений к Ву н одновременно «еоу. но зто может быть толью в том случае, если к у, т.е. ~ и С содержвтединственныйобщнйэлемент, С) Поскольку О'сати объявляются предстааленнлмн пврвллальных процес. сов, возникает вопрос. насколько корректно они представляют процессы этого типа, Сравмениа определений пвраллального лроцвсса и О сати убеждает, что все понлтил, свлзвнныа с процессами, хорошо з)нтерпретмруютал ° терминах сетей. Чтобы установить обратное. следуат выяснить, длл любой лм О сети можно найти подтвернщающмй ее реальный пврвплепьньзй про.
цвсс, Трудность здесь состоит ° том, что формальное понятие сати нужно сравнивать с нвформапизоввнным, мнтуитманым понлтием пареллельного процесса. Однако уже предверительные исследования показали, что сущест. вуют "синтаксически корректные" О свтм, юторыв, если нх проинтарпре. тироввть квк процессы, оказываютсл неприемлемыми в качестве реальных процессов. В связи с этим Патри (74. 77) ввел дополиитмюное условие К-плотмости дпл О сетей, соблюдммю которого позволяет набежать оюзсам. ного выше нвсоответствил между синтаксичаскмм и семантическим аспектами сетевого яредстввленил яроцессов, О.сеть незыааетсл Кчпзолюд, если ° нвй любое й сечение и любое ао се. ченив первсеквютал ровно по одному элементу.
С учетом теоремы 73 это означает, что К. злотнвя сеть не содержит нн одной пары непераеакаощихал йсечвннй м аосеченнй, Легко убедиться нвтосредстванно, что сеть нв рнс. 7.2 К плотна. Пример не.К.платной сати приввдвн нв рнс, 7,3. В этой сети ау. ществует бесконечное Исечвнне (Р,, г„р. гз, Рт, гз...,). катаров не пврасекавтсл с бваконечнымм аочпчанмлми (Рз. Рз, Рз"; ° ). (гз. гз. гз. ° ° ). (Рз, Р„рз..., ) (нв рнс, 7.3 этн сосечанмл показаны пунктмрйыми лм. нилми).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
