сеть Петри

Сеть Петри , также известная как сеть мест/переходов ( PT-сеть ), является одним из нескольких математического языков моделирования для описания распределенных систем . Это класс дискретно-событийной динамической системы . Сеть Петри представляет собой ориентированный двудольный граф , имеющий два типа элементов: места и переходы. Элементы места изображаются в виде белых кружков, а элементы перехода — в виде прямоугольников. Место может содержать любое количество жетонов, обозначенных черными кружками. Переход разрешен, если все места, подключенные к нему в качестве входов, содержат хотя бы один токен. Некоторые источники утверждают, что сети Петри были изобретены в августе 1939 года Карлом Адамом Петри — в возрасте 13 лет — с целью описания химических процессов.

Подобно отраслевым стандартам, таким как UML диаграммы деятельности , модель и нотация бизнес-процессов , а также цепочки процессов, управляемых событиями , сети Петри предлагают графическую нотацию для пошаговых процессов, включающих выбор, итерацию и одновременное выполнение . В отличие от этих стандартов, сети Петри имеют точное математическое определение семантики их выполнения и хорошо развитую математическую теорию анализа процессов. .

(a) Пример траектории сети Петри

Историческая справка

Немецкий ученый-компьютерщик Карл Адам Петри , в честь которого названы такие структуры, подробно проанализировал сети Петри в своей диссертации 1962 года « Kommunikation mit Automaten» .

Основы сети Петри

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

Графически места в сети Петри могут содержать дискретное количество меток, называемых токенами . Любое распределение жетонов по местам будет представлять собой конфигурацию сети, называемую маркировкой . В абстрактном смысле, относящемся к диаграмме сети Петри, переход сети Петри может сработать, если он включен , т. е. во всех его входных позициях имеется достаточное количество токенов; когда переход срабатывает, он потребляет необходимые входные токены и создает токены в своих выходных местах. Запуск является атомарным, то есть одним непрерываемым шагом.

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

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

Формальное определение и основная терминология

Сети Петри — это системы переходов состояний , которые расширяют класс сетей, называемых элементарными сетями.

Определение 1. Сеть – это кортеж. $N=(P,T,F)$ где

1. P и T — непересекающиеся конечные множества мест и переходов соответственно.
2. $F\subseteq (P\times T)\cup (T\times P)$ представляет собой набор (направленных) дуг (или отношений потока).

Определение 2. Для сети N = ( P , T , F ) конфигурация — это множество C такое, что C ⊆ P .

Сеть Петри с разрешенным переходом.

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

Определение 3. Элементарной сетью называется сеть вида EN = ( N , C ), где

1. N = ( P , T , F ) — сеть.
2. C такова, что C ⊆ P — конфигурация .

Определение 4. Сеть Петри — это сеть вида PN = ( N , M , W ), расширяющая элементарную сеть так, что

1. N = ( P , T , F ) — сеть.
2. M : P → Z мест — мультимножество , где Z — счетное множество . M расширяет концепцию конфигурации и обычно описывается со ссылкой на диаграммы сетей Петри как маркировку .
3. W : F → Z дуг — мультимножество , так что количество (или вес) каждой дуги является мерой кратности дуг .

Если сеть Петри эквивалентна элементарной сети, то Z может быть счетным множеством {0,1}, и те элементы в P , которые отображаются в 1 под действием M, образуют конфигурацию. Аналогично, если сеть Петри не является элементарной сетью, то мультимножество M можно интерпретировать как представляющее неодноэлементный набор конфигураций. В этом отношении М расширяет концепцию конфигурации элементарных сетей на сети Петри.

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

справа) позиция p1 _{На верхнем рисунке (см .} является входной точкой перехода t ; тогда как позиция p ₂ является выходной точкой того же перехода. Пусть PN ₀ (верхний рисунок) будет сетью Петри с разметкой, настроенной M ₀ , а PN ₁ (нижний рисунок) будет сетью Петри с разметкой, настроенной M ₁ . Конфигурация PN ₀ обеспечивает переход t благодаря тому свойству, что все входные позиции имеют достаточное количество фишек (показанных на рисунках точками), «равных или превышающих», чем кратности на соответствующих дугах до t . Переход сработает только один раз и только после того, как переход будет включен. В этом примере запуск перехода t генерирует карту, которая имеет маркировку, настроенную M ₁ на изображении M ₀ , и приводит к сети Петри PN ₁ , как показано на нижнем рисунке. На диаграмме правило срабатывания перехода можно охарактеризовать путем вычитания из его входных позиций количества фишек, равного кратности соответствующих входных дуг, и накопления нового количества фишек на выходных позициях, равного кратности соответствующих входных дуг. выходные дуги.

Замечание 1. Точное значение слова «равно или больше» будет зависеть от точных алгебраических свойств сложения, применяемых к Z в правиле стрельбы, где тонкие изменения алгебраических свойств могут привести к другим классам сетей Петри; например, алгебраические сети Петри.

Следующее формальное определение во многом основано на ( Peterson 1981 ). Существует множество альтернативных определений.

Синтаксис

Граф сети Петри ( называют его сетью Петри некоторые , но см. ниже) представляет собой трехкортеж $(S,T,W)$, где

• S — конечное множество мест
• T — конечное множество переходов
• S и T , не пересекаются т.е. ни один объект не может быть одновременно местом и переходом.
• $W:(S\times T)\cup (T\times S)\to \mathbb {N}$ является мультимножеством дуг , т.е. каждой дуге присваивается неотрицательная целочисленная кратность дуги (или вес); обратите внимание, что никакая дуга не может соединять два места или два перехода.

представляет Отношение потока собой набор дуг: $F=\{(x,y)\mid W(x,y)>0\}$. Во многих учебниках кратность дуг может быть только 1. В этих текстах сети Петри часто определяются с F вместо W. использованием При использовании этого соглашения граф сети Петри представляет собой двудольный ориентированный граф. $(S\cup T,F)$ с узловыми S и T. разделами

Предустановка — перехода t это набор его входных позиций : ${}^{\bullet }t=\{s\in S\mid W(s,t)>0\}$;его постсет — это набор его выходных мест : $t^{\bullet }=\{s\in S\mid W(t,s)>0\}$. Определения пре- и пост-наборов мест аналогичны.

Разметка сети Петри (графа) — это мультимножество ее мест, т. е. отображение $M:S\to \mathbb {N}$. Мы говорим, что маркировка присваивает каждому месту определенное количество жетонов .

Сеть Петри (некоторые называют ее маркированной сетью Петри , см. выше) представляет собой четырехкортежную сеть. $(S,T,W,M_{0})$, где

• $(S,T,W)$ – граф сети Петри;
• $M_{0}$ — начальная разметка , разметка графа сети Петри.

Семантика выполнения

На словах

• запуск перехода t в маркировке M потребляет $W(s,t)$ токены из каждого из своих входных мест s и производит $W(t,s)$ фишки в каждом из его выходных мест s
• переход разрешен (он может сработать ) в M , если на его входных позициях достаточно фишек, чтобы потребления были возможны, т. е. тогда и только тогда, когда $\forall s:M(s)\geq W(s,t)$.

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

Будем говорить, что разметка М' достижима из разметки М за один шаг , если $M{\underset {G}{\longrightarrow }}M'$; мы говорим, что оно достижимо из M, если $M{\overset {*}{\underset {G}{\longrightarrow }}}M'$, где ${\overset {*}{\underset {G}{\longrightarrow }}}$ это замыкание рефлексивное транзитивное ${\underset {G}{\longrightarrow }}$; то есть, если он достижим за 0 или более шагов.

Для (маркированной) сети Петри $N=(S,T,W,M_{0})$, нас интересуют обжиги, которые можно выполнить, начиная с начальной разметки $M_{0}$. Его набор достижимых разметок — это набор $R(N)\ {\stackrel {D}{=}}\ \left\{M'{\Bigg |}M_{0}{\xrightarrow[{(S,T,W)}]{*}}M'\right\}$

Граф достижимости N представляет собой соотношение перехода ${\underset {G}{\longrightarrow }}$ ограничено достижимыми отметками $R(N)$. Это пространство состояний сети.

Последовательность запуска сети Петри с графом G и начальной разметкой $M_{0}$ представляет собой последовательность переходов ${\vec {\sigma }}=\langle t_{1}\cdots t_{n}\rangle$ такой, что $M_{0}{\underset {G,t_{1}}{\longrightarrow }}M_{1}\wedge \cdots \wedge M_{n-1}{\underset {G,t_{n}}{\longrightarrow }}M_{n}$. Набор последовательностей срабатывания обозначается как $L(N)$.

Вариации определения

Распространенным вариантом является запрет кратности дуг и замена набора дуг W простым набором, называемым отношением потока , $F\subseteq (S\times T)\cup (T\times S)$.Это не ограничивает выразительную силу , поскольку оба могут представлять друг друга.

Другой распространенный вариант, например, у Деселя и Юхаса (2001): заключается в том, чтобы позволить мощности определять на местах. Это обсуждается в разделе «Расширения» ниже.

Формулировка в терминах векторов и матриц

Маркировка сети Петри $(S,T,W,M_{0})$ можно рассматривать как векторы целых неотрицательных чисел длины $|S|$.

(б) Пример сети Петри

Его переходное отношение можно описать как пару $|S|$ к $|T|$ матрицы :

• $W^{-}$, определяемый $\forall s,t:W^{-}[s,t]=W(s,t)$
• $W^{+}$, определяемый $\forall s,t:W^{+}[s,t]=W(t,s).$

Тогда их разница

• $W^{T}=-W^{-}+W^{+}$

может использоваться для описания достижимых разметок с помощью матричного умножения следующим образом.Для любой последовательности переходов w напишите $o(w)$ для вектора, который отображает каждый переход в количество его вхождений в w . Тогда у нас есть

• $R(N)=\{M\mid \exists w:\ w{\text{ is a firing sequence of }}N\ {\text{ and }}\ M=M_{0}+W^{T}\cdot o(w)\}$.

Должно потребоваться, чтобы w было последовательностью срабатывания; разрешение произвольных последовательностей переходов обычно приводит к увеличению набора.

$$W^{-}={\begin{bmatrix}*&t1&t2\\p1&1&0\\p2&0&1\\p3&0&1\\p4&0&0\end{bmatrix}},\ W^{+}={\begin{bmatrix}*&t1&t2\\p1&0&1\\p2&1&0\\p3&1&0\\p4&0&1\end{bmatrix}},\ W^{T}={\begin{bmatrix}*&t1&t2\\p1&-1&1\\p2&1&-1\\p3&1&-1\\p4&0&1\end{bmatrix}}$$

$$M_{0}={\begin{bmatrix}1&0&2&1\end{bmatrix}}$$

Теоретико-категорная формулировка

Месегер и Монтанари рассматривали своего рода симметричные моноидальные категории, известные как категории Петри .

Математические свойства сетей Петри

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

Обзор таких проблем принятия решений с результатами по разрешимости и сложности для сетей Петри и некоторых подклассов можно найти в Esparza and Nielsen (1995).

Доступность

Проблема достижимости сетей Петри состоит в том, чтобы решить, учитывая сеть Петри N и маркировку M , $M\in R(N)$.

Это вопрос обхода графа достижимости, определенного выше, до тех пор, пока либо не будет достигнута запрошенная маркировка, либо ее больше нельзя будет найти. Это сложнее, чем может показаться на первый взгляд: граф достижимости обычно бесконечен, и нелегко определить, когда можно безопасно остановиться.

На самом деле эта проблема оказалась EXPSPACE -hard. за несколько лет до того, как было показано, что она вообще разрешима (Mayr, 1981). Продолжают публиковаться статьи о том, как сделать это эффективно. В 2018 году Червинский и др. улучшил нижнюю границу и показал, что проблема НЕ ЭЛЕМЕНТАРНАЯ . было показано, что эта проблема не является примитивно-рекурсивной . В 2021 году независимо от Жерома Леру и Войцех Червинский и Лукаш Орликовский. Таким образом, эти результаты устраняют давний разрыв в сложности.

Хотя достижимость кажется хорошим инструментом для поиска ошибочных состояний, для практических задач построенный граф обычно содержит слишком много состояний для расчета. Чтобы облегчить эту проблему, линейная темпоральная логика обычно используется в сочетании с методом таблиц, чтобы доказать, что такие состояния недостижимы. Линейная темпоральная логика использует технику полурешения, чтобы определить, действительно ли состояние может быть достигнуто, путем нахождения набора необходимых условий для достижения состояния, а затем доказывания, что эти условия не могут быть удовлетворены.

живость

Сеть Петри, в которой переход $t_{0}$ мертв, хотя для всех $j>0,$ $t_{j}$ является $L_{j}$-жить

Сети Петри можно охарактеризовать как имеющие разную степень живости. $L_{1}-L_{4}$. Сеть Петри $(N,M_{0})$ называется $L_{k}$-живым тогда и только тогда, когда все его переходы $L_{k}$-живой, где переход

• мертв , если он никогда не сможет выстрелить, т. е. он не находится ни в какой последовательности выстрелов в $L(N,M_{0})$
• $L_{1}$-live ( потенциально срабатываемый ), тогда и только тогда, когда он может сработать, т.е. он находится в некоторой последовательности срабатывания в $L(N,M_{0})$
• $L_{2}$-live, если он может срабатывать сколь угодно часто, т.е. если для каждого положительного целого числа k он встречается как минимум k раз в некоторой последовательности срабатываний в $L(N,M_{0})$
• $L_{3}$-live, если он может срабатывать бесконечно часто, т.е. если существует некоторая фиксированная (обязательно бесконечная) последовательность срабатываний, в которой для каждого положительного целого числа k переход $L_{3}$ встречается не менее k раз,
• $L_{4}$-live ( живой ), если он всегда может сработать, т.е. $L_{1}$-жить в каждой доступной разметке в $R(N,M_{0})$

Обратите внимание, что требования становятся все более строгими: $L_{j+1}$-живость подразумевает $L_{j}$-живость, т. ${\textstyle \textstyle {j\in {1,2,3}}}$.

Эти определения соответствуют обзору Мураты: который дополнительно использует $L_{0}$-Живой как термин для мертвых .

Ограниченность

Граф достижимости N2 .

Место в сети Петри называется k-связанным , если оно содержит не более k фишек во всех достижимых разметках, включая начальную; говорят, что оно безопасно, если оно 1-ограничено; оно ограничено, если оно k-ограничено для некоторого k .

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

Сеть Петри ограничена тогда и только тогда, когда ее граф достижимости конечен.

Ограниченность разрешима, рассматривая покрытие и строя дерево Карпа -Миллера.

Может оказаться полезным явно установить границы для мест в данной сети.Это можно использовать для моделирования ограниченных системных ресурсов.

Некоторые определения сетей Петри явно допускают это как синтаксическую особенность. Формально сети Петри с емкостью мест можно определить как кортежи $(S,T,W,C,M_{0})$, где $(S,T,W,M_{0})$ представляет собой сеть Петри, $C:P\rightarrow \!\!\!\shortmid \mathbb {N}$ присвоение мощностей (некоторым или всем) местам, а отношение перехода является обычным, ограниченным разметками, в которых каждое место с емкостью имеет не более такого количества фишек.

Неограниченная сеть Петри N .

Например, если в сети N обоим местам присвоена емкость 2, мы получим сеть Петри с емкостью мест, скажем N2 ; график его достижимости показан справа.

Двуограниченная сеть Петри, полученная расширением N «встрочными местами».

Альтернативно, места можно ограничить, расширив сеть. Если быть точным,место можно сделать k -ограниченным, добавив «противоместо» с потоком, противоположным потоку места, и добавив жетоны, чтобы получить сумму в обоих местах k .

Дискретные, непрерывные и гибридные сети Петри.

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

Расширения

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

Термин « сеть Петри высокого уровня» используется для обозначения многих формализмов сетей Петри, которые расширяют базовый формализм сетей P/T; сюда входят цветные сети Петри, иерархические сети Петри, такие как сети внутри сетей , и все другие расширения, описанные в этом разделе. Этот термин также используется специально для типа цветных сетей, поддерживаемых CPN Tools .

Ниже приводится краткий список возможных расширений:

• Дополнительные типы дуг; два распространенных типа
  • дуга сброса не накладывает предварительных условий на срабатывание и очищает место при срабатывании перехода; это делает достижимость неразрешимой, в то время как некоторые другие свойства, такие как прекращение, остаются разрешимыми;
  • запрещающая дуга накладывает предварительное условие, согласно которому переход может срабатывать только тогда, когда место пусто; это позволяет выражать произвольные вычисления с количеством токенов, что делает формализм Тьюринга полным и предполагает существование универсальной сети.
• В стандартной сети Петри фишки неразличимы. В цветной сети Петри каждая фишка имеет значение. В популярных инструментах для цветных сетей Петри, таких как CPN Tools , значения токенов вводятся, их можно тестировать (с использованием защитных выражений) и манипулировать ими с помощью функционального языка программирования . Дочерней структурой цветных сетей Петри являются хорошо сформированные сети Петри , в которых выражения дуги и защиты ограничены, чтобы облегчить анализ сети.
• Еще одним популярным расширением сетей Петри является иерархия; это в форме различных взглядов, поддерживающих уровни утонченности и абстракции, было изучено Фелингом. Другая форма иерархии встречается в так называемых объектных сетях Петри или объектных системах, где сеть Петри может содержать сети Петри в качестве своих маркеров, создавая иерархию вложенных сетей Петри, которые взаимодействуют посредством синхронизации переходов на разных уровнях. Видеть для неформального знакомства с объектными сетями Петри.
• Система векторного сложения состояний (VASS) представляет собой формализм, эквивалентный сетям Петри. Однако поверхностно ее можно рассматривать как обобщение сетей Петри. Рассмотрим конечный автомат , в котором каждый переход помечен переходом из сети Петри. Затем сеть Петри синхронизируется с конечным автоматом, т. е. переход в автомате осуществляется одновременно с соответствующим переходом в сети Петри. Совершить переход в автомате можно только в том случае, если соответствующий переход в сети Петри разрешен, а запустить переход в сети Петри можно только в том случае, если в автомате, помеченном им, имеется переход из текущего состояния. . (Определение VASS обычно формулируется несколько иначе.)
• Сети Петри с приоритетом добавляют приоритеты переходам, в результате чего переход не может сработать, если включен переход с более высоким приоритетом (т. е. может сработать). Таким образом, переходы находятся в группах приоритета, и, например, группа приоритета 3 может сработать только в том случае, если все переходы отключены в группах 1 и 2. Внутри группы приоритета срабатывание по-прежнему недетерминировано.
• Недетерминированное свойство оказалось очень ценным, поскольку оно позволяет пользователю абстрагировать большое количество свойств (в зависимости от того, для чего используется сеть). Однако в некоторых случаях возникает необходимость моделировать не только структуру модели, но и время. Для этих случаев были разработаны синхронизированные сети Петри , в которых есть синхронизированные переходы и, возможно, несинхронизированные переходы (если они есть, то несинхронизированные переходы имеют более высокий приоритет, чем синхронизированные). Дочерней структурой временных сетей Петри являются стохастические сети Петри , которые добавляют недетерминированное время за счет регулируемой случайности переходов. Экспоненциальное случайное распределение обычно используется для «времени» этих сетей. В этом случае граф достижимости сетей можно использовать как цепь Маркова с непрерывным временем (CTMC).
• Дуалистические сети Петри (dP-Nets) — это расширение сети Петри, разработанное Э. Дэвисом и др. чтобы лучше представить реальный процесс. dP-сети уравновешивают двойственность изменения/неизменения, действия/пассивности, (преобразования) времени/пространства и т. д. между двучастными конструкциями сети Петри преобразования и места, что приводит к уникальной характеристике маркировки преобразования , т. е. когда трансформация "работает" отмечено. Это позволяет преобразованию запускаться (или помечаться) несколько раз, отражая реальное поведение пропускной способности процесса. Маркировка трансформации предполагает, что время трансформации должно быть больше нуля. Нулевое время преобразования, используемое во многих типичных сетях Петри, может быть математически привлекательным, но непрактичным для представления реальных процессов. dP-Nets также использует возможности иерархической абстракции сетей Петри для изображения архитектуры процессов . Сложные системы процессов моделируются как серия более простых сетей, связанных между собой различными уровнями иерархической абстракции. Архитектура процесса коммутатора пакетов продемонстрирована в: где требования к разработке организованы вокруг структуры проектируемой системы.

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

Ограничения

Типы сетей Петри графически

Вместо расширения формализма сетей Петри мы можем также рассмотреть его ограничение и рассмотреть конкретные типы сетей Петри, полученные путем ограничения синтаксиса определенным образом. Обычные сети Петри — это сети, в которых все веса дуг равны 1. Кроме того, обычно используются и изучаются следующие типы обычных сетей Петри:

1. В конечном автомате (SM) каждый переход имеет одну входящую и одну исходящую дугу, и все метки имеют ровно один токен. Как следствие, не может быть параллелизма , но может быть конфликт (т.е. недетерминизм ): математически, $\forall t\in T:|t^{\bullet }|=|{}^{\bullet }t|=1$
2. В размеченном графе (MG) каждое место имеет одну входящую и одну исходящую дугу. Это означает, что не быть конфликта может , но может быть параллелизм: математически $\forall s\in S:|s^{\bullet }|=|{}^{\bullet }s|=1$
3. В сети свободного выбора (FC) каждая дуга от места к переходу является либо единственной дугой от этого места, либо единственной дугой к этому переходу, т.е. может быть как параллелизм, так и конфликт, но не одновременно : математически , $\forall s\in S:(|s^{\bullet }|\leq 1)\vee ({}^{\bullet }(s^{\bullet })=\{s\})$
4. Расширенный свободный выбор (EFC) – сеть Петри, преобразуемая в FC .
5. В асимметричной сети выбора (АС) параллелизм и конфликт (в общем, путаница могут возникать ), но не симметрично: математически $\forall s_{1},s_{2}\in S:(s_{1}{}^{\bullet }\cap s_{2}{}^{\bullet }\neq \emptyset )\to [(s_{1}{}^{\bullet }\subseteq s_{2}{}^{\bullet })\vee (s_{2}{}^{\bullet }\subseteq s_{1}{}^{\bullet })]$

Сети рабочих процессов

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

WF-сети обладают свойством устойчивости , указывая, что процесс с начальной маркировкой из k токенов в исходной позиции может достичь состояния завершения с маркировкой k токенов в своей приемной позиции (определяемой как k -sound WF-net). Кроме того, могут сработать все переходы в процессе (т. е. для каждого перехода существует достижимое состояние, в котором переход разрешен). Общий звук (G-звук) WF-сети определяется как k -звук для каждого k > 0.

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

Хорошо управляемая сеть Петри — это сеть, в которой нет полностью различных элементарных путей между местом и переходом (или переходом и местом), т. е. если между парой узлов существует два пути, то эти пути имеют общий узел. .Ациклическая, хорошо управляемая WF-сеть надежна (G-звук).

Расширенная WF-сеть — это сеть Петри, состоящая из WF-сети с дополнительным переходом t (переход с обратной связью). Место стока подключено как входное место перехода t, а место источника — как его выходное место. Запуск перехода вызывает итерацию процесса (обратите внимание, расширенная WF-сеть не является WF-сетью).

WRI (хорошо управляемая с регулярной итерацией) WF-сеть представляет собой расширенную ациклическую хорошо управляемую WF-сеть. Сеть WRI-WF может быть построена как композиция сетей, т.е. замена перехода внутри сети WRI-WF подсетью, которая является сетью WRI-WF. Результатом также является сеть WRI-WF. WRI-WF-сети - G-звук, поэтому, используя только строительные блоки WRI-WF-сетей, можно получить WF-сети, которые по конструкции являются G-звуковыми.

Матрица структуры проектирования (DSM) может моделировать взаимосвязи процессов и использоваться для планирования процессов. Сети DSM представляют собой реализацию планов на основе DSM в рабочих процессах с помощью сетей Петри и эквивалентны сетям WRI-WF. Процесс построения DSM-сети обеспечивает свойство устойчивости полученной сети.

Другие модели параллелизма

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

Подход к взаимодействию некоторых из этих моделей параллелизма предложен в главе Винскеля и Нильсена.

Области применения

• Булево дифференциальное исчисление
• Моделирование бизнес-процессов
• Вычислительная биология
• Параллельное программирование
• Техника управления
• Анализ данных
• Диагностика (искусственный интеллект)
• Дискретное управление процессом
• Теория игр
• Аппаратное обеспечение
• Сети процессов Кана
• Моделирование процессов
• Инженерия надежности
• Моделирование
• Разработка программного обеспечения
• Системы управления рабочими процессами

См. также

• Конечный автомат
• Язык разметки сетей Петри
• Петрискрипт
• Архитектура процесса
• Системы векторного сложения
• Машинное обучение

Дальнейшее чтение

• Кардосо, Джанетт; Камарго, Элоиза (1999). Нечеткость в сетях Петри . Физика-Верлаг. ISBN  978-3-7908-1158-2 .
• Кьячио, Мануэль; Кьячио, Хуан; Пресскотт, Даррен; Эндрюс, Джон (2018). «Новая парадигма представления неопределенных знаний с помощью «правдоподобных сетей Петри» » . Информационные науки . 453 (июль 2018 г.): 323–345. дои : 10.1016/j.ins.2018.04.029 .
• Гробельна, Ивона (2011). «Формальная проверка спецификации встроенного логического контроллера с компьютерным выводом во временной логике». Пшегленд Электротехнический . 87 (12а): 47–50.
• Дженсен, Курт (1997). Цветные сети Петри . Спрингер Верлаг. ISBN  978-3-540-62867-5 .
• Патарича, Андраш (2004). Формальные методы в информатике . Издательство ТИПОТЕКС. ISBN  978-963-9548-08-4 .
• Петерсон, Джеймс Лайл (1977). «Сети Петри». Обзоры вычислительной техники ACM . 9 (3): 223–252. дои : 10.1145/356698.356702 . hdl : 10338.dmlcz/135597 . S2CID   3605804 .
• Петерсон, Джеймс Лайл (1981). Теория сетей Петри и моделирование систем . Прентис Холл. ISBN  978-0-13-661983-3 .
• Петри, Карл Адам (1962). Связь с автоматами (кандидатская диссертация). Боннский университет.
• Петри, Карл Адам; Райзиг, Вольфганг (2008). «Сеть Петри» . Схоларпедия . 3 (4): 6477. Бибкод : 2008SchpJ...3.6477P . doi : 10.4249/scholarpedia.6477 .
• Райзиг, Вольфганг (1992). Учебник по проектированию сетей Петри . Издательство Спрингер. ISBN  978-3-540-52044-3 .
• Риман, Роберт-Кристоф (1999). Моделирование параллельных систем: структурные и семантические методы в исчислении сетей Петри высокого уровня . Герберт Утц Верлаг. ISBN  978-3-89675-629-9 .
• Стеррле, Харальд (2000). Модели архитектуры программного обеспечения: проектирование и анализ с помощью UML и сетей Петри . Книги по запросу. ISBN  978-3-8311-1330-9 .
• Зайцев, Дмитрий (2013). Кланы сетей Петри: Проверка протоколов и оценка производительности сетей . ЛАП ЛАМБЕРТ Академическое издательство. ISBN  978-3-659-42228-7 .
• Чжоу, Мэнчу ; Дичесаре, Франк (1993). Синтез сетей Петри для дискретного управления событиями производственных систем . Академическое издательство Клювер. ISBN  978-0-7923-9289-7 .
• Чжоу, Мэнчу ; Венкатеш, Курапати (1998). Моделирование, моделирование и управление гибкими производственными системами: подход сетей Петри . Мировое научное издательство. ISBN  978-981-02-3029-6 .
• Сюэ-Го, Сюй (2019). «Изображение нечетких сетей Петри для представления и приобретения знаний при учете противоречивых мнений» . Прикладные науки . 9 (5): 983. дои : 10.3390/app9050983 .