Ординарные сети Петри

Сеть Петри общего вида C = (P, T, E, W, M₀) является ординарной, если кратность любой ее дуги равна единице:

" e Î E: W(e) = 1.

Для возбужденных переходов в ординарной сети выполняется условие:

" t_j Î T " p_i Î I(t_j): M(p_i) ³ 1.

Переход сети в новое состояние выполняется по правилам:

" p_i Î I(t_j): M⁺(p_i) = M(p_i) - 1, t_j Î T;

" pi Î О(t_j): M⁺(p_i) = M(p_i) + 1, t_j Î T;

" p_i Ï (I(t_j) È O(t_j)): M⁺(p_i) = M(p_i), t_j Î T; p_i Î P.

Для ординарных сетей можно использовать специальное обозначение

C = (P, T, E, M₀),

в котором отсутствует кратность дуг W, а элементы P, T, E, M₀ представляют соответственно множества позиций, переходов, дуг и начальную разметку.

Класс ординарных сетей по определению является сужением класса сетей общего вида. Однако, относительно существенной части своих свойств сети этих двух классов остаются эквивалентными. Так, сеть C общего вида преобразуется в ординарную сеть C с сохранением присущих исходной сети свойств живости, ограниченности, консервативности, безопасности.

На рисунке дан пример преобразования сети с кратными дугами в эквивалентную ординарную сеть. Каждой вершине p_i Î P сети на левом рисунке ставится в соответствие кольцевая структура на правом рисунке. Число вершин в кольцевой структуре

определяется из условия

d(p_i) = max{W(t_j, p_i) + W(p_i, t_j)}; p_i Î P, t_j Î T.

t_j Î T

d(p₁) = max{(0+2), (0+1), (3+1)} = 4;

d(p₂) = max{(0+3), (1+0), (2+2)} = 4.

Множество позиций ординарной сети находится как объединение всех позиций, образующих кольцевые структуры. В примере - это позиции p_1i , p_2i , i = 1, 2.

сеть общего вида

ординарная сеть

Множество переходов ординарной сети включает все переходы исходной сети и множества переходов, входящих в кольцевые структуры. На рисунках - это переходы t₁, t₂, t₃ и переходы в кольцевых структурах.

Дуги в кольцевых структурах определяются естественным способом. Всякой дуге e_ij Î (P´ T) È (T´ P) сети C, имеющей кратность W(e_ij), в ординарной сети соответствует W(e_ij) дуг единичной кратности, соединяющих по входу (или выходу) переход t_j c позициями i -й кольцевой структуры.

Если W(e_ij) = d(p_i), то t_j будет связан дугой с каждой позицией кольцевой структуры. Если W(e_ij) < d(p_i), то t_j будет связан с какими-то (любыми) W(e_ij) позициями из имеющегося набора p_{i, 1}, p_{i, 2},..., p_{i, d(pi )} позиций i-й кольцевой структуры.

Начальная разметка сети C отображается на ординарную сеть С согласно правилу:

M₀(p_i) = ∑ M₀(p_ik), p_{i, k} Î P, k = 1,.., d(p_i)

p_ik Î P_i.

Если в состоянии M(s) Î M(C) сеть С имеет возбужденный переход t_j Î T, то в ординарной сети этому будет соответствовать состояние M(s) Î M(C), при котором окажется возбужденным переход t _j Î T, связанный по входу с кольцевой структурой:

" p_i Î I(t_j): å M(p_ik) = M(p_i)

p_ik Î P_i