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

Вопрос №9,16

На этом шаге мы рассмотрим вопросы, связанные с достижимостью и покрываемостью в сетях Петри.

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

Для данной сети Петри С = (P, T, I, O) с маркировкой m и маркировки m' определить: m', принадлежащее R(C, m).

Задача достижимости - основная задача анализа сети Петри. Многие задачи анализа могут быть сформулированы в терминах такой задачи достижимости.

Множество достижимости сети Петри представляет собой дерево достижимости. Пусть имеется сеть Петри, представленная на рисунке 1.

Рис.1. Маркированная сеть Петри, для которой строится дерево достижимости

Ее начальная маркировка - (1, 0, 0). В этой начальной маркировке разрешены t₁ и t₂. Чтобы рассмотреть все множество достижимости, определим новые вершины в дереве достижимости для других достижимых маркировок, получающихся в результате запуска каждого из этих двух переходов. Начальной (корневой) является вершина, соответствующая начальной маркировке. Дуга, помеченная запускаемым переходом, приводит из начальной маркировки к каждой из новых маркировок (рисунок 2).

Рис.2. Первый шаг построения дерева достижимости

Это частичное дерево показывает все маркировки, непосредственно достижимые из начальной маркировки.

Теперь необходимо рассмотреть все маркировки, достижимые из новых маркировок. Из маркировки (1, 1, 0) можно снова запустить t₁ (получая 1, 2, 0) и t₂ (получая (0, 2, 1)); из (0, 1, 1) можно запустить t₃ (получая 0, 0, 1). Это порождает дерево, изображенное на рисунке 3.

Рис.3. Второй шаг построения дерева достижимости

Начиная с трех новых маркировок, необходимо повторить этот процесс, порождая новые маркировки, которые нужно ввести в дерево, как показано на рисунке 4.

Рис.4. Третий шаг построения дерева достижимости

Заметим, что маркировка (0, 0, 1) пассивная; никакой переход в ней не является разрешенным, поэтому никакие новые маркировки из этой пассивной маркировки в дереве порождаться не будут. Кроме того, необходимо отметить, что маркировка (0,1, 1), порождаемая запуском t₃ в (0, 2, 1) была уже порождена непосредственно из начальной маркировки запуском t₂.

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

Рис.5. Простая сеть Петри с бесконечным деревом достижимости

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

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

Приведение к конечному представлению осуществляется несколькими способами. Прежде всего, необходимо использовать те средства, которые ограничивают введение новых маркировок (называемых граничными вершинами) на каждом шаге. Для этого могут вводиться пассивные маркировки, то есть маркировки, в которых нет разрешенных переходов. Такие пассивные маркировки называются терминальными вершинами. Другой класс маркировок - это маркировки, ранее встречавшиеся в дереве. Такие маркировки называются дублирующими вершинами: никакие последующие маркировки можно не рассматривать - все они будут порождены из места первого появления дублирующей маркировки в дереве. Таким образом, в дереве на рисунке 5 маркировка (0, 1, 1), получившаяся в результате выполнения последовательности t₁, t₂, t₃, не будет порождать какие-либо новые вершины в дереве, поскольку она ранее встречалась в дереве в результате выполнения последовательности t₂ из начальной маркировки.

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

Алгоритм обычно начинается с определения начальной маркировки корнем дерева, т. е. граничной вершиной.

Пусть х - граничная вершина, которую необходимо обработать, тогда

1. если в дереве имеется другая вершина у, не являющаяся граничной, и с ней связана та же маркировка, m(х) = m(у), то вершина х - дублирующая;
2. если для маркировки m(х) ни один из переходов не разрешен, то х - терминальная вершина;
3. дуга, помеченная t_j, направлена от вершины х к вершине у. Вершина х переопределяется как внутренняя, вершинау - становится граничной.

Если все вершины дерева - терминальные, дублирующие или внутренние, то обработка данным алгоритмом останавливается.