Безопасность и ограниченность.( до 50 минут)

Позиция 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)

Рис. 26.1

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

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

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

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

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

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

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

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

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

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

_{i=n i=n}

å l_i m(p_i ) = å l_i m₀(p_i )

^{i=1 i=1}

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

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

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

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

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

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

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

Лекция №27.

Дата добавления: 2015-12-01