Алгоритм построения дерева

Каждая вершина i дерева связывается с расширенной маркировкой M(i). В этой маркировке число меток в позиции может быть либо неотрицательным целым, либо w. Каждая вершина классифицируется как граничная или терминальная или дублирующая или внутренняя.

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

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

Пусть х – граничная вершина.

1. Если в дереве имеется другая вершина у, не являющаяся граничной, и с ней связана также маркировка М(х)=М(у), то вершина х – дублирующая.

2. Если для маркировки М(х) ни один из переходов не разрешен для всех t_jÎT, то х – терминальная вершина.

3. Для всякого перехода t_jÎT, разрешенного в М(х), создать новую вершину z дерева. Маркировка М(z) определяется для каждой позиции P_i следующим образом:

а) если М(х)i=w, то М(z)_i=w.

б) если на пути от корневой вершины к х существует вершина у с М(у)<d(M(x), t_j) и М(у)_i<d(M(x), t_j)_i, то М(z)_i=w, d - функция следующего состояния.

в) в противном случае М(z)_i=d(M(x), t_j)_i,

Функция d(M(x), t_j) не определена, если t_j не разрешен в маркировке М(х). Если t_j разрешен, то d(M(x), t_j)=M’(x), где M’(x) – маркировка, полученная после срабатывания t_j. Дуга, помеченная t_j, направлена от вершины х к вершине z. Вершина х переопределяется как внутренняя, вершина z становится граничной.

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

Для нашего примера дерево достижимости имеет вид:

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

Ниже приведем еще один пример сети Петри и дерево достижимости для него.