Сети Петри — математический аппарат для моделирования динамических дискретных систем. Впервые описаны Карлом Петри в 1962 году.
Сеть Петри представляет собой двудольный ориентированный мультиграф, состоящий из вершин двух типов — позиций и переходов, соединённых между собой дугами. Вершины одного типа не могут быть соединены непосредственно. В позициях могут размещаться метки (маркеры), способные перемещаться по сети.
Событием называют срабатывание перехода, при котором метки из входных позиций этого перехода перемещаются в выходные позиции. События происходят мгновенно, либо разновременно, при выполнении некоторых условий.
Сеть Петри есть мультиграф, так как он допускает существование кратных дуг от одной вершины графа к другой. Так как дуги являются направленными, то это ориентированный мультиграф. Вершины графа можно разделить на два множества (позиции и переходы) таким образом, что каждая дуга будет направлена от элемента одного множества (позиций или переходов) к элементу другого множества (переходов или позиций); следовательно, такой граф является двудольным ориентированным мультиграфом.
Сети Петри разрабатывались для моделирования систем с параллельными взаимодействующими компонентами. Сети Петри впервые предложил Карл Адам Петри. В докторской диссертации «Связь автоматов» он сформулировал основные понятия теории связи асинхронных компонент вычислительной системы[1].
Процесс функционирования сети Петри может быть наглядно представлен графом достижимых маркировок. Состояние сети однозначно определяется её маркировкой — распределением фишек по позициям. Вершинами графа являются допустимые маркировки сети Петри, дуги помечены символом срабатывающего перехода. Дуга строится для каждого возбуждённого перехода. Построение прекращается, когда мы получаем маркировки, в которых не возбуждён ни один переход либо маркировки, содержащиеся в графе. Отметим, что граф достижимых маркировок представляет собой автомат.
Некоторые виды сетей Петри:
Основными свойствами сети Петри являются:
В основе исследования перечисленных свойств лежит анализ достижимости. Методы анализа свойств сетей Петри основаны на использовании графов достижимых (покрывающих) маркировок, решении уравнения состояний сети и вычислении линейных инвариантов позиций и переходов. Применяются также вспомогательные методы редукции, позволяющие уменьшить размер сети Петри с сохранением ее свойств, и декомпозиции[2], разделяющие исходную сеть на подсети.
В 1974 году Тилак Аджервала показал, что ингибиторная сеть Петри является универсальной алгоритмической системой. В монографии Котова В. Е. приведен набросок доказательства, указывающий правила кодирования ингибиторной сетью программы счетчикового автомата Минского. Питерсон Дж. приводит примеры других расширенных классов сетей Петри, являющихся универсальной алгоритмической системой: синхронных и приоритетных. Построенная в явном виде универсальная сеть Петри[3] насчитывала несколько тысяч вершин и недавно была уменьшена до 56 вершин[4].
Бесконечные сети Петри были введены для верификации вычислительных решеток и позволяют определять свойства сетей Петри для регулярных структур (линейная, древовидная, квадратная, треугольная, шестиугольная и гиперкуб[5]) произвольного размера, полученных путем композиции типовых фрагментов.
Сети Петри.
