сеть Петри

Модель для описания распределенных систем

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

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

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

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

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

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

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

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

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

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

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

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

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

1. P и T — непересекающиеся конечные множества позиций и переходов соответственно.
2. ${\displaystyle 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 можно интерпретировать как представляющее несинглетонный набор конфигураций. В этом отношении M расширяет концепцию конфигурации для элементарных сетей на сети Петри.

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

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

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

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

Синтаксис

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

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

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

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

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

Сеть Петри ( некоторые называют ее маркированной сетью Петри , см. выше) — это 4-кортеж , где ${\displaystyle (S,T,W,M_{0})}$

• ${\displaystyle (S,T,W)}$представляет собой граф сети Петри;
• ${\displaystyle M_{0}}$— начальная маркировка , маркировка графа сети Петри.

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

В словах

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

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

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

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

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

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

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

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

Другим распространенным вариантом, например, в Desel и Juhás (2001), ^[4] является разрешение определять мощности на местах. Это обсуждается в расширениях ниже.

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

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

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

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

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

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

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

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

• ${\displaystyle 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 было последовательностью срабатывания; разрешение произвольных последовательностей переходов, как правило, приведет к созданию большего набора.

$${\displaystyle 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}}}$$

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

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

Месегер и Монтанари рассматривали разновидность симметричных моноидальных категорий, известных как категории Петри . ^[5]

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

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

Обзор таких задач принятия решений с результатами по разрешимости и сложности для сетей Петри и некоторых подклассов можно найти в работе Эспарца и Нильсена (1995). ^[6]

Достижимость

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

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

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

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

Живость

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

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

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

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

Эти определения соответствуют обзору Мураты ^[12], который дополнительно использует термин -live для обозначения dead . ${\displaystyle L_{0}}$

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

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

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

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

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

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

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

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

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

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

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

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

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

Наряду с дискретными событиями существуют сети Петри для непрерывных и гибридных дискретно-непрерывных процессов ^[14] , которые полезны в дискретной, непрерывной и гибридной теории управления ^[15] и связаны с дискретными, непрерывными и гибридными автоматами .

Расширения

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

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

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

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

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

Ограничения

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

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

1. В машине состояний (SM) каждый переход имеет одну входящую дугу и одну выходящую дугу, и все маркировки имеют ровно один токен. Как следствие, не может быть параллелизма , но может быть конфликт (т.е. недетерминизм ): математически, ${\displaystyle \forall t\in T:|t^{\bullet }|=|{}^{\bullet }t|=1}$
2. В маркированном графе (MG) каждое место имеет одну входящую дугу и одну выходящую дугу. Это означает, что не может быть конфликта , но может быть параллелизм: математически, ${\displaystyle \forall s\in S:|s^{\bullet }|=|{}^{\bullet }s|=1}$
3. В сети свободного выбора (FC) каждая дуга от места до перехода является либо единственной дугой от этого места, либо единственной дугой к этому переходу, т.е. может быть как параллелизм, так и конфликт, но не одновременно : математически, ${\displaystyle \forall s\in S:(|s^{\bullet }|\leq 1)\vee ({}^{\bullet }(s^{\bullet })=\{s\})}$
4. Расширенный свободный выбор (РСВ) – сеть Петри, которая может быть преобразована в РС .
5. В асимметричной сети выбора (АС) могут возникать параллелизм и конфликт (в общем, путаница ), но не симметрично: математически, ${\displaystyle \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-сети) являются подклассом сетей Петри, предназначенных для моделирования рабочего процесса действий процесса. ^[24] Переходы WF-сети назначаются задачам или действиям, а места назначаются предварительным/постусловиям. WF-сети имеют дополнительные структурные и эксплуатационные требования, в основном добавление одного входного (исходного) места без предыдущих переходов и выходного места (приемника) без последующих переходов. Соответственно, можно определить начальные и конечные отметки, которые представляют статус процесса.

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

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

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

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

WRI (Well-handled with Regular Iteration) WF-net, является расширенной ациклической хорошо управляемой WF-сетью. WRI-WF-net может быть построена как композиция сетей, т. е. замена перехода внутри WRI-WF-net на подсеть, которая является WRI-WF-net. Результатом также является WRI-WF-net. WRI-WF-сети являются G-звуковыми, ^[26] поэтому, используя только строительные блоки WRI-WF-net, можно получить WF-сети, которые являются G-звуковыми по конструкции.

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

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

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

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

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

• Булево дифференциальное исчисление ^[29]
• Моделирование бизнес-процессов ^{[30] [31]}
• Вычислительная биология ^{[32] [33]}
• Параллельное программирование ^[34]
• Техника управления ^{[15] [35] [36]}
• Анализ данных ^[37]
• Диагностика (искусственный интеллект) ^[38]
• Дискретное управление процессами ^{[39] [40] [41]}
• Теория игр ^[42]
• Аппаратная часть ^{[43] [44] [45]}
• Сети процессов Кана ^[46]
• Моделирование процесса ^{[47] [48] [49]}
• Надежность техники ^{[50] [51]}
• Моделирование ^[30]
• Разработка программного обеспечения ^[14]
• Системы управления рабочим процессом ^{[52] [48] [49]}

Смотрите также

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

Ссылки

1. Петри, Карл Адам; Райзиг, Вольфганг (2008). «Сеть Петри». Схоларпедия . 3 (4): 6477. Бибкод : 2008SchpJ...3.6477P. doi : 10.4249/scholarpedia.6477 .
2. Розенбург, Г.; Энгельфрит, Дж. (1998). «Элементарные сетевые системы». В Рейсиге, В.; Розенберг, Г. (ред.). Лекции по сетям Петри I: Базовые модели – Достижения в сетях Петри . Заметки лекций по информатике. Том 1491. Springer. стр. 12–121. doi :10.1007/3-540-65306-6_14. ISBN 3-540-65306-6.
3. Рейзиг, Вольфганг (1991). «Сети Петри и алгебраические спецификации». Теоретическая информатика . 80 (1): 1–34. doi :10.1016/0304-3975(91)90203-e.
4. Десел, Йорг; Юхас, Габриэль (2001). «Что такое сеть Петри? Неформальные ответы для информированного читателя». В Ehrig, Hartmut ; et al. (ред.). Объединение сетей Петри . LNCS. Том 2128. Springer. стр. 1–25. doi :10.1007/3-540-45541-8_1. ISBN 9783540430674.
5. Месегер, Хосе; Монтанари, Уго (октябрь 1990 г.). «Сети Петри — это моноиды». Информация и вычисления . 88 (2): 105–155. doi :10.1016/0890-5401(90)90013-8.
6. Эспарса, Хавьер; Нильсен, Могенс (1995) [1994]. «Вопросы разрешимости для сетей Петри – обзор». Бюллетень EATCS (пересмотренное издание) . Получено 14 мая 2014 г.
7. Липтон, Р. (1976). «Проблема достижимости требует экспоненциального пространства». Технический отчет 62. Йельский университет: 305–329.
8. Кюнгас, П. (26–29 июля 2005 г.). Petri Net Reachability Checking Is Polynomial with Optimal Abstraction Hierarchies. Труды 6-го Международного симпозиума по абстракции, переформулированию и аппроксимации — SARA 2005. Заметки лекций по информатике. Том 3607. Замок Эйрт, Шотландия, Великобритания: Springer. С. 149–164. doi :10.1007/11527862_11. ISBN 3-540-31882-8. Архивировано из оригинала 2012-02-09 . Получено 2008-07-10 .
9. Червинский, Войцех; Ласота, Славомир; Лазич, Ранко; Леру, Жером; Мазовецкий, Филип (2018). «Проблема достижимости сетей Петри не является элементарной (расширенное резюме)». arXiv : 1809.07115 [cs.FL].
10. Леру, Жером (2021). «Проблема достижимости сетей Петри не является примитивно рекурсивной». arXiv : 2104.12695 [cs.LO].
11. Червинский, Войцех; Орликовский, Лукаш (2021). «Достижимость в системах сложения векторов является полной по Аккерману». arXiv : 2104.13866 [cs.FL].
12. Мурата, Тадао (апрель 1989 г.). «Сети Петри: свойства, анализ и приложения» (PDF) . Труды IEEE . 77 (4): 541–558. doi :10.1109/5.24143 . Получено 26.05.2024 .
13. "Petri Nets". www.techfak.uni-bielefeld.de . Архивировано из оригинала 2011-09-27 . Получено 2011-04-13 .
14. Кучера, Эрик; Хаффнер, Ото; Драгош, Питер; Цыганек, Ян; Лесковский, Роман; Штефанович, Юрай (январь 2020 г.). «Новый программный инструмент для моделирования и управления дискретно-событийными и гибридными системами с использованием интерпретируемых по времени сетей Петри». Прикладные науки . 10 (15): 5027. дои : 10.3390/app10155027 .
15. Дэвид, Рене; Алла, Хассан (2005). Дискретные, непрерывные и гибридные сети Петри. Springer. ISBN 978-3-540-22480-8.
16. Йенсен, Курт (1997). "Краткое введение в цветные сети Петри" (PDF) . Краткое введение в цветные сети Петри . Lecture Notes in Computer Science. Vol. 1217. pp. 203–208. doi :10.1007/BFb0035389. ISBN 978-3-540-62790-6.
17. Араки, Т.; Касами, Т. (1977). «Некоторые проблемы принятия решений, связанные с проблемой достижимости сетей Петри». Теоретическая информатика . 3 (1): 85–104. doi :10.1016/0304-3975(76)90067-0.
18. Дюфур, К.; Финкель, А.; Шнобелен, Ф. (1998). «Сети сброса между разрешимостью и неразрешимостью». Труды 25-го Международного коллоквиума по автоматам, языкам и программированию . Конспект лекций по информатике. Том 1443. С. 103–115. doi :10.1007/11527862_11. ISBN 3-540-68681-9.
19. Зайцев, ДА (2013). «К минимальной универсальной сети Петри». Труды IEEE по системам, человеку и кибернетике: системы . 44 : 47–58. doi :10.1109/TSMC.2012.2237549. S2CID  6561556.
20. "Very Brief Introduction to CP-nets". Department of Computer Science, University of Aarhus, Denmark. Архивировано из оригинала 2010-10-28 . Получено 2007-08-22 .
21. "LLPN - Линейные логические сети Петри". Архивировано из оригинала 2005-11-03 . Получено 2006-01-06 .
22. Dawis, EP; Dawis, JF; Koo, Wei-Pin (2001). Архитектура компьютерных систем с использованием дуалистических сетей Петри . Международная конференция IEEE по системам, человеку и кибернетике 2001 г. Том 3. С. 1554–8. doi :10.1109/ICSMC.2001.973505. ISBN 0-7803-7087-2.
23. Dawis, EP (2001). Архитектура стека протоколов SS7 на платформе широкополосного коммутатора с использованием дуалистических сетей Петри . 2001 IEEE Pacific Rim Conference on Communications, Computers and Signal Processing. Том 1. С. 323–6. doi :10.1109/PACRIM.2001.953588. ISBN 0-7803-7080-5.
24. van der Aalst, WMP (1998). "Применение сетей Петри к управлению рабочим процессом" (PDF) . Journal of Circuits, Systems and Computers . 8 (1): 21–66. CiteSeerX 10.1.1.30.3125 . doi :10.1142/s0218126698000043. S2CID  248401501. Архивировано из оригинала (PDF) 2016-11-19 . Получено 2015-04-02 . 
25. van Hee, K.; Sidorova, N.; Voorhoeve, M. (2003). "Надежность и разделимость сетей рабочих процессов в подходе пошагового уточнения" (PDF) . В van der Aalst, WMP; Best, E. (ред.). Application and Theory of Petri Nets 2003 . Lecture Notes in Computer Science. Vol. 2678. Springer. pp. 337–356. doi :10.1007/3-540-44919-1_22. ISBN 3-540-44919-1.
26. Ping, L.; Hao, H.; Jian, L. (2004). Moldt, Daniel (ред.). On 1-soundness и soundness of workflow nets . Proc of the 3rd Workshop on Modelling of Objects, Components, and Agents. Vol. 571. Aarhus, Denmark: DAIMI PB. pp. 21–36. ISSN  0105-8517. OCLC  872760679.
27. Мазуркевич, Антони (1995). «Введение в теорию следов». В Diekert, V.; Rozenberg, G. (ред.). Книга следов . World Scientific. стр. 3–67.
28. Winskel, G.; Nielsen, M. "Models for Concurrency" (PDF) . Handbook of Logic and the Foundations of Computer Science . Vol. 4. OUP. pp. 1–148. Архивировано из оригинала (PDF) 2020-05-04.
29. Шеуринг, Райнер; Велан, Герберт «Ганс» (1 декабря 1991 г.) [июль 1991 г.]. Бреттауэр, Георг (ред.). «Der Boolesche Differentialkalkül – eine Methode zur Analysis und Synthese von Petri-Netzen» [Булевое дифференциальное исчисление – метод анализа и синтеза сетей Петри]. At – Automatisierungstechnik – Methoden und Anwendungen der Steuerungs-, Regelungs- und Informationstechnik (на немецком языке). 39 (7). Штутгарт, Германия: Р. Ольденбург Верлаг  [де] : 226–233. дои : 10.1524/auto.1991.39.112.226. ISSN  0178-2312. S2CID  56766796. Архивировано из оригинала 2017-10-16 . Получено 2017-10-16 .(8 страниц)
30. ван дер Аалст, WMP; Шталь, К. (27 мая 2011 г.). Моделирование бизнес-процессов — подход, ориентированный на сети Петри. МТИ Пресс. стр. 1–400. ISBN 9780262015387.
31. ван дер Аалст, WMP (2018). «Управление бизнес-процессами». Энциклопедия систем баз данных . Спрингер. стр. 370–374. дои : 10.1007/978-1-4614-8265-9_1179. ISBN 978-1-4614-8266-6.
32. Фаврин, Бин (2014-09-02). "esyN: Создание сетей, совместное использование и публикация". PLOS ONE . 9 (9): e106035. Bibcode : 2014PLoSO...9j6035B. doi : 10.1371/journal.pone.0106035 . PMC 4152123. PMID  25181461 . 
33. Кох, Ина ; Райзиг, Вольфганг; Шрайбер, Фальк (2011). Моделирование в системной биологии - подход сетей Петри. Вычислительная биология. Том. 16. Спрингер. дои : 10.1007/978-1-84996-474-6. ISBN 978-1-84996-473-9.
34. Кристенсен, Л. М.; Вестергаард, М. (2010). «Автоматическая генерация кода на основе структур из цветных сетей Петри: доказательство концепции». Формальные методы для промышленных критических систем . Формальные методы для промышленных критических систем — 15-й международный семинар, FMICS 2010. Конспект лекций по информатике. Том 6371. С. 215–230. doi :10.1007/978-3-642-15898-8_14. ISBN 978-3-642-15897-1.
35. Гао, С.; Ху, Синьян (2020). «Надежное управление нейронной сетью Петри для новой модели процесса заполнения пастой». IEEE Access . 8 : 18420–18425. Bibcode : 2020IEEEA...818420G. doi : 10.1109/ACCESS.2020.2968510 . S2CID  210994447.
36. Кучера, Эрик; Хаффнер, Ото; Драгош, Петер; Лесковски, Роман; Циганек, Ян (январь 2020 г.). «PetriNet Editor + PetriNet Engine: новый программный инструмент для моделирования и управления дискретными системами событий с использованием сетей Петри и генерации кода». Прикладные науки . 10 (21): 7662. doi : 10.3390/app10217662 .
37. ван дер Аалст, WMP (2016). Process Mining — наука о данных в действии, второе издание. Спрингер. дои : 10.1007/978-3-662-49851-4. ISBN 978-3-662-49850-7. S2CID  12806779.
38. Кармона, Дж.; ван Донген, Б. Ф.; Шолти, А.; Вайдлих, М. (2018). Проверка соответствия — связанные процессы и модели. Springer. doi : 10.1007/978-3-319-99414-7. ISBN 978-3-319-99413-0. S2CID  53250018.
39. Фернандес, Дж. Л.; Санс, Р.; Пас, Э.; Алонсо, К. (19–23 мая 2008 г.). «Использование иерархических бинарных сетей Петри для создания надежных приложений для мобильных роботов: RoboGraph». Международная конференция IEEE по робототехнике и автоматизации, 2008 г. Пасадена, Калифорния, США. стр. 1372–7. doi :10.1109/ROBOT.2008.4543394. ISBN 978-1-4244-1646-2.
40. Мендес, Дж. Марко; Лейтао, Пауло; Коломбо, Армандо В.; Рестиво, Франциско (2012). «Высокоуровневые сети Петри для описания и управления процессами в сервисно-ориентированных производственных системах». Международный журнал исследований производства . 50 (6). Тейлор и Фрэнсис: 1650–1665. doi :10.1080/00207543.2011.575892. S2CID  39688855.
41. Фэланд, Д.; Гирдс, К. (2013). «Анализ и завершение проектов промежуточного программного обеспечения для интеграции предприятий с использованием цветных сетей Петри». Active Flow and Combustion Control 2018. Advanced Information Systems Engineering - 25-я международная конференция, CAiSE 2013. Lecture Notes in Computer Science. Vol. 7908. pp. 400–416. doi : 10.1007/978-3-642-38709-8_26 . ISBN 978-3-319-98176-5.
42. Клемпнер, Хулио (2006). «Моделирование игр на кратчайшие пути с помощью сетей Петри: теория на основе Ляпунова». Международный журнал прикладной математики и компьютерных наук . 16 (3): 387–397. ISSN  1641-876X.
43. Яковлев, Алекс; Гомес, Луис; Лаваньо, Лучано, ред. (2000). Проектирование аппаратного обеспечения и сети Петри. дои : 10.1007/978-1-4757-3143-9. ISBN 978-1-4419-4969-1.
44. Кортаделла, Дж .; Кишиневский, М.; Кондратьев, А.; Лаваньо, Л.; Яковлев, А. (2002). Логический синтез для асинхронных контроллеров и интерфейсов. Springer Series in Advanced Microelectronics. Том 8. doi :10.1007/978-3-642-55989-1. ISBN 978-3-642-62776-7. ISSN  1437-0387.
45. Кортаделла, Хорди ; Яковлев, Алекс; Розенберг, Гжегож, ред. (2002). Параллелизм и проектирование оборудования. Конспект лекций по информатике. Том 2549. doi :10.1007/3-540-36190-1. ISBN 978-3-540-00199-7. ISSN  0302-9743. S2CID  42026227.
46. Бернардески, К.; Де Франческо, Н.; Ваглини, Г. (1995). «Семантика сетей Петри для сетей потоков данных». Акта Информатика . 32 (4): 347–374. дои : 10.1007/BF01178383. S2CID  7285573.
47. Ван дер Аалст, Виль MP; Шталь, Кристиан; Вестергаард, Майкл (2013). «Стратегии моделирования сложных процессов с использованием цветных сетей Петри». Труды по сетям Петри и другим моделям параллелизма VII . Конспект лекций по информатике. Том 7. С. 6–55. doi :10.1007/978-3-642-38143-0_2. ISBN 978-3-642-38142-3. {{cite book}}: |journal=проигнорировано ( помощь )
48. ван дер Аалст, WMP (2018). «Схемы рабочих процессов». Энциклопедия систем баз данных . Спрингер. стр. 4717–4718. дои : 10.1007/978-1-4614-8265-9_826. ISBN 978-1-4614-8266-6.
49. ван дер Аалст, WMP (2018). «Анализ модели рабочего процесса». Энциклопедия систем баз данных . Спрингер. стр. 4716–4717. дои : 10.1007/978-1-4614-8265-9_1476. ISBN 978-1-4614-8266-6.
50. О'Коннор, Патрик DT (2012). Практическая надежность техники . Андре Клейнер (5-е изд.). Wiley. ISBN 978-1-119-96126-0. OCLC  862121371.
51. Хуан, Мэрион; Мейлланд, Дэвид; Фифис, Николас; Грегорис, Гай (декабрь 2021 г.). «Моделирование панелей активной антенны и модификации архитектуры». Техники инженера . Sécurité des Systèmes Industriels. doi : 10.51257/a-v1-se1221. S2CID  245057775.
52. тер Хофстеде, Артур Х.М.; ван дер Аалст, член парламента Вила; Адамс, Майкл; Рассел, Ник (2010). Хофстед, Артур Х.М; Алст, Уил М.П.; Адамс, Майкл; Рассел, Ник (ред.). Современная автоматизация бизнес-процессов — YAWL и его среда поддержки. дои : 10.1007/978-3-642-03121-2. ISBN 978-3-642-03122-9.

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

• Кардосо, Джанетт; Камарго, Элоиза (1999). Нечеткость в сетях Петри . Физика-Верлаг. ISBN 978-3-7908-1158-2.
• Чиачио, Мануэль; Чиачио, Хуан; Пресскотт, Даррен; Эндрюс, Джон (2018). «Новая парадигма представления неопределенных знаний с помощью «правдоподобных сетей Петри»». Information Sciences . 453 (июль 2018 г.): 323–345. doi : 10.1016/j.ins.2018.04.029 .
• Grobelna, Iwona (2011). «Формальная проверка спецификации встроенного логического контроллера с помощью компьютерного вывода во временной логике». Przegląd Elektrotechniczny . 87 (12a): 47–50.
• Дженсен, Курт (1997). Цветные сети Петри. Спрингер Верлаг. ISBN 978-3-540-62867-5.
• Патарича, Андраш (2004). Formális modszerek az informatikában (Формальные методы в информатике) . ТИПОТЕКС Киадо. ISBN 978-963-9548-08-4.
• Петерсон, Джеймс Лайл (1977). «Сети Петри». ACM Computing Surveys . 9 (3): 223–252. doi :10.1145/356698.356702. hdl : 10338.dmlcz/135597 . S2CID  3605804.
• Петерсон, Джеймс Лайл (1981). Теория сетей Петри и моделирование систем . Prentice Hall. ISBN 978-0-13-661983-3.
• Петри, Карл Адам (1962). Kommunikation mit Automaten (докторская диссертация). Боннский университет.
• Петри, Карл Адам; Райзиг, Вольфганг (2008). «Сеть Петри». Схоларпедия . 3 (4): 6477. Бибкод : 2008SchpJ...3.6477P. doi : 10.4249/scholarpedia.6477 .
• Райзиг, Вольфганг (1992). Учебник по проектированию сетей Петри . Спрингер-Верлаг. ISBN 978-3-540-52044-3.
• Риман, Роберт-Кристоф (1999). Моделирование параллельных систем: структурные и семантические методы в исчислении сетей Петри высокого уровня . Herbert Utz Verlag. ISBN 978-3-89675-629-9.
• Störrle, Harald (2000). Модели архитектуры программного обеспечения – Проектирование и анализ с использованием UML и сетей Петри . Книги по запросу. ISBN 978-3-8311-1330-9.
• Зайцев, Дмитрий (2013). Кланы сетей Петри: Проверка протоколов и оценка производительности сетей. LAP LAMBERT Academic Publishing. ISBN 978-3-659-42228-7.
• Чжоу, Мэнчу ; Дичезаре, Франк (1993). Синтез сетей Петри для дискретного управления событиями производственных систем . Kluwer Academic Publishers. ISBN 978-0-7923-9289-7.
• Чжоу, Мэнчу ; Венкатеш, Курапати (1998). Моделирование, имитация и управление гибкими производственными системами: подход с использованием сетей Петри . World Scientific Publishing. ISBN 978-981-02-3029-6.
• Сюэ-Го, Сюй (2019). «Нечеткие сети Петри с изображениями для представления и получения знаний при рассмотрении противоречивых мнений». Прикладные науки . 9 (5): 983. doi : 10.3390/app9050983 .