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

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

Безопасность и ограниченность.

Позиция p€P называется k – ограниченой, если существует такое k, что M(p)≤k для каждого M€R(N). Если

Рис.44

(1, 1,0,0,0)

(0,0,1,2,0)

(1,0,0,2,1) (1,1,1,1,0)

(1,0,0,3,0) (2,1,0,1,1) (0,0,2,3,0) (2,2,1,0,0)

Рис. 45

k-1, то эта позиция называется безопасной. Сеть Петри безопасна, если безопасна любая её позиция. Сеть является k-ограниченной, если её позиции k – ограничены. Проблема ограничения разрешима для любой сети Петри.

Ограниченность сети свидетельствует о конечности состояний отдельных элементов системы.

Живость. Сеть N – живая, если, во-первых, для каждого tT существуют. _i ,_jR(N) такие, что _i ^t _j ; Во вторых, для каждой пары _i ,_jR(N) маркировка _j достижима из _i

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

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

Например, для автономных и маркированных графов, доказаны теоремы:

1. если автономная сеть представляет собой сильно связанный граф, то каждая маркировка с одним маркером – живая и безопасная;

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

Сохраняемость. Сеть Петри называется сохраняющей по отношению к весовому вектору =(₁ ,…, _n ) _i  0,

n=|P|, если для каждой маркировки R(N) выполняется

_{i=n i=n}

 _i (p_i ) =  _i ₀(p_i )

^{i=1 i=1}

Если _i =1 для всех i=1…n, то сеть называется строго сохраняющей. Необходимым условием сохраняемости является ограниченность сети, а достаточным - наличие вектора  .

Сохраняемость сети свидетельствует о невозможности уничтожения или возникновения маркеров.

Достижимость. Проблема достижимости заданной маркировки  из начальной ₁ эквивалентна следующим задачам:

• определение достижимости нулевой маркировки (0,0,…,0);

• определение достижимости подмножества позиций для  1

• определение достижимости маркировки ¹ , покрывающей маркировку  покомпонентно.

Анализ достижимости позволяет получить допустимые и недопустимые состояния сети.