Введем понятие сети Петри. Только напомним, что N  множество натуральных чисел, а N+  множество положительных натуральных чисел.

Определение 7  Сетью Петри (СП) называется система  N=(S,T,F,W,M0)где

  • (S, T, F) — конечная сеть;
  •  W:FN+функция кратности дуг;
  • M0:S N — начальная маркировка.

Пример сети Петри показан на рис. 1.9.

По сравнению с сетью правило срабатывания перехода в СП модифицируется с учетом функции кратности дуг.
Введем вспомогательные обозначения для узлов x,yX:

F(x,y)={W(x,y),(x,y)F,0,иначе.

Если места сети упорядочены, то каждому переходу tT можно сопоставить следующие два вектора:

F(t)=(a1,...,an), где ai=F(si,t)(1in),

F(t)=(b1,...,bn), где bi=F(t,si)(1in),

где n=|P|. Для перехода t1 СП, изображенной на рис. 1.9, имеем, что F(t)=(1,1,0,0,0) и F(t)=(0,0,1,2,0).

Переход tT  разрешен (может сработать, готов к срабатыванию) при маркировке M, если

st    M(s)F(s,t) или MF(t).

Переход t1 СП, изображенной на рис. 1.9, может сработать при маркировке (1,1,0,0,0).

Срабатывание  перехода  t  при маркировке  M  порождает новую маркировку  М'  (обозначается как M [t> M') по следующему правилу:

sS   M(s)=M(s)-F(t,p)+F(t,p) или M=M-F(t)+F(t).

Срабатывание перехода t1 СП, изображенной на рис. 1.9, при маркировке (1,1,0,0,0) порождает маркировку (0,0,1,2,0).

Последовательность переходов σ=t1t2...tr называется  последовательностью срабатываний  сети Петри (N,M0), если существует последовательность M0t1M1t2M2 ... trMr такая, что i,1ir    M(i-1)[ti>Mi. В этом случае говорят, что маркировка Mr  достижима  из M0 последовательностью срабатываний σ (обозначается как M0[σ>Mr). Множество маркировок, достижимых из M0, обозначается как [M0>. Маркировка называется  достижимой  в сети Петри, если она достижима из начальной маркировки.

Сформулируем некоторые поведенческие свойства СП.

СП (N,M0) называется

  • k-ограниченной (ограниченной), если существует натуральное число  k  такое, что для любого места  s  и для любой достижимой маркировки в СП ерно M(s)=k. Если СП 1-ограничена, то ее называют  безопасной,
  • S-живой, если для любого места  s  и для любой достижимой маркировки  M  в СП существует достижимая из  M  маркировка  М', которая маркирует место  s,
  • M-живой, если для любой достижимой маркировки  M  в СП существует некоторый переход  t, который может сработать при  M,
  • живой, если для любого перехода  t  и для любой достижимой маркировки  M  в СП существует достижимая из  M  маркировка  М', при которой переход  t  может сработать,

СП, избраженная на рис. 1.8, является 2-ограниченной и обладает всеми перечисленными свойствами живости. Тогда как СП на рис. 1.9  хотя и является ограниченной, но не обладает ни одним свойством живости.