Сеть Петри , также известная как место / переход (PT) сети , является одним из нескольких математических языков моделирования для описания распределенных систем . Это класс дискретных событийных динамических систем . Сеть Петри - это ориентированный двудольный граф, который имеет два типа элементов, места и переходы, изображенные как белые кружки и прямоугольники соответственно. Место может содержать любое количество жетонов, обозначенных черными кружками. Переход разрешен, если все точки, подключенные к нему как входы, содержат хотя бы один токен. Некоторые источники [1] утверждают, что сети Петри были изобретены в августе 1939 года Карлом Адамом Петри.- в 13 лет - для описания химических процессов.
Как и отраслевые стандарты , такие как UML диаграммы деятельности , бизнес - процессы модель и нотация и событийно-управляемые цепочки процессов , сети Петри предлагает графическое обозначение для процессов ступенчаты , которые включают выбор, итерацию и одновременное выполнение . В отличие от этих стандартов, сети Петри имеют точное математическое определение семантики их выполнения с хорошо развитой математической теорией для анализа процессов [ необходима цитата ] .
Основы сети Петри
Сеть Петри состоит из мест , переходов и дуг . Дуги проходят от места к переходу или наоборот, но никогда между местами или переходами. Места, из которых проходит дуга к переходу, называются входными местами перехода; места, куда идут дуги от перехода, называются местами вывода перехода.
Графически места в сети Петри могут содержать дискретное количество меток, называемых токенами . Любое распределение жетонов по местам будет представлять конфигурацию сети, называемую маркировкой . В абстрактном смысле, относящемся к диаграмме сети Петри, переход сети Петри может сработать, если он разрешен , т. Е. Имеется достаточно токенов во всех его входных местах; когда срабатывает переход, он потребляет необходимые входные токены и создает токены в своих выходных местах. Обжиг является атомарным, то есть одиночным непрерывным шагом.
Если не определена политика выполнения (например, строгий порядок переходов, описывающий приоритет), выполнение сетей Петри недетерминировано : когда несколько переходов разрешены одновременно, они будут срабатывать в любом порядке.
Поскольку активация является недетерминированной, и несколько токенов могут присутствовать в любом месте сети (даже в одном месте), сети Петри хорошо подходят для моделирования параллельного поведения распределенных систем.
Формальное определение и основная терминология
Сети Петри - это системы с переходом между состояниями, которые расширяют класс сетей, называемых элементарными сетями. [2]
Определение 1. сетка представляет собой кортеж где:
- а также - непересекающиеся конечные множества мест и переходов соответственно.
- представляет собой набор (направленных) дуг (или потоковых соотношений).
Определение 2. Учитывая чистый N = ( P , T , F ), A конфигурация представляет собой набор С , так что С ⊆ P .
Определение 3. элементарная сетка представляет собой сеть в виде EN = ( N , C ) , где:
- N = ( P , T , F ) - сеть.
- C такова, что C ⊆ P - конфигурация .
Определение 4. сеть Петри представляет собой сеть в виде ПНА = ( N , M , W ), которая проходит элементарную сеть таким образом , чтобы:
- N = ( P , T , F ) - сеть.
- M : P → Z - местное мультимножество , где Z - счетное множество . M расширяет концепцию конфигурации и обычно описывается со ссылкой на диаграммы сети Петри как маркировку .
- W : F → Z - это мультимножество дуг , поэтому количество (или вес) каждой дуги является мерой кратности дуги .
Если сеть Петри эквивалентна элементарной сети, то Z может быть счетным множеством {0,1}, и те элементы в P, которые отображаются в 1 при M, образуют конфигурацию. Точно так же, если сеть Петри не является элементарной сетью, то мультимножество M можно интерпретировать как представляющее не одноэлементный набор конфигураций. В этом отношении M расширяет понятие конфигурации элементарных сетей на сети Петри.
На схеме сети Петри (см. Верхний рисунок справа) места условно изображаются кружками, переходы - длинными узкими прямоугольниками, а дуги - односторонними стрелками, которые показывают соединения мест с переходами или переходы к местам. Если бы диаграмма представляла собой элементарную сеть, то эти места в конфигурации были бы условно изображены в виде кругов, где каждый круг включает в себя одну точку, называемую токеном . На данной диаграмме сети Петри (см. Справа) кружки мест могут охватывать более одного токена, чтобы показать, сколько раз место появляется в конфигурации. Конфигурация токенов, распределенных по всей диаграмме сети Петри, называется маркировкой .
На верхнем рисунке (см. Справа) позиция p 1 является входной точкой перехода t ; тогда как место p 2 является местом выхода к тому же переходу. Пусть PN 0 (верхний рисунок) будет сетью Петри с настроенной маркировкой M 0 , а PN 1 (нижний рисунок) будет сетью Петри с настроенной маркировкой M 1 . Конфигурация PN 0 обеспечивает переход t через свойство, что все входные позиции имеют достаточное количество маркеров (показанных на рисунках точками), «равное или большее», чем кратности на их соответствующих дугах к t . Один и только один раз переход будет активирован. В этом примере срабатывание перехода t генерирует карту, которая имеет маркировку, сконфигурированную M 1 в изображении M 0, и приводит к сети Петри PN 1 , показанной на нижнем рисунке. На диаграмме правило активации для перехода может быть охарактеризовано вычитанием количества токенов из его входных позиций, равного кратности соответствующих входных дуг, и накопления нового количества токенов в выходных местах, равного кратности соответствующих входных дуг. выходные дуги.
Замечание 1. Точное значение слова «равно или больше» будет зависеть от точных алгебраических свойств сложения, применяемого к Z в правиле срабатывания, где тонкие изменения алгебраических свойств могут привести к другим классам сетей Петри; например, алгебраические сети Петри. [3]
Следующее формальное определение в общих чертах основано на ( Peterson 1981 ). Существует множество альтернативных определений.
Синтаксис
Петри графа ( так называемый Петри некоторыми, но смотри ниже) представляет собой 3- кортеж , где
- S представляет собой конечное множество из мест
- T - конечное множество переходов
- S и T не пересекаются , т.е. ни один объект не может быть одновременно местом и переходом.
- является мультимножеством из дуг , т.е. присваивает каждый дугового неотрицательной целого числа дуги кратность (или вес); обратите внимание, что никакая дуга не может соединять два места или два перехода.
Отношение потока - это набор дуг:. Во многих учебниках, дуги могут иметь только множественность 1. Эти тексты часто определяют с помощью сетей Петри F вместо W . При использовании этого соглашения граф сети Петри представляет собой двудольный мультиграф. с узлом перегородки S и Т .
Запрограммированное переходный т есть множество его входных позиции :; его постсет - это набор его выходных мест :. Аналогичны определения пред- и постсетей мест.
Маркировка в сети Петри (графа) является мультимножеством своих мест, т.е. отображение. Мы говорим, что маркировка присваивает каждому месту количество жетонов .
Сеть Петри ( так называемые отмечена Петри некоторых см выше) представляет собой 4-кортеж, где
- граф сети Петри;
- - начальная разметка , разметка графа сети Петри.
Семантика исполнения
В словах:
- срабатывание перехода t в маркировке M потребляеттокены из каждого из входных мест s , и производиттокенов в каждом из своих выходных мест s
- переход разрешен (он может сработать ) в M, если во входных местах достаточно токенов для возможного потребления, то есть тогда и только тогда, когда.
Обычно нас интересует, что может произойти, если переходы могут непрерывно запускаться в произвольном порядке.
Мы говорим, что маркировка M ' достижима из маркировки M за один шаг, если; мы говорим, что она достижима из M, если, где является рефлексивным транзитивным замыканием в; то есть, если до него можно добраться за 0 или более шагов.
Для (отмеченной) сети Петри , нас интересуют стрельбы, которые можно проводить, начиная с начальной разметки. . Его набором меток достижимости является набор
Достижимости граф из N является переход отношения ограничен доступной маркировкой . Это пространство состояний сети.
Последовательность срабатывания сети Петри с графом G и начальной разметкой это последовательность переходов такой, что . Набор последовательностей срабатывания обозначается как.
Варианты определения
Как уже отмечалось, обычным вариантом является запрет на множественность дуг и замена мешка дуг W простым набором, называемым отношением потока ,. Это не ограничивает выразительную силу, поскольку оба могут представлять друг друга.
Другой распространенный вариант, например, в Desel and Juhás (2001), [4], - это возможность определять пропускную способность на местах. Это обсуждается ниже в разделе « Расширения» .
Формулировка в терминах векторов и матриц
Маркировка сети Петри можно рассматривать как векторы неотрицательных целых чисел длины.
Его переходное отношение можно описать как пару от матрицы :
- , определяется
- , определяется
Тогда их отличие
может использоваться для описания достижимой маркировки в терминах умножения матриц следующим образом. Для любой последовательности переходов w запишемдля вектора, который отображает каждый переход на его количество вхождений в w . Тогда у нас есть
- .
Обратите внимание, что должно требоваться, чтобы w была последовательностью срабатывания; разрешение произвольных последовательностей переходов обычно дает больший набор.
Математические свойства сетей Петри
Одна вещь, которая делает сети Петри интересными, заключается в том, что они обеспечивают баланс между мощностью моделирования и анализируемостью: многие вещи, которые хотелось бы знать о параллельных системах, могут быть автоматически определены для сетей Петри, хотя определение некоторых из этих вещей в целом очень дорого. дело. Было изучено несколько подклассов сетей Петри, которые все еще могут моделировать интересные классы параллельных систем, хотя эти проблемы становятся проще.
Обзор таких проблем принятия решений с результатами о разрешимости и сложности для сетей Петри и некоторых подклассов можно найти в Esparza and Nielsen (1995). [5]
Достижимость
Проблема достижимости сетей Петри состоит в том, чтобы решить, учитывая сеть Петри N и маркировку M , будет ли.
Очевидно, что это вопрос обхода графа достижимости, определенного выше, до тех пор, пока мы не достигнем запрошенной отметки или не узнаем, что ее больше нельзя найти. Это сложнее, чем может показаться на первый взгляд: график достижимости обычно бесконечен, и нелегко определить, когда можно безопасно остановиться.
Фактически, эта проблема была показана как EXPSPACE- трудная [6] за годы до того, как была показана вообще разрешимость (Mayr, 1981). Продолжают публиковаться статьи о том, как это сделать эффективно. [7] В 2018 году Czerwiński et al. улучшил нижнюю границу и показал, что проблема НЕ ЭЛЕМЕНТАРНАЯ . [8] В 2021 году эта проблема была показана как непримитивно рекурсивная, независимо Жеромом Леру [9] , Войцехом Червиньским и Лукашем Орликовским. [10] Таким образом, эти результаты закрывают давний разрыв в сложности.
Хотя достижимость кажется хорошим инструментом для поиска ошибочных состояний, для практических задач построенный граф обычно имеет слишком много состояний для вычисления. Чтобы облегчить эту проблему, линейная временная логика обычно используется в сочетании с методом таблиц, чтобы доказать, что такие состояния не могут быть достигнуты. Линейная темпоральная логика использует технику полурешения, чтобы определить, действительно ли состояние может быть достигнуто, путем нахождения набора необходимых условий для достижения состояния, а затем доказательства того, что эти условия не могут быть выполнены.
Живучесть
Сети Петри можно охарактеризовать как имеющие разную степень живучести. . Сеть Петри называется -live тогда и только тогда, когда все его переходы-live, где есть переход
- мертвый , если он никогда не может стрелять, т.е. он не находится в какой-либо последовательности стрельбы в
- -live ( потенциально может стрелять ), если и только если он может стрелять, т.е. он находится в некоторой последовательности стрельбы в
- -live, если он может срабатывать сколь угодно часто, т.е. если для каждого положительного целого числа k он встречается не менее k раз в некоторой последовательности срабатывания в
- -живой, если он может срабатывать бесконечно часто, т.е. если существует некоторая фиксированная (обязательно бесконечная) последовательность срабатывания, в которой для каждого положительного целого числа k переходвстречается не менее k раз,
- -live ( жить ), если он всегда может срабатывать, т.е.-жить в каждой достижимой маркировке в
Обратите внимание, что требования становятся все более жесткими: -жизнь подразумевает -жизнь, для .
Эти определения соответствуют обзору Мураты [11], в котором дополнительно используется-Жить как термин для мертвых .
Ограниченность
Место в сети Петри называется k-ограниченным, если оно содержит не более k маркеров во всех доступных маркировках, включая начальную маркировку; он считается безопасным, если он 1-ограничен; он ограничен, если он k-ограничен для некоторого k .
( Помеченная ) сеть Петри называется k -ограниченной, безопасной или ограниченной, если все ее места есть. Сеть (граф) Петри называется (структурно) ограниченной, если она ограничена для всевозможных начальных разметок.
Отметим, что сеть Петри ограничена тогда и только тогда, когда ее граф достижимости конечен.
Ограниченность разрешима, глядя на покрытие , путем построения дерева Карпа – Миллера.
Может быть полезно явно наложить ограничения на места в данной сети. Это можно использовать для моделирования ограниченных системных ресурсов.
Некоторые определения сетей Петри явно допускают это как синтаксическую особенность. [12] Формально сети Петри с вместимостью мест можно определить как кортежи., где сеть Петри, присвоение емкостей (некоторым или всем) местам, а отношение перехода - обычное, ограниченное маркировкой, в которой каждое место с емкостью имеет не более этого количества жетонов.
Например, если в сети N обоим местам назначена емкость 2, мы получим сеть Петри с емкостью мест, скажем, N2 ; его график достижимости отображается справа.
В качестве альтернативы, места можно ограничить, расширив сетку. Точнее , место можно сделать k -ограниченным, добавив «встречное место» с потоком, противоположным потоку места, и добавив жетоны, чтобы получить сумму в обоих местах k .
Дискретные, непрерывные и гибридные сети Петри
Так же как и для дискретных событий, существует сети Петри для непрерывных и гибридных дискретно-непрерывных процессов [13] , которые являются полезными в дискретном, непрерывной и гибридной теории управления , [14] и связанный с дискретным, непрерывным и гибридными автоматами .
Расширения
У сетей Петри есть много расширений. Некоторые из них полностью обратно совместимы (например, цветные сети Петри ) с исходной сетью Петри, некоторые добавляют свойства, которые не могут быть смоделированы в исходном формализме сети Петри (например, синхронизированные сети Петри). Хотя обратно-совместимые модели не расширяют вычислительную мощность сетей Петри, они могут иметь более сжатые представления и могут быть более удобными для моделирования. [15] Расширения, которые не могут быть преобразованы в сети Петри, иногда бывают очень мощными, но обычно не имеют полного набора математических инструментов, доступных для анализа обычных сетей Петри.
Термин « высокоуровневая сеть Петри» используется для обозначения многих формализмов сетей Петри, которые расширяют базовый формализм P / T-сети; это включает цветные сети Петри, иерархические сети Петри, такие как Сети в сетях , и все другие расширения, описанные в этом разделе. Этот термин также используется специально для типа цветных сетей, поддерживаемых CPN Tools .
Краткий список возможных расширений:
- Дополнительные типы дуг; два распространенных типа:
- дуга сброса не навязывает предпосылку обжига, и пустеет место при переходе пожаров; это делает достижимость неразрешимой [16], в то время как некоторые другие свойства, такие как завершение, остаются разрешимыми; [17]
- ингибитор дуга накладывает предпосылку , что переход может сработать только тогда , когда место пусто; это позволяет выражать произвольные вычисления числа токенов, что делает формализм Тьюринга полным и подразумевает существование универсальной сети. [18]
- В стандартной сети Петри токены неотличимы. В цветной сети Петри каждый жетон имеет значение. [19] В популярных инструментах для раскрашенных сетей Петри, таких как CPN Tools , значения токенов типизированы и могут быть протестированы (с использованием защитных выражений) и обработаны с помощью функционального языка программирования . Дочерним элементом цветных сетей Петри являются хорошо сформированные сети Петри , в которых выражения дуги и защиты ограничены, чтобы упростить анализ сети.
- Другое популярное расширение сетей Петри - иерархия; это в форме различных представлений, поддерживающих уровни уточнения и абстракции, было изучено Фелингом. Другая форма иерархии встречается в так называемых объектных сетях Петри или объектных системах, где сеть Петри может содержать сети Петри в качестве своих токенов, порождающих иерархию вложенных сетей Петри, которые взаимодействуют посредством синхронизации переходов на разных уровнях. См. [20] для неформального введения в объектные сети Петри.
- Система сложения векторов с состояниями (VASS) - формализм, эквивалентный сетям Петри. Однако на поверхностном уровне его можно рассматривать как обобщение сетей Петри. Рассмотрим конечный автомат, в котором каждый переход помечен переходом из сети Петри. Затем сеть Петри синхронизируется с конечным автоматом, т. Е. Переход в автомате выполняется одновременно с соответствующим переходом в сети Петри. Сделать переход в автомате можно только в том случае, если соответствующий переход в сети Петри разрешен, и только возможно запустить переход в сети Петри, если есть переход из текущего состояния в помеченном им автомате. . (Определение VASS обычно формулируется несколько иначе.)
- Приоритетные сети Петри добавляют приоритеты переходам, в результате чего переход не может сработать, если включен переход с более высоким приоритетом (т. Е. Может сработать). Таким образом, переходы находятся в группах приоритета, и, например, группа приоритета 3 может срабатывать, только если все переходы отключены в группах 1 и 2. В группе приоритета срабатывание все еще недетерминировано.
- Недетерминированное свойство было очень ценным, поскольку оно позволяет пользователю абстрагироваться от большого количества свойств (в зависимости от того, для чего используется сеть). Однако в некоторых случаях возникает необходимость в моделировании сроков, а не только структуры модели. Для этих случаев эволюционировали синхронизированные сети Петри , в которых есть синхронизированные переходы и, возможно, несинхронизированные переходы (если есть, то несвязанные по времени переходы имеют более высокий приоритет, чем синхронизированные). Дочерним элементом синхронизированных сетей Петри являются стохастические сети Петри, которые добавляют недетерминированное время за счет регулируемой случайности переходов. Для « хронометрирования » этих сетей обычно используется экспоненциальное случайное распределение . В этом случае граф достижимости сетей может использоваться как цепь Маркова с непрерывным временем (CTMC).
- Дуалистические сети Петри (dP-Nets) - это расширение сети Петри, разработанное Э. Дависом и др. [21], чтобы лучше представить реальный процесс. dP-Nets уравновешивают двойственность: изменение / отсутствие изменений, действие / пассивность, (преобразование) время / пространство и т. д. между двудольными конструкциями преобразования сети Петри и местом, что приводит к уникальной характеристике маркировки преобразований , т. е. когда трансформация "рабочая" отмечена. Это позволяет преобразованию запускаться (или быть отмеченным) несколько раз, представляя реальное поведение пропускной способности процесса. Маркировка трансформации предполагает, что время трансформации должно быть больше нуля. Нулевое время преобразования, используемое во многих типичных сетях Петри, может быть математически привлекательным, но непрактичным для представления реальных процессов. dP-Nets также используют мощь иерархической абстракции сетей Петри для описания архитектуры процессов . Сложные технологические системы моделируются как ряд более простых сетей, связанных между собой через различные уровни иерархической абстракции. Архитектура процесса пакетного коммутатора продемонстрирована в [22], где требования к разработке организованы вокруг структуры спроектированной системы.
Существует еще много расширений сетей Петри, однако важно помнить, что по мере увеличения сложности сети с точки зрения расширенных свойств становится все труднее использовать стандартные инструменты для оценки определенных свойств сети. По этой причине рекомендуется использовать наиболее простой тип цепи, возможный для данной задачи моделирования.
Ограничения
Вместо того, чтобы расширять формализм сети Петри, мы можем также рассмотреть возможность его ограничения и рассмотреть определенные типы сетей Петри, полученные путем ограничения синтаксиса определенным образом. Обычные сети Петри - это сети, в которых все веса дуги равны 1. С другой стороны, обычно используются и изучаются следующие типы обычных сетей Петри:
- В конечном автомате (SM) каждый переход имеет одну входящую дугу и одну исходящую дугу, и все маркировки имеют ровно один токен. Как следствие, может не быть параллелизм , но может быть конфликт (т.е. недетерминизм ). Математически:
- В отмеченном графе (MG) каждое место имеет одну входящую дугу и одну исходящую дугу. Это означает, что конфликта быть не может , но может быть параллелизм . Математически:
- В сети со свободным выбором (FC) каждая дуга от места к переходу является либо единственной дугой от этого места, либо единственной дугой к этому переходу, то есть может быть как параллелизм, так и конфликт, но не одновременно . Математически:
- Расширенный свободный выбор (EFC) - сеть Петри, которая может быть преобразована в FC .
- В сети асимметричного выбора (AC ) могут возникать параллелизм и конфликт (в сумме, путаница ), но не симметрично . Математически:
Сети рабочего процесса
Сети рабочего процесса (WF-сети) - это подкласс сетей Петри, предназначенный для моделирования рабочего процесса действий процесса. [23] Переходы WF-net назначаются задачам или действиям, а места назначаются до / после условий. У WF-сетей есть дополнительные структурные и эксплуатационные требования, в основном добавление одного места ввода (источника) без предыдущих переходов и места вывода (приемника) без последующих переходов. Соответственно, могут быть определены отметки начала и завершения, которые представляют состояние процесса.
WF-сети обладают свойством надежности [23], указывающим, что процесс с отметкой о начале из k токенов в исходном месте, может достичь состояния завершения, отмеченного k токенами в своем месте приемника (определяется как k- звук WF-net) . Кроме того, все переходы в процессе могут срабатывать (т. Е. Для каждого перехода существует достижимое состояние, в котором переход разрешен). Общий звук (G-звук) WF-net определяется как k -звук для каждого k > 0. [24]
Направленный путь в сети Петри определяется как последовательность узлов (мест и переходов), соединенных направленными дугами. Элементарный путь включает в себя каждый узел в последовательности только один раз.
Хорошо обрабатываются сеть Петри является чистой , в котором есть не полностью различный элементарный путь между местом и переходом (или переходом и местом), то есть, если есть два пути между парой узлов , то эти пути разделяют узел . Ациклическая хорошо управляемая WF-сеть - это звук (звук G). [25]
Расширенная WF-сеть - это сеть Петри, состоящая из WF-сети с дополнительным переходом t (переход с обратной связью). Место стока соединено как входное место перехода t, а место истока - как его выходное место. Запуск перехода вызывает итерацию процесса (Примечание: расширенная WF-сеть не является WF-сетью). [23]
WRI (Хорошо обрабатывается с помощью регулярных итераций) WF-net - это расширенная ациклическая хорошо обрабатываемая WF-сеть. Сеть WRI-WF может быть построена как композиция сетей, т. Е. Замена перехода внутри сети WRI-WF подсетью, которая является сетью WRI-WF. Результат - тоже WRI-WF-net. Сети WRI-WF являются G-звуком, [25] поэтому, используя только строительные блоки WRI-WF-net, можно получить WF-сети, которые имеют G-звук по конструкции.
Дизайн матричной структуры (DSM) может моделировать процесс отношений, а также использоваться для планирования процесса. В DSM-сети являются реализацией DSM на основе планов в рабочие процессы с помощью сетей Петри, и эквивалентны МО-WF-сети. Процесс построения DSM-сети обеспечивает свойство прочности полученной сети.
Другие модели параллелизма
Были предложены и другие способы моделирования параллельного вычисления, в том числе векторного сложения систем , связи конечных автоматов , сети процессов Кана , процесс алгебру , то модель актера , и теорию следов . [26] Различные модели обеспечивают компромисс между такими понятиями, как композиционность , модульность и локальность.
Подход к связи некоторых из этих моделей параллелизма предлагается в главе Винскеля и Нильсена. [27]
Области применения
- Булево дифференциальное исчисление [28]
- Моделирование бизнес-процессов [29] [30]
- Вычислительная биология [31] [32]
- Параллельное программирование [33]
- Техника управления [14] [34] [35]
- Анализ данных [36]
- Диагностика (Искусственный интеллект) [37]
- Дискретное управление процессом [38] [39] [40]
- Теория игр [41]
- Технологические сети Кана [42]
- Моделирование процессов [43] [44] [45]
- Техника надежности [ необходима цитата ]
- Симуляторы [29]
- Разработка программного обеспечения [13]
- Системы управления рабочим процессом [46] [44] [45]
Смотрите также
- Конечный автомат
- Язык разметки сети Петри
- Петрискрипт
- Архитектура процесса
- Системы сложения векторов
Рекомендации
- ^ Петри, Карл Адам; Рейзиг, Вольфганг (2008). «Сеть Петри» . Scholarpedia . 3 (4): 6477. Bibcode : 2008SchpJ ... 3.6477P . DOI : 10,4249 / scholarpedia.6477 .
- ^ Розенбург, Г .; Энгельфриет Дж. (1998). «Элементарные сетевые системы». In Reisig, W .; Розенберг, Г. (ред.). Лекции о сетях Петри I. Основные модели - достижения в сетях Петри . Конспект лекций по информатике. 1491 . Springer. С. 12–121.
- ^ Рейзиг, Вольфганг (1991). «Сети Петри и алгебраические спецификации». Теоретическая информатика . 80 (1): 1–34. DOI : 10.1016 / 0304-3975 (91) 90203-e .
- ^ Дезель, Йорг; Юхас, Габриэль (2001). «Что такое сеть Петри? Неформальные ответы для информированного читателя». В Эриге, Хартмуте ; и другие. (ред.). Объединение сетей Петри . LNCS. 2128 . Springer. С. 1–25. DOI : 10.1007 / 3-540-45541-8_1 . ISBN 9783540430674.
- ^ Эспарса, Хавьер; Нильсен, Могенс (1995) [1994]. «Проблемы разрешимости сетей Петри - обзор» . Бюллетень EATCS (Перераб. Ред.) . Проверено 14 мая 2014 .
- ^ Липтон, Р. (1976). «Проблема достижимости требует экспоненциального пространства» . Технический отчет 62 .
- ^ Кюнгас, П. (26–29 июля 2005 г.). Проверка достижимости сети Петри является полиномиальной с оптимальными иерархиями абстракции . Материалы 6-го Международного симпозиума по абстракции, переформулировке и приближению - SARA 2005. Замок Эйрт, Шотландия, Великобритания. Архивировано из оригинала на 2012-02-09 . Проверено 10 июля 2008 .
- ^ Червинский, Войцех; Ласота, Славомир; Лазич, Ранко; Леру, Жером; Мазовецкий, Филип (2018). «Проблема достижимости сетей Петри не элементарна (расширенная аннотация)». arXiv : 1809.07115 [ cs.FL ].
- ^ Леру, Жером (2021). «Проблема достижимости сетей Петри не является примитивно рекурсивной». arXiv : 2104.12695 [ cs.LO ].
- ^ Червинский, Войцех; Орликовский, Лукаш (2021). «Достижимость в системах сложения векторов полная по Аккерману». arXiv : 2104.13866 [ cs.FL ].
- ^ Мурата, Тадао (апрель 1989 г.). «Сети Петри: свойства, анализ и приложения» . Труды IEEE . 77 (4): 541–558. DOI : 10.1109 / 5.24143 . Проверено 13 октября 2014 .
- ^ «Сети Петри» . www.techfak.uni-bielefeld.de .
- ^ а б Кучера, Эрик; Хаффнер, Ото; Драгош, Питер; Циганек, Ян; Лесковский, Роман; Штефанович, Юрай (январь 2020 г.). «Новый программный инструмент для моделирования и управления дискретно-событийными и гибридными системами с использованием сетей Петри с временной интерпретацией» . Прикладные науки . 10 (15): 5027. DOI : 10,3390 / app10155027 .
- ^ а б Давид, Рене; Алла, Хассане (2005). Дискретные, непрерывные и гибридные сети Петри . Springer. ISBN 978-3-540-22480-8.
- ^ Дженсен, Курт (1997). «Краткое введение в цветные сети Петри» (PDF) . Краткое введение в цветные сети Петри . Конспект лекций по информатике. 1217 . С. 203–208. DOI : 10.1007 / BFb0035389 . ISBN 978-3-540-62790-6.
- ^ Araki, T .; Касами, Т. (1977). «Некоторые проблемы решения, связанные с проблемой достижимости сетей Петри». Теоретическая информатика . 3 (1): 85–104. DOI : 10.1016 / 0304-3975 (76) 90067-0 .
- ^ Dufourd, C .; Финкель, А .; Schnoebelen, Ph. (1998). «Сбросить сети между разрешимостью и неразрешимостью». Материалы 25-го Международного коллоквиума по автоматам, языкам и программированию . LNCS . 1443 . С. 103–115.
- ^ Зайцев, Д.А. (2013). «К минимальной универсальной сети Петри». IEEE Transactions по системам, человеку и кибернетике: системы . 44 : 47–58. DOI : 10.1109 / TSMC.2012.2237549 . S2CID 6561556 .
- ^ «Очень краткое введение в CP-сети» . Департамент компьютерных наук, Орхусский университет, Дания.
- ^ «ЛЛПН - сети Петри с линейной логикой» . Архивировано из оригинала на 2005-11-03 . Проверено 6 января 2006 .
- ^ Дэвис, EP; Давис, Дж. Ф.; Ку, Вэй-Пин (2001). Архитектура компьютерных систем с использованием дуалистических сетей Петри . 2001 Международная конференция IEEE по системам, человеку и кибернетике. 3 . С. 1554–1558.
- ^ Давис, EP (2001). Архитектура стека протоколов SS7 на платформе широкополосного коммутатора с использованием дуалистических сетей Петри . 2001 Конференция IEEE Pacific Rim по связи, компьютерам и обработке сигналов. 1 . С. 323–326.
- ^ а б в ван дер Аалст, WMP (1998). «Применение сетей Петри для управления рабочим процессом» (PDF) . Журнал схем, систем и компьютеров . 8 (1): 21–66. CiteSeerX 10.1.1.30.3125 . DOI : 10.1142 / s0218126698000043 .
- ^ ван Хи, К .; Сидорова, Н .; Вурхув, М. (2003). «Надежность и разделимость сетей рабочего процесса при пошаговом подходе к уточнению» (PDF) . Ин ван дер Аалст, WMP; Бест, Э. (ред.). Применение и теория сетей Петри 2003 . Lect Notes in Comput Sci. 2678 . Springer. С. 337–356.
- ^ а б Пинг, Л .; Hao, H .; Цзянь, Л. (2004). Молдт, Дэниел (ред.). О надежности и надежности сетей документооборота . Материалы 3-го семинара по моделированию объектов, компонентов и агентов. 571 . Орхус, Дания: DAIMI PB. С. 21–36.
- ^ Мазуркевич, Антони (1995). «Введение в теорию следов». В Diekert, V .; Розенберг, Г. (ред.). Книга следов . Сингапур: World Scientific. С. 3–67.
- ^ Винскель, Г .; Нильсен, М. "Модели для параллелизма" (PDF) . Справочник по логике и основам информатики . 4 . ОУП. С. 1–148. Архивировано из оригинального (PDF) 04.05.2020.
- ^ Шойринг, Райнер; Велан, Герберт «Ганс» (1991-12-01) [июль 1991]. Бреттауэр, Георг (ред.). "Der Boolesche Differentialkalkül - eine Methode zur Analyze und Synthese von Petri-Netzen" [Логическое дифференциальное исчисление - метод анализа и синтеза сетей Петри]. At - Automatisierungstechnik - Methoden und Anwendungen der Steuerungs-, Regelungs- und Informationstechnik (на немецком языке). Штутгарт, Германия: R. Oldenbourg Verlag . Проверено 16 октября 2017 . (8 страниц) . 39 (7): 226–233. DOI : 10,1524 / auto.1991.39.112.226 . ISSN 0178-2312 . S2CID 56766796 . Архивировано 16 октября 2017 года
- ^ а б ван дер Аалст, WMP; Шталь, К. Моделирование бизнес-процессов - подход, ориентированный на сеть Петри . MIT Press. С. 1–400.
- ^ ван дер Аалст, WMP (2018). "Управление бизнес-процессами". Энциклопедия систем баз данных, второе издание . Springer. С. 370–374. DOI : 10.1007 / 978-1-4614-8265-9_1179 . ISBN 978-1-4614-8266-6.
- ^ Фаврин, Бин (02.09.2014). "ESYN: Построение сети, обмен и публикация" . PLOS ONE . 9 (9): e106035. Bibcode : 2014PLoSO ... 9j6035B . DOI : 10.1371 / journal.pone.0106035 . PMC 4152123 . PMID 25181461 .
- ^ Кох, Инна; Рейзиг, Вольфганг; Шрайбер, Фальк (2011). Моделирование в системной биологии - подход сети Петри . Вычислительная биология. 16 . Springer. DOI : 10.1007 / 978-1-84996-474-6 . ISBN 978-1-84996-473-9.
- ^ Кристенсен, LM; Вестергаард, М. (2010). Автоматическая генерация кода на основе структуры из разноцветных сетей Петри: подтверждение концепции . Формальные методы для промышленных критических систем - 15-й международный семинар, FMICS 2010. Конспект лекций по информатике. 6371 . С. 215–230. DOI : 10.1007 / 978-3-642-15898-8_14 .
- ^ Gao, X .; Ху, Синьян (2020). "Надежное управление нейронной сетью Петри для новой модели процесса обратной засыпки вставкой" . Доступ IEEE . 8 : 18420–18425. DOI : 10,1109 / ACCESS.2020.2968510 . S2CID 210994447 .
- ^ Кучера, Эрик; Хаффнер, Ото; Драгош, Питер; Лесковский, Роман; Циганек, Ян (январь 2020 г.). "PetriNet Editor + PetriNet Engine: новый программный инструмент для моделирования и управления дискретными системами событий с использованием сетей Петри и генерации кода" . Прикладные науки . 10 (21): 7662. DOI : 10,3390 / app10217662 .
- ^ ван дер Аалст, WMP (2016). Process Mining - Data Science in Action, Second Edition . Springer. DOI : 10.1007 / 978-3-662-49851-4 . ISBN 978-3-662-49850-7. S2CID 12806779 .
- ^ Carmona, J .; ван Донген, Б.Ф .; Solti, A .; Вайдлих, М. (2018). Проверка соответствия - взаимосвязанные процессы и модели . Springer. DOI : 10.1007 / 978-3-319-99414-7 . ISBN 978-3-319-99413-0. S2CID 53250018 .
- ^ Фернандес, Дж. Л.; Sanz, R .; Paz, E .; Алонсо, К. (19–23 мая 2008 г.). «Использование иерархических двоичных сетей Петри для создания надежных приложений для мобильных роботов: RoboGraph». IEEE Международная конференция по робототехнике и автоматизации, 2008 . Пасадена, Калифорния, США. С. 1372–1377. DOI : 10.1109 / ROBOT.2008.4543394 .
- ^ Мендес, Дж. Марко; Лейтао, Паулу; Коломбо, Армандо В .; Рестиво, Франциско (2012). «Сети Петри высокого уровня для описания и контроля процессов в сервис-ориентированных производственных системах» . Международный журнал производственных исследований . Тейлор и Фрэнсис. 50 (6): 1650–1665. DOI : 10.1080 / 00207543.2011.575892 . S2CID 39688855 .
- ^ Fahland, D .; Гирдс, К. (2013). Анализ и завершение проектов промежуточного программного обеспечения для корпоративной интеграции с использованием цветных сетей Петри . Передовая инженерия информационных систем - 25-я Международная конференция, CAiSE 2013. Конспект лекций по информатике. 7908 . С. 400–416. DOI : 10.1007 / 978-3-642-38709-8_26 .
- ^ Клемпнер, Хулио (2006). «Моделирование игр кратчайшего пути с помощью сетей Петри: теория, основанная на Ляпунове» . Международный журнал прикладной математики и информатики . 16 (3): 387–397. ISSN 1641-876X .
- ^ Бернардески, C .; De Francesco, N .; Ваглини, Г. (1995). «Семантика сетей Петри для сетей с потоками данных» . Acta Informatica . 32 (4): 347–374. DOI : 10.1007 / BF01178383 . S2CID 7285573 .
- ^ ван дер Аалст, член парламента Виль; Шталь, Кристиан; Вестергаард, Майкл (2013). «Стратегии моделирования сложных процессов с использованием раскрашенных сетей Петри» . Пер. Сети Петри Другая модель. Concurr . Конспект лекций по информатике. 7 : 6–55. DOI : 10.1007 / 978-3-642-38143-0_2 . ISBN 978-3-642-38142-3.
- ^ а б ван дер Аалст, WMP (2018). «Шаблоны рабочего процесса». Энциклопедия систем баз данных, второе издание . Springer. С. 4717–4718. DOI : 10.1007 / 978-1-4614-8265-9_826 . ISBN 978-1-4614-8266-6.
- ^ а б ван дер Аалст, WMP (2018). «Анализ модели рабочего процесса». Энциклопедия систем баз данных, второе издание . Springer. С. 4716–4717. DOI : 10.1007 / 978-1-4614-8265-9_1476 . ISBN 978-1-4614-8266-6.
- ^ тер Хофстеде, Артур Х.М.; ван дер Аалст, член парламента Виль; Адамс, Майкл; Рассел, Ник (2010). Хофстеде, Артур Х. М.; Aalst, Wil M.P; Адамс, Майкл; Рассел, Ник (ред.). Современная автоматизация бизнес-процессов - YAWL и среда его поддержки . DOI : 10.1007 / 978-3-642-03121-2 . ISBN 978-3-642-03122-9.
дальнейшее чтение
- Кардозу, Джанетт; Камарго, Элоиза (1999). Нечеткость в сетях Петри . Physica-Verlag. ISBN 978-3-7908-1158-2.
- Кьячио, Мануэль; Кьячио, Хуан; Пресскотт, Даррен; Эндрюс, Джон (2018). «Новая парадигма представления неопределенных знаний с помощью« Правдоподобных сетей Петри » » . Информационные науки . 453 (июль 2018 г.): 323-345. DOI : 10.1016 / j.ins.2018.04.029 .
- Гробельна, Ивона (2011). «Формальная проверка спецификации встроенного логического контроллера с компьютерным выводом во временной логике». Przeglad Elektrotechniczny . 87 (12a): 47–50.
- Дженсен, Курт (1997). Цветные сети Петри . Springer Verlag. ISBN 978-3-540-62867-5.
- Патарича, Андраш (2004). Formális módszerek az informatikában (Формальные методы в информатике) . TYPOTEX Kiadó. 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). Теория сетей Петри и моделирование систем . Прентис Холл. ISBN 978-0-13-661983-3.
- Петри, Карл Адам (1962). Коммуникация с автоматами (кандидатская диссертация). Боннский университет.
- Петри, Карл Адам; Рейзиг, Вольфганг (2008). «Сеть Петри» . Scholarpedia . 3 (4): 6477. Bibcode : 2008SchpJ ... 3.6477P . DOI : 10,4249 / scholarpedia.6477 .
- Рейзиг, Вольфганг (1992). Учебник по дизайну сетей Петри . Springer-Verlag. ISBN 978-3-540-52044-3.
- Риман, Роберт-Кристоф (1999). Моделирование параллельных систем: структурные и семантические методы в исчислении сети Петри высокого уровня . Герберт Утц Верлаг. ISBN 978-3-89675-629-9.
- Стёррле, Харальд (2000). Модели архитектуры программного обеспечения - проектирование и анализ с помощью UML и сетей Петри . Книги по запросу. ISBN 978-3-8311-1330-9.
- Зайцев, Дмитрий (2013). Кланы сетей Петри: проверка протоколов и оценка производительности сетей . LAP LAMBERT Academic Publishing. ISBN 978-3-659-42228-7.
- Чжоу, Мэнчу ; Dicesare, Франк (1993). Синтез сетей Петри для дискретного управления производственными системами . Kluwer Academic Publishers. ISBN 978-0-7923-9289-7.
- Чжоу, Мэнчу ; Венкатеш, Курапати (1998). Моделирование, имитация и управление гибкими производственными системами: подход сети Петри . Мировое научное издательство. ISBN 978-981-02-3029-6.
Внешние ссылки
- Мир сетей Петри
- Язык разметки сети Петри
- Реализация сетей Петри на Java в библиотеке jBPT (см. Модуль jbpt-petri)
- Симулятор сети Петри на Java
- Введение в технологию рабочего процесса с сетями Петри на основе Flash от Пети Вохэд.
- Список инструментов сети Петри