П р о ц е д у р а

1. М₀ = (M₀(p₁), M₀(p₂),., M₀(p_{½ P½} )) - начальная разметка сети Петри. Она обозначает корневую вершину дерева достижимости.

2. M = (M(p₁), M(p₂),., M(p_{½ P½} )) - разметка сети Петри, обозначающая граничную вершину дерева достижимости, еще не обработанную данной процедурой. Применяя процедуру к граничной вершине, можно получить варианты:

2.1. M - концевая терминальная вершина дерева, если при M нет возбужденных переходов;

2.2. M - концевая дублирующая вершина дерева, если в уже построенной части дерева существует вершина, имеющая разметку, совпадающую с M;

2.3. M - разметка, при которой оказываются возбужденными один или несколько переходов. Для всякого t_j Î T, разрешенного в M, должна быть построена новая граничная вершина дерева, представляющая разметку

M⁺ = (M⁺(p₁), M⁺(p₂),., M⁺ (p_{½ P½} )),. M M⁺,

непосредственно достижимую из M. При этом маркировки позиций в разметке M⁺ определяются по следующим правилам:

2.3.1. Если M(p_i) = w, то M⁺(p_i) = w, p_i Î P; Символ w означает возможность получения как угодно большого числа маркировок M⁺(p_i) вследствие циклического запуска перехода t_j;

2.3.2. Если на пути от M₀ к M в уже построенной части дерева найдется вершина, представляющая разметку

M^- = (M^-(p₁), M^-(p₂),., M^-(p_{½ P½} )) такую, что

M^- < M⁺ и M^-(p_i) < M⁺(p_i), то M⁺(p_i) = w, p_i Î P;

2.3.3. В случаях, отличных от рассмотренных в пп. 2.3.1 и 2.3.2, маркировки позиций новой разметки сети M⁺ находятся обычным образом:

M(p_i) + W(tj, p_i), p_i Î O(t_j), t_j Î T;

M⁺(p_i) =

M(p_i) - W(p_i, t_j), p_i Î I(t_j); t_j Î T.

3. Процедура прекращает работу, если дерево достижимости не содержит граничных вершин.

Ограниченность. При моделировании систем, функционирование которых связано с процессами перемещения (передачи) и накопления материальных ингредиентов (единиц информации), действуют ограничения на вместимость накопителей или общее допустимое количество единиц материального (информационного) потока в системе.

Позиция p_i Î P сети Петри C=(P, T, E, W, M₀) является S-ограниченной, если существует число S Î N такое, что

" M_k Î M(C, M₀): M_k(p_i) £ S.

Сеть Петри называется S-ограниченной, если любая её позиция S - ограниченная. Особый случай - ограниченность сетей при S = 1. Такие сети называются безопасными. Любая достижимая на безопасной сети разметка задается вектором из нулей и единиц.

Консервативность. Свойство ограниченности тесно связано со свойством сохранения (консервативности) сетей Петри. В сохраняющих сетях общая сумма меток всех позиций остается постоянной величиной на любом шаге выполнения сети. Это означает, что при срабатывании любого перехода общая сумма меток не изменяется и остается равной сумме меток позиций сети в её начальном состоянии. В общем виде свойство сохранения определяется равенством вида:

" M_k, M_r Î M(C, M₀): å _i a_i M_k(p_i) = å _i a_i M_r(p_i), a_i Î N, p_i Î P,

(a₁, a₂,., a_|P|) - вектор весов. При (a₁, a₂,., a_|P|) = (1, 1,., 1) в сети выполняется " строгое сохранение":

" M_k, M_r Î M(C, M₀): å _i M_k(p_i) = å _i M_r(p_i)), откуда следует:

" t_j Î T: |O(t_j)| = |I(t_j)|.

Проблема ограниченности сетей Петри разрешима. Полезным инструментом анализа ограниченности является дерево достижимости сети. С его помощью можно проверить безопасность и S- ограниченность отдельных позиций и сети в целом, а также установить, какие именно позиции данной сети являются в ней неограниченными (позиции с маркировкой w).

Проблема сохранения в сетях Петри также разрешима. Для сохраняющей сети выполняются равенства

å _i a_i M_k(p_i) = å _i a_i M₀(p_i), M_k Î M(C, M₀).

Переходя к матричным представлениям, получим M_k a^T = M₀ a^T.

Поскольку M_k = M₀ + m(s)R, где R - матрица сети, то Ra^T = 0. Тем самым сеть Петри будет сохраняющей тогда и только тогда, когда существует вектор весов a = (a₁, a₂,., a_|P|) с положительными компонентами (a_i > 0), удовлетворяющий уравнению Ra^T = 0.

Активность, живость, тупики. Всякий переход t_j Î T сети Петри будет активным, если в этой сети существует разметка M_k Î M(C, M₀), при которой данный переход может сработать.

Переходы различаются по уровням активности. Тупиковые (пассивные) переходы имеют активность нулевого уровня.

Переход, получающий в сети возбуждение, обладает активностью первого уровня. Переход t_j Î T называют живым, если для любой исходной разметки M₀ в сети достигается разметка M_k Î M(C, M₀), при которой этот переход получает возбуждение. Сеть C = (P, T, E, W, M₀) - живая, если все её переходы живые.

Переход t_j Î T характеризуется активностью второго уровня, если для произвольно взятого числа n Î N в сети Петри с начальной разметкой M₀ существует последовательность срабатываний s, в которой переход t_j будет запускаться не менее n раз.

Переход t_j Î T относится к переходам третьего уровня активности, если в сети Петри возможна бесконечная последовательность срабатываний, в которой t_j будет запускаться неограниченное число раз.

Переход t_j Î T имеет четвертый уровень активности, если при любой разметке M_s, достижимой от M_k, в сети Петри возможна последовательность срабатываний переходов, в результате выполнения которой установится разметка M_r, обеспечивающая запуск перехода t_j.