|
130 предварительное преобразование расщепления исходной сети на совокупность примитивных сетей со стандартной разметкой. Расщепление осуществляется следующим образом. Пусть т — сумма фишек в начальной разметке исходной сети. Если т = 0, то сеть порождает “пустой” процесс, никак не изображаемый сетями. В противном случае эта сеть копируется в т экземплярах, и каждый из экземпляров сети получает новую начальную разметку по следующему правилу. 1) в каждой копии единственное место имеет ненулевую разметку, равную 1; 2) если место р в некоторой копии имеет фишку, то М0(р)>Ъ в исходной сети; 3) общее число копий, имеющих фишку в месте р , в точности равно Мо(р) в исходной сети. Следующий шаг состоит в индексации переходов и мест в каждом из т экземпляров. Эти экземпляры упорядочиваются произвольным образом и каждый элемент / -го экземпляра (1 < / < т) получает верхний индекс /. На рис. 2.14. показана примитивная сеть 2а;*(Ь;\с). Начальная разметка этой сети <2,0,1 J отличается от стандартной. Исходная сеть преобразована в совокупность трех примитивных сетей, две из которых имеют по фишке в головном месте, а третья содержит фишку во “внутреннем” месте р3. Каждая из копий разворачивается по правилам развертки примитивной сети со стандартной разметкой, причем переходы и места получают второй верхний индекс. В случае, если в некоторой копии фишка содержится не в головном месте сети, как, например, в третьей копии сети развертка осуществляется, как будто фишка находится в головном месте. Затем фишка помещается в первое вхождение р'л (в развертку копии) того места р‘, которое содержало фишку в соответствующей z-й копии исходной сети. Наконец, в развертке / -й копии удаляются все те элементы х (и связывающие их дуги), для которых не выполняется отношение p,,xF*x , т.е. |
61 компонентов: N = (И , ; Ы2 N ,,п) , где п > 1, и для любого 1< / < п , если /V, — циклический (ациклический) компонент, то Ы1+] — ациклический (циклический) компонент. Пусть N = ( Р , Т , Р , М 0) — исходная сеть Петри; условимся в порождаемой сети-процессе Ы = ( Р , Т , Р , М 0) использовать в качестве элементов множества X = Р и Т символы элементов из X = Р и Т с дополнительными верхними индексами. Развертка примитивной сети с произвольной начальной разметкой осуществляется сведением к рассмотренному выше случаю сети со стандартной начальной разметкой. С этой целью производится предварительное преобразование расщепления исходной сети на совокупность примитивных сетей со стандартной разметкой. Расщепление осуществляется следующим образом. Пусть т — сумма фишек в начальной разметке исходной сети. Если т = 0, то сеть порождает “ пустой” процесс, никак не изображаемый сетями. В противном случае эта сеть копируется в т экземплярах, и каждый из экземпляров сети получает новую начальную разметку по следующему правилу: 1) в каждой копии единственное место имеет ненулевую разметку, равную 1; 2) если место р в некоторой копии имеет фишку, то М 0( р ) > 0 в исходной сети; 3) общее число копий, имеющих фишку в месте р , в точности равно М 0( р ) в исходной сети. Следующий шаг состоит в индексации переходов и мест в каждом из т экземпляров. Эти экземпляры упорядочиваются произвольным образом и каждый элемент /-го экземпляра ( \ < 1 < т ) получает верхний индекс /. На рис. 2.9.а показана примитивная сеть 2 а ;* ( Ь ;\ с ) . Начальная разметка этой сети ( 2,0,1) отличается от стандартной. На рис. 2.9.6 исходная сеть 62 преобразована в совокупность трех примитивных сетей, две из которых имеют по фишке в головном месте, а третья содержит фишку во “ внутреннем” месте р . . Каждая из копий разворачивается по правилам развертки примитивной сети со стандартной разметкой, причем переходы и места получают второй верхний индекс. В случае, если в некоторой копии фишка содержится не в головном месте сети, как, например, в третьей копии сети на рис. 2.9.6, развертка осуществляется, как будто фишка находится в головном месте. Затем фишка помещается в первое вхождение р ',] (в развертку копии) того места р ' , которое содержало фишку в соответствующей /-й копии исходной сети. Наконец, в развертке /-й копии удаляются все те элементы х (и связывающие их дуги), для которых не выполняется отношение р ' лР +%, т.е. те элементы, которые не достижимы в развернутой сети при движении от места р ' л вдоль дуг сети. При этом необходима корректировка вторых верхних индексов оставшихся элементов. Для элемента %''' берется новый второй индекс ( у к ) , где к — максимальный индекс удаленного элемента х "к. На рис. 2.9. показана сеть, полученная в результате развертки сети. Развертка примитивной сети с произвольной начальной разметкой может привести к сети, не являющейся Б -сетью, т.е. теорема 7.8 не верна щ для этого случая. Например, сеть на рис. 2.9.в является А -сетью. Для получаемых сетей-процессов выполняется ограничение А10 (см. § 7.3), т.е. каждый переход имеет ровно одну входную и ровно одну выходную дуги, но нарушается требование А9 к £ -сети иметь ровно одно головное место. В то же время теорема 7.9 остается верной и для случая примитивной сети с произвольной разметкой. Рассмотрим развертку подкласса регулярных сетей, которые мы назовем параллельными сетями. Параллельная сеть N представляет собой наложение последовательных сетей NХ,Ы Nп, каждая из которых является простым путем или простым (регулярным) циклом. Примеры |