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

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

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

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

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

• Если в дереве имеется другая вершина у, не являющаяся граничной, и с ней связана также маркировка М(х)=М(у), то вершина х – дублирующая.
• Если для маркировки М(х) ни один из переходов не разрешен для всех , то х – терминальная вершина.
• Для всякого перехода , разрешенного в М(х), создать новую вершину z дерева. Маркировка М(z) определяется для каждой позиции Pi следующим образом:

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

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

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

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