Краткие теоретические сведения о сетях Петри

Сети Петри являются мощным инструментом исследования моделируемых систем благодаря их возможности описания многих классов дискретных, асинхронных, параллельных, распределенных, недетерминированных систем, благодаря наглядности представления их работы, развитому математическому и программному аппарату анализа [1].

Она представляет собой разновидность ориентированного графа, включающего в себя вершины двух типов: позиции и переходы. Позиции символизируют состояния и обозначаются как p_i, а переходы обозначают собой действия (переходы из одного состояния в другое) и обозначаются как t_j. Позиции и переходы соединены направленными дугами f_k, каждая из которых имеет свой вес w_k. Дуги также можно разделить на два типа: дуги, направленные от позиции к переходам, (p-t) и дуги, направленные от переходов к позициям (t-p). Исходя из этого, сеть Петри может быть формально представлена как совокупность множеств:

N = (P, T, F, W),

где P = {p₁, p₂… p_n} – множество всех позиций (n – количество позиций),

T = {t₁, t₂… t_m} – множество переходов (m – количество переходов),

F = (F_p-t, F_t-p) – множество дуг сети:

F_p-t = (p´t), F_t-p = (t´p) – множества дуг, ведущих соответственно от переходов к позициям и от позиций к переходам.

W = {w₁, w₂… w_k} – множество весов дуг (k – количество дуг).

Каждая позиция может быть маркирована, т.е. содержать некоторое число фишек. Если обозначить числа фишек, находящихся в i-й позиции p_i, как m_i, то маркировка всей сети: M = {m₁, m₂… m_n}. Тогда полное определение сети Петри, включая данные о начальной маркировке, можно записать в виде:

PN = (N, M₀),

где М₀ – начальная маркировка сети.