Свойства сетей Петри

Свойства условий: ограниченность и безопасность

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

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

 

Определение 2.8. Условие (место) р в сети À называется ограниченным, если существует число n такое, что для любой достижимой в сети разметки М справедливо неравенство М(р) £ n. Сеть называется ограниченной, если любое ее место ограниченно.

 

Ясно, что множество достижимых разметок R(À) конечно, если и только если À - ограниченная сеть.

 

Определение 2.9. Условие р называется безопасным, если для любой МÎ R(À): М(р) £ 1. Сеть безопасна, если все ее места безопасны.

 

То есть любая достижимая в безопасной сети разметка представляет собой вектор из 0 и 1.

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

Родственным этим понятиям является понятие консервативной сети.

 

Определение 2.10. Консервативной называют сеть, в которой сумма фишек во всех ее местах остается постоянной при ее работе, то есть

для любых M₁, M₂Î R(À): M₁(p) = M₂(p)

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

Свойства переходов: живость и устойчивость

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

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

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

 

Определение 2.11. Переход t в сети À называется потенциально живым при разметке МÎR(À), если существует

M’ÎR(À,M) : M’³ F(p,t),

То есть существует достижимая от М разметка М’, при которой переход t может сработать.

Если М = М₀, то t называется потенциально живым в сети À.

 

Определение 2.12. Переход t в сети Àназывается живым, если для любой разметки MÎR(À) существует M’ÎR(À,M) : M’ ³ F(p,t).

То есть он потенциально живой при любой достижимой в сети разметке.

Сеть называется живой, если все ее переходы живы.

 

Определение 2.13. Переход t называется потенциально мертвым, если существует MÎR(À) такая, что при любой разметке M’ÎR(À,M) переход t не может сработать.

 

Определение 2.14. Переход t - мертвый при разметке М, если не существует разметки М’, достижимой от М, при которой он может сработать.

Переход t – мертвый в сети, если он мертвый при любой достижимой в сети разметке.

 

Определение 2.15. Переход t называется устойчивым в сети À, если для любого t’ÎT {t} и любой MÎR(À) из того что (M ³ F(p,t)) & (M ³ F(p,t’)) следует M ³ F(p,t) + F(p,t’).

То есть, если переход t может сработать, то никакой другой переход не может, сработав, лишить его этой возможности.

Сеть À устойчива, если все ее переходы устойчивы.

 

Определение 2.16. Разметку М сети À будем называть конфликтной, если найдутся множества совместно возможных при М множеств событий Т₁ и Т₂ (Т₁,Т₂ Í Т, Т₁¹Т₂) и Т₂ не является множеством совместно возможных событий при M’, М М’.

 

Сеть Петри будем называть устойчивой, если R(À) не содержит конфликтных разметок.

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

 

Эквивалентность и включение

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

 

Определение 2.17. Сеть Петри À с начальной разметкой М и сеть Петри À’ с начальной разметкой М’ эквивалентны, если справедливо R(À,М)= R(À’,М’).

 

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

Более слабым, по сравнению с эквивалентностью, является свойство включения, определение которого совпадает с определением эквивалентности, с точностью до замены = на Í.