Сеть Петри

Графы специального вида, получившие название “Сети Петри” были впервые предложены Карлом Петри в 60-х годах для моделирования систем, которые содержат взаимодействующие и параллельно функционирующие компоненты.

Карл Адам Петри (нем. Carl Adam Petri; 12 июля 1926 — 2 июля 2010) — немецкий математик и исследователь в области информатики.

Он описал сети Петри в 1962 году в рамках диссертации. «Kommunikation mit Automaten» (взаимодействие с автоматами).

Работал с 1959 по 1962 год в Боннском университете, в 1962 году получил степень доктора философии в Дармштадтском университете.

Труды Петри стали существенным вкладом в развитие параллельных и распределённых вычислений, способствовали исследованиям сложных систем и потоков работ.

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

Все вершины графа относятся к одному из двух классов - позициям и переходам. , О

Либо начало дуги совпадает с позицией и тогда конец этой дуги совпадает с переходом, либо наоборот.

C = (P, T, I, O).

P = {p1, p2,... pn} – конечное множество позиций,

T = {t1, t2,... tm} – конечное множество переходов

I: T → P∞ ‑ входная функция.

O: T → P∞ ‑ выходная функция

Это отображения из множества переходов в множество объединений комплектов позиций. (Комплект ‑ подмножество мультимножества, состоящее из одного или более одинаковых элементов.)

Кратность входной (выходной) позиции pi для перехода tj есть число появлений позиции во входном (выходном) комплекте перехода.

Позиции изображаются окружностями, переходы - отрезками прямой. Каждая дуга связывает вершины только разных классов.

P = (p1, p2, p3, p4, p5, p6) T = (t1, t2, t3, t4, t5)

I(t1) = (p1) O(t1) = (p2, p3)

I(t2) = (p3) O(t2) = (p3, p5, p5)

I(t3) = (p2, p3) O(t3) = (p2, p4)

I(t4) = (p4, p5, p5, p5) O(t4) = (p4)

I(t5) = (p2) O(t5) = (p6)

Сеть Петри – это структурная схема – статическая модель системы.