Определение. Задача покрываемости.

Для заданной сети Петри С с начальной маркировкой m и маркировки m' определить, существует ли такая достижимая маркировка m'' принадлежащая R(C, m), что m'' >= m. Маркировка m'' покрывает m'.

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

Вопрос №10

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

· ограниченность — число меток в любой позиции сети не может превысить некоторого значения K;

· безопасность — частный случай ограниченности, K=1;

· сохраняемость — постоянство загрузки ресурсов, постоянна. Где — число маркеров в i-той позиции, — весовой коэффициент;

· достижимость — возможность перехода сети из одного заданного состояния (характеризуемого распределением меток) в другое;

· живость — возможность срабатывания любого перехода при функционировании моделируемого объекта.

В основе исследования перечисленных свойств лежит анализ достижимости.

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

Определение.

Позиция p_i принадлежащая P сети Петри С = (Р, Т, I, О) с начальной маркировкой m является безопасной, еслиm '(p_i) <= 1 для любой m' принадлежащей R(C, m). Сеть Петри безопасна, если безопасна каждая ее позиция.

Безопасность - очень важное свойство для устройств аппаратного обеспечения.

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

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

если p_i принадлежит I(t_j) и p_i не принадлежит O(t_j), тогда добавить p_i' к O(t_j);

если p_i принадлежит O(t_j) и p_i не принадлежит I(t_j), тогда добавить p_i' к I(t_j).

Цель введения этой новой позиции p_i ' - представить дополнительное условие (p_i пуста). Следовательно p_i и p_i'находятся в следующей зависимости: p_i имеет фишку, только если p_i ' не имеет фишки и наоборот. Любой переход, удаляющий фишку из p_i должен помещать фишку в p_i ', а всякий переход, удаляющий фишку из p_i ', должен помещать фишку в p_i. Начальная маркировка также должна быть модифицирована для обеспечения того, чтобы только одна фишка была либо в p_i, либо в p_i '.Такая принудительная безопасность возможна лишь для позиций, которые в начальной маркировке являются безопасными, и входная, и выходная кратность которых равна 0 или 1 для всех переходов. Позиция, имеющая для некоторого перехода выходную кратность 2, будет получать при его запуске две фишки и, следовательно, не может быть безопасной. На рисунке 1 простая сеть Петри (а) преобразована в безопасную (б).

Рис.1. Сеть Петри, не являющаяся безопасной (а), и безопасная сеть Петри (б), эквивалентная сети (а)

Вопрос №11