Раскрашенная сеть петри позволяет

Сети Петри. Структура и правила выполнения сетей Петри.

Сети Петри Править

Сети Петри — математический аппарат для моделирования динамических дискретных систем. Впервые описаны Карлом Петри в 1962 году.

Пример работы сети Петри

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

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

Как и стандартные UML диаграммы, BPMN и EPC, сети Петри предоставляют возможность графически иллюстрировать процессы включающие выбор, итерации и одновременное выполнение. Но в отличие от данных стандартов, у сетей Петри четкая математическая формулировка и за ними стоит развитая математическая теория.

$ Введите сюда формулу $ ==Структура сетей Петри==

Сеть Петри состоит из 4-х элементов:

• множество позиций P,
• множество переходов T,
• входная функция I,
• выходная функция O.

Пример сети Петри. Белыми кружками обозначены позиции, полосками — переходы, чёрными кружками — метки.

Входная и выходная функции связаны с переходами и позициями. Входная функция I отображает переход t_j в множество позиций I(t_j) , называемых входными позициями перехода . Выходная функция O отображает переход p_i в множество позиций O(p_i) , называемых выходными позициями перехода . Структура сети Петри определяется её позициями, переходами, входной и выходной функциями.

Сеть Петри С является четверкой, C=(P,T,I,O). P=1, p₂, . p_i, p_n> — конечное множество позиций, n>=0. T=< t₁, t₂, . t_j, t_m > — конечное множество переходов, m>=0. Множество позиций и множество переходов не пересекаются, то есть пересечение P и T равно пустому множеству. I: T->P ¥ является входной функцией — отображением из переходов в комплекты позиций. O: P ¥ ->T есть выходная функция — отображение из комплектов позиций в переходы.

Произвольный элемент P обозначается символом p_i , i=1, . n, а произвольный элемент T — символом t_j, j=1, . m.

Правила выполнения сетей Петри Править

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

Переход запускается, если он разрешен. Переход называется разрешенным, если каждая из его входных позиций имеет число фишек по крайней мере равное числу дуг из позиции в переход. Фишки во входной позиции, которые разрешают переход, называются его разрешающими фишками. Например, если позиции р1 и р2 служат входами для перехода t1, тогда t1 разрешен, если р1 и р2 имеют хотя бы по одной фишке. Для перехода t3 с входным комплектом позиция р3 должна иметь не менее 3 фишек для разрешения перехода t3.

Определение. Переход $ t_j in T $ маркированной сети Петри $ C = (P, T, I, O, mu) $ с маркировкой $ mu $ , разрешен, если для всех $ p_j in P $ , $ mu (p_i) geq # (p_i, I(t_j)) $ .

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

>Переход t3 I(t3) = и O(t3) = разрешен каждый раз, когда в р2 будет хотя бы одна фишка. Переход t3 запускается удалением одной фишки из позиции р2 и помещением одной фишки в позицию р3 и р4 (его выходы). Переход t4, в котором I(t4) = и O(t4) = запускается удалением по одной фишке из позиций р4 и р5, при этом одна фишка помещается в р5 и две в р6 (рис. 2).

Определение. Переход $ t_j $ в маркированной сети Петри с маркировкой $ mu $ может быть запущен всякий раз, когда он разрешен. В результате запуска разрешенного перехода $ t_j $ образуется новая маркировка $ mu^ <'>$ :

$ mu^ <'>(p_i) = mu (p_j) — # (p_i, I(t_j) + # (p_i, O(t_j)) $

Сети Петри. Структура и правила выполнения сетей Петри.

Сети Петри Править

Сети Петри — математический аппарат для моделирования динамических дискретных систем. Впервые описаны Карлом Петри в 1962 году.

Пример работы сети Петри

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

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

Как и стандартные UML диаграммы, BPMN и EPC, сети Петри предоставляют возможность графически иллюстрировать процессы включающие выбор, итерации и одновременное выполнение. Но в отличие от данных стандартов, у сетей Петри четкая математическая формулировка и за ними стоит развитая математическая теория.

$ Введите сюда формулу $ ==Структура сетей Петри==

Сеть Петри состоит из 4-х элементов:

• множество позиций P,
• множество переходов T,
• входная функция I,
• выходная функция O.

Пример сети Петри. Белыми кружками обозначены позиции, полосками — переходы, чёрными кружками — метки.

Входная и выходная функции связаны с переходами и позициями. Входная функция I отображает переход t_j в множество позиций I(t_j) , называемых входными позициями перехода . Выходная функция O отображает переход p_i в множество позиций O(p_i) , называемых выходными позициями перехода . Структура сети Петри определяется её позициями, переходами, входной и выходной функциями.

Сеть Петри С является четверкой, C=(P,T,I,O). P=1, p₂, . p_i, p_n> — конечное множество позиций, n>=0. T=< t₁, t₂, . t_j, t_m > — конечное множество переходов, m>=0. Множество позиций и множество переходов не пересекаются, то есть пересечение P и T равно пустому множеству. I: T->P ¥ является входной функцией — отображением из переходов в комплекты позиций. O: P ¥ ->T есть выходная функция — отображение из комплектов позиций в переходы.

Произвольный элемент P обозначается символом p_i , i=1, . n, а произвольный элемент T — символом t_j, j=1, . m.

Правила выполнения сетей Петри Править

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

Переход запускается, если он разрешен. Переход называется разрешенным, если каждая из его входных позиций имеет число фишек по крайней мере равное числу дуг из позиции в переход. Фишки во входной позиции, которые разрешают переход, называются его разрешающими фишками. Например, если позиции р1 и р2 служат входами для перехода t1, тогда t1 разрешен, если р1 и р2 имеют хотя бы по одной фишке. Для перехода t3 с входным комплектом позиция р3 должна иметь не менее 3 фишек для разрешения перехода t3.

Определение. Переход $ t_j in T $ маркированной сети Петри $ C = (P, T, I, O, mu) $ с маркировкой $ mu $ , разрешен, если для всех $ p_j in P $ , $ mu (p_i) geq # (p_i, I(t_j)) $ .

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

>Переход t3 I(t3) = и O(t3) = разрешен каждый раз, когда в р2 будет хотя бы одна фишка. Переход t3 запускается удалением одной фишки из позиции р2 и помещением одной фишки в позицию р3 и р4 (его выходы). Переход t4, в котором I(t4) = и O(t4) = запускается удалением по одной фишке из позиций р4 и р5, при этом одна фишка помещается в р5 и две в р6 (рис. 2).

Определение. Переход $ t_j $ в маркированной сети Петри с маркировкой $ mu $ может быть запущен всякий раз, когда он разрешен. В результате запуска разрешенного перехода $ t_j $ образуется новая маркировка $ mu^ <'>$ :

$ mu^ <'>(p_i) = mu (p_j) — # (p_i, I(t_j) + # (p_i, O(t_j)) $

Цветные сети Петри

Расширение простых сетей в цветные заключается в добавлении информации к элементам сети, основываясь на которой, при определённых условиях, можно преобразовать цветные сети в простые ([8]).

1. Токены вместо простого обозначения содержимого места преобразуются в объект, который может содержать в себе один или более параметров, каждый из которых может принимать дискретный набор значений. В соответствии с этим токены различаются по типам параметров (переменных). Чтобы отличать токены различных типов их можно окрашивать в различные цвета (поэтому сети называют цветными)

2. К местам добавляется информация о типах токенов, которые могут находится в данном месте.

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

4. К переходам может быть добавлена информация с предикатом возбуждения перехода, в зависимости от переменных, содержащихся в токенах.

(and )

5. К дугам, исходящим из переходов, добавляется информация о типах токенов, исходящих из перехода и о преобразовании переменных.

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

В графическом представлении информацию, которую можно однозначно достроить из сопутствующей информации, можно пропускать. Приведем пример цветной сети Петри (Рис. 6)

Рис. 6: Пример цветной сети Петри (очередь)

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

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

Точки доступа в цветной сети

S-точка доступа. Как видно из определения s-точки доступа, она задаётся множеством маркировок, которые считаются эквивалентными в смысле наступления состояний, определённых этими маркировками, в синхронизируемых по s-точке доступа сетях. При задании s-точки доступа в цветной сети, маркировки могут содержать в себе места, в которые могут поступать токены различных типов. Такие места при преобразовании в простую сеть разбиваются на множество мест, количество которых равно мощности множества значений токенов допустимых в этом месте. Согласно смыслу операции мы обязаны будем в синхронизированной сети раздробить эти места, чтобы удовлетворить множеству значений токенов во второй сети. Получается, что при синхронизации мест одинакового типа (с одинаковыми допустимыми типами токенов) значение параметров одной сети никак не влияет на значение параметров другой, то есть смысл операции в цветных и простых сетях может пониматься по-разному. Чтобы этого избежать, надо доопределить s-точку доступа:

Пусть заданы: цветная сеть N и С – множество типов токенов в этой сети. Тогда s-точкой доступа сети N называется набор , где

1. — имя (идентификатор) s-точки доступа;

2. — некоторый алфавит;

3. — множество такое, что .

4. , где , причём если . — пометочная функция мест, ставящая в соответствие каждому типу токена в месте уникальное имя из алфавита.

В операции слияния цветных сетей по местам, необходимо убрать расщепление мест по токенам с определёнными именами. Фактически, это означает переопределение операции слияния по одной s-точке доступа в простых сетях в операцию слияния серии точек доступа цветных сетей, пронумерованных значениями параметров с именами. Можно показать, что изменённая таким образом операция не меняет своих свойст.

Рис. 7: Пример слияния цветных сетей Петри по S-точке доступа

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

Рис. 8: Пример слияния цветных сетей по T-точке доступа

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

Рис. 9: T-Слияние простых сетей из рисунка 8.

Рис. 10: Представление композициональных сетей Петри на уровне взаимодействия сетей.