|
132 переиндексация развернутой сети N, для обеспечения последующего наложения развернутых сетей. На третьем этапе развернутые сети накладываются друг на друга с учетом индексации и образуют развернутую сеть (Nx,N2 ,..., N п), которая затем приводится к “каноническому” виду сетипроцесса путем удаления мертвых переходов и связанных с ними дуг и мест. b Рис. 2.15. Параллельная сеть Пусть N, — последовательная составляющая параллельной сети и начальная разметка сети N, помещает в ее места т фишек. После расщепления N, на т экземпляров последовательных сетей N, к,\ < к < т со стандартной разметкой (единственная фишка в каждой из копий) и их развертки в S -сети N,Л производится переиндексация переходов данных сетей следующим образом. На первом шаге новый индекс получают первые переходы в каждой из сетей. Первый переход в первой сети (Nhi) получает индекс 1. Если первый переход в к -й сети (Nht) не имеет одноименных среди первых переходов предыдущих к -1 сетей (N,л,..., N,, то он также получает индекс 1, в противном случае данный переход получает индекс, на единицу больший максимального индекса среди одноименных первых переходов в предыдущих сетях N,д,..., N,Л_,. На к -м шаге индексируются к -е переходы в каждой из копий. Аналогично индексированию на первом шаге, переиндексация ведется “сверху вниз” с учетом перехода копий; к -й переход в сети N,i7 получает |
63 параллельных сетей показаны на рис. 2.10.а. Процедура развертки параллельных сетей включает три этапа. На первом этапе в исходной сети N = (N^ ,Ыг,..., Ыи) выделяются все ее последовательные составляющие, и каждая из них разворачивается по правилам развертки примитивных сетей с произвольной разметкой (последовательная сеть является честным случаем примитивной сети). На втором этапе осуществляется специальная переиндексация развернутой сети ТУ, для обеспечения последующего наложения развернутых сетей. На третьем этапе развернутые сети накладываются друг на друга с учетом индексации и образуют развернутую сеть (N ^ N 2 7У„) , которая затем приводится к “ каноническому” виду сетипроцесса путем удаления мертвых переходов и связанных с ними дуг и мест. Ь Рис. 2.9. Развертка примитивной сети с произвольной начальной разметкой Пусть /У, — последовательная составляющая параллельной сети и начальная разметка сети Nl помещает в ее места т фишек. После расщепления Ы, на т экземпляров последовательных сетей N1к,1 < к < т со стандартной разметкой (единственная фишка в каждой из копий) и их развертки в 5 -сети производится переиндексация переходов данных сетей следующим образом. На первом шаге новый индекс получают первые переходы в каждой из сетей. Первый переход в первой сети (Ы1Л) получает индекс 1. Если первый переход в к п сети ( М, л ) не имеет одноименных среди первых переходов предыдущих к 1 сетей (Ы1, , то он также получает индекс 1, в противном случае данный переход получает индекс, на 64 единицу больший максимального индекса среди одноименных первых переходов в предыдущих сетях А (>, Т У #Д_,. На к -м шаге индексируются к -е переходы в каждой из копий. Аналогично индексированию на первом шаге, переиндексация ведется “сверху вниз” с учетом перехода копий; к -й переход в сети N , получает индекс 1, если среди всех ранее переиндексированных переходов нет ему одноименных, в противном случае данный переход получает индекс, на единицу больший максимального индекса среди всех ранее занумерованных одноименных переходов. После переиндексации все переходы из множества сетей {И,'к 11< к < т } различны: или переходы имеют разные имена (но могут иметь одинаковый индекс), или если переходы имеют одну и ту же метку, то их индексы (по построению) различны. Все сети N1к,1 < к < т объединяются в одну сеть Ж, путем наложения. При этом ни одна из пар переходов фактически не накладывается, так как все переходы различны. В случае, если число экземпляров т конечно (сеть ТУ, не содержит разметки с со) и ТУ, не является циклом, процесс переиндексации заканчивается за конечное число шагов. В противном случае процедура переиндексации применяется к конечным префиксам разверток циклических сетей. На рис 2.10. показана параллельная сеть ТУ, представляющая собой наложение двух последовательных сетей ТУ, и ТУ2 (рис. 2.10.6). Начальная разметка сети ТУ, помещает в ее места 3 фишки, сети ТУ2— 2 фишки, поэтому сеть ТУ, расщепляется на три последовательные сети ТУи ,ТУ>2,ТУКЗ со стандартной разметкой, сеть Ы 2 — на две сети ТУ2,,ТУ22. На рис. 2.10.в и г показаны сети ТУ, и А 2 после переиндексации переходов и объединения разверток расщеплений в одну сеть. |