Свойства сетей петри дерево достижимости

4.5.3 Анализ свойств сетей Петри на основе дерева достижимости

Анализ безопасности и ограниченности. Сеть Петри ограничен- на тогда и только тогда, когда символ w отсутствует в ее дереве достижимости. Присутствие символа w в дереве достижимости ( m [ x ] ( p ) = w для некоторой вершины x и позиции p ) означает, что для произвольного положительного целого k существует достижимая маркировка со значением в позиции p , большим, чем k (а также бесконечность множества достижимых маркировок). Это, в свою очередь, означает неограниченность позиции p , а следовательно, и самой сети Петри. Отсутствие символа w в дереве достижимости означает, что множество достижимых маркировок конечно. Следовательно, простым перебором можно найти верхнюю границу, как для каждой позиции в отдельности, так и общую верхнюю границу для всех позиций. По-

следнее означает ограниченность сети Петри. Если граница для всех позиций равна 1, то сеть Петри безопасна. Анализ сохранения. Так как дерево достижимости конечно, для каждой маркировки можно вычислить сумму начальной маркировки. Если эта сумма одинакова для каждой достижимой маркировки, то сеть Петри является сохраняющей. Если суммы не равны, сеть не является сохраняющей. Если маркировка некоторой позиции совпадает с w , то эта позиция должна был исключена из рассмотрения. Анализ покрываемости. Задача покрываемости требуется для заданной маркировки m ¢ определить, достижима ли маркировка m ¢¢ ³ m ¢ . Такая задача решается путём простого перебора вершин де-

рева достижимости. При этом ищется	такая вершина x ,	что
m [ x ] ³ m ¢ . Если такой вершины не существует,	то маркировка m ¢	не

является покрываемой. Если она найдена, то m [ x ] определяет покры- вающую маркировку для m ¢ . Если компонента маркировки m [ x ] , со- ответствующая некоторой позиции p совпадает с w , то конкретное её значение может быть вычислено. В этом случае на пути от начальной маркировки к покрывающей маркировке имеется повторяющаяся последовательность переходов, запуск которой увеличивает значение маркировки в позиции p . Число таких повторений должно быть та- ким, чтобы значение маркировки в позиции p превзошло или сравнялось с m ¢ ( p ) . Анализ живости. Переход t сети Петри является потенциально живым, тогда и только тогда, когда он метит некоторую дугу в дереве достижимости этой сети. Доказательство очевидно. Ограниченность метода дерева достижимости . Как видно из предыдущего, дерево достижимости можно использовать для решения задач безопасности, ограниченности, сохранения и покрываемости. К сожалению, в общем случае его нельзя использовать для решения задач достижимости и активности, эквивалентности. Решение этих задач ограничено существованием символа w . Символ w означает потерю информации: конкретные количества фишек отбрасываются, учитывается только существование их большого числа.

4.5.3 Матричные уравнения

Другой подход к анализу сетей Петри основан на матричном представлении сетей Петри и решении матричных уравнений. Альтерна-

тивным

по отношению

к

определению

сети

Петри N

в

виде

( P , T , I , O ) является определение

сети N в виде двух матриц

D — и

D + , представляющих входную и выходную функции I и O . Пусть

каждая из матриц D —

и D +

имеет m =

T

строк (по одной на переход)

и n =

P

ê столбцов (по одному на позицию).

Матричный

вид

сети

Петри N = ( P , T , I , O )

задаётся

парой

( D — , D + ) , где

D — [ k , i ] = ^ # ( p i , t k

)

–

кратность

дуги,

ведущей из

позиции p i

в

переход t k ;

D + [ k , i ] = #^ ( p i , t k )

–

кратность дуги,

ведущей из перехода t k

в

позицию p i ,

для произвольных 1 £ k £ m ,

1 £ i £ n .

Пусть e [ k ] — m -вектор, k -тый элемент которого равен1, а ос-

тальные

равны0.

Переход

t k , 1 £ k £ m , в маркировке m разрешен,

если m ³ e [ k ] D — .

Результатом

запуска разрешённого перехода t k в

маркировке m является следующая ниже маркировка m ¢ :

¢

[

]

—

[

+

[

]

m

= m

— e

k

D

+ e

k =

D m + e

k

D ,

]

где D = ( D + — D — )

— составная матрица изменений .

Источник

Анализ сетей Петри

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

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

Более общим свойством, чем безопасность, является ограниченность. Говорят, что сеть Петри является k-ограниченной, если в любой достижимой маркировке количество фишек в любой позиции не превосходит k.

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

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

При рассмотрении задачи активности анализируется возможность запуска позиции сети Петри. Можно определить различные уровни активности перехода t_j в сети Петри С с маркировкой μ. Уровень активности 0 означает, что переход t_j никогда не сможет быть запущен.

Уровень 1. Переход t_j потенциально запустим, т.е. существует , в которой переход t_j потенциально разрешён.

Уровень 2. Если для всякого целого n существует последовательность запусков, в которой переход t_j присутствует, по крайней мере, n раз.

Уровень 3. Существует такая бесконечная последовательность запусков, в которой переход t_j присутствует неограниченно часто.

Уровень 4. Для любой достижимой маркировки существует такая последовательность запусков σ, что в результате её применения, начиная с маркировки , мы придём к маркировке, в которой переход t_j является разрешённым.

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

Методы анализа сетей Петри. Дерево достижимости

Дерево достижимости представляет собой множество достижимости сети Петри. Рассмотрим следующую сеть Петри.

Error: Reference source not found

При этой маркировке разрешёнными являются переходы t₁ и t₂.

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

Построим дерево достижимости.

(2,0,0)

t₁ t₂ t₃

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

t₃

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

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

Для сведения дерева достижимости к конечному можно использовать ещё одно средство.

Рассмотрим последовательность запусков переходов σ, начинающуюся в некоторой маркировке μ. Пусть конечной маркировкой при этом будет μ’, для которой μ’> μ (сравнение идёт покомпонентно), т.е. в некоторых позициях для маркировки μ’ количество фишек будет больше, чем в маркировке μ (в остальных позициях количества фишек будут совпадать).

Условно мы можем записать μ’= μ+( μ’- μ), (μ’- μ)>0. Поскольку лишние фишки не мешают запуску переходов, то мы можем последовательность переходов σ запустить, начиная с маркировки μ’ и получить маркировку μ”= μ’+( μ’- μ)= μ+2(μ’- μ).

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

Представим значение “” в маркировке символом ω. Будем считать, что для любого постоянного значения а ω+а=ω и ω-а=ω.

Алгоритм формирования дерева достижимости: каждая вершина i дерева достижимости связана с расширенной маркировкой μ[i]. В этой маркировке число фишек может быть либо неотрицательным целым, либо бесконечным, обозначаемым ω. Каждая вершина дерева может быть одного из четырёх типов:

1. граничная

1. терминальная

1. дублирующая
2. внутренняя

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

1. Если в дереве достижимости имеется другая вершина y, не являющаяся граничной, такая, что μ[у]= μ[х], то вершина х становится дублирующей.

1. Если для маркировки μ[х] ни один из переходов не разрешён, то вершина х становится терминальной.

1. Для всякого перехода , разрешённого в маркировке μ[х], необходимо создать новую вершину z дерева достижимости. Маркировка μ[z], связанная с этой вершиной, для каждой позиции определяется следующим образом:

а) Если μ[х]_i=ω, то μ[z]_i=ω. б) Если на пути от корневой вершины к вершине х существует вершина у такая, что маркировка μ[у]<δ(μ[х], t_j) и, кроме того, в μ[у]_i<δ(μ[х], t_j)_i, то μ[z]_i=ω. в) В противном случае μ[z]_i= δ(μ[х], t_j)_i. Дуга помечается запущенным переходом t_j, которая направляется от вершины х к вершине z дерева достижимости. Вершина z помечается как граничная. После просмотра всех переходов, которые можно запустить при маркировке μ[х], вершина х помечается как внутренняя. Прекращение работы алгоритма осуществляется тогда, когда в дереве достижимости не останется граничных вершин. Основным свойством алгоритма построения дерева достижимости является то, что он заканчивает свою работу. Для доказательства этого необходимо показать, что алгоритм не может создавать новых граничных вершин бесконечно. Доказательство основано на трёх леммах. Лемма 1. В любом бесконечном направленном дереве, в котором всякая вершина имеет только конечное число непосредственно следующих вершин, существует бесконечный путь, исходящий из корня. Лемма 2. Всякая бесконечная последовательность неотрицательных целых чисел содержит бесконечную неубывающую подпоследовательность. Лемма 3. Всякая бесконечная последовательность n-мерных векторов, содержащих элементы как неотрицательные целые числа , содержит бесконечную неубывающую подпоследовательность. Теорема: дерево достижимости сети Петри конечно. Доказательство: Предположим противное, т.е. существует бесконечное дерево достижимости. Тогда, согласно Лемме 1, в нём имеется бесконечный путь х₀,х₁,х₂,…, исходящий из корня х_0. Тогда мы имеем μ[х₀], μ[х₁], μ[х₂],…, бесконечную последовательность n-мерных векторов со значениями, которые определены в Лемме 3. Согласно ей должна существовать бесконечная неубывающая подпоследовательность . Но, согласно алгоритму, мы не можем иметь ситуации, что , поскольку одна из этих вершин была бы дублирующей и не имела бы продолжений. Таким образом, мы имеем последовательность строго возрастающих маркировок . Но по построению дерева достижимости, если , то нам следует заменить хотя бы одну компоненту маркировки на символ ω. Таким образом, для имеющейся последовательности мы имеем, что содержит, по крайней мере, один символ ω. — по крайней мере, два символа ω и т.д. Т.е. не далее, чем маркировка содержит все n символов ω, а это означает, что следующая маркировка подпоследовательности уже не может быть строго больше, чем . Полученное противоречие доказывает конечность дерева достижимости. Использование дерева достижимости позволяет решать поставленные ранее задачи анализа сетей Петри. Для этого необходимо будет просмотреть узлы дерева достижимости. 6

Источник