129 установлена, можно следующим обрезом перенести на сети Петри определения тех свойств, которые были введены для сетей-процессов. Будем говорить, что сеть Петри является плотной (К -,L -,М -плотной), если порождаемая ею сеть-процесс является плотной {К L-, М -плотной). Сопоставление сети Петри порождаемой сети-процесса будет рассматриваться как результат некоторого преобразования развертки исходной сети. Поскольку сеть, задающая процесс, может быть в общем случае бесконечной, то процедура развертки сводится к построению некоторого префикса сети-процесса, заканчивающегося указанием на бесконечное повторение ее периодического фрагмента. Назовем циклическим компонентом примитивной сети N ее максимальную циклическую подсеть N' такую, что Vy е X I е X': ^(xF+y л yF\). Любой циклический компонент представим в виде формулы сети, начинающейся операцией итерации *. Максимальная подсеть сети N, не содержащая внутри ни одного циклического компонента, образует ациклический компонент. Любую примитивную сеть М можно представить как конечную чередующуюся последовательность циклических и ациклических компонентов: N = (Nx ;N2 ;...NПп), где п > 1, и для любого 1 < i < п , если N, — циклический (ациклический) компонент, то Nl+l — ациклический (циклический) компонент. Пусть N = (P,T,F,Mq) — исходная сеть Петри; условимся в порождаемой сети-процессе N = (P,T,F,Ma) использовать в качестве элементов множества X = Р u Т символы элементов из X = Р u Т с дополнительными верхними индексами. Развертка примитивной сети с произвольной начальной разметкой осуществляется сведением к рассмотренному выше случаю сети со стандартной начальной разметкой. С этой целью производится |
60 2.4. Моделирование интеграции приложений на основе развертки сетей Петри в сети-процессы Введение обобщенных процессов, в которых действия и изменения условий могут быть связаны не только отношениями следования и параллелизма, но и отношениями альтернативы и конкуренции, позволяет ставить вопрос об установлении взаимно-однозначного соответствия между сетями Петри и порождаемыми ими сетями-процессами. Когда связь установлена, можно следующим образом перенести на сети Петри определения тех свойств, которые были введены для сетей-процессов. Будем говорить, что сеть Петри является плот ной ( К -плот ной), если порождаемая ею сеть-процесс является плотной ( К -, Ь -, М -плотной). Сопоставление сети Петри порождаемой сети-процесса будет рассматриваться как результат некоторого преобразования развертки исходной сети. Поскольку сеть, задающая процесс, может быть в общем случае бесконечной, то процедура развертки сводится к построению некоторого префикса сети-процесса, заканчивающегося указанием на бесконечное повторение ее периодического фрагмента. Для сети Петри, являющейся конечной сетью, удовлетворяющей ограничения А1-А7, преобразование развертки тривиально: исходная сеть и порождаемая ею сеть-процесс совпадают. Назовем циклическим компонентом примитивной сети N ее максимальную циклическую подсеть Ы' такую, что Уу е X 1Х ' , 3 * е Г : Г х ^ +У а у ^ +Х Л Любой циклический компонент представим в виде формулы сети, начинающейся операцией итерации *. Максимальная подсеть сети N , не содержащая внутри ни одного циклического компонента, образует ациклический компонент. Любую примитивную сеть м можно представить как конечную чередующуюся последовательность циклических и ациклических 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 исходная сеть |