Cети Петри. Структура СП. Гибкий производственный модуль. Алгоритм преобразования в ординарную СП, страница 5

- является ограниченной и строго сохраняющейся,

- имеет конечный граф достижимых маркировок R(C,m₀) в силу ограниченности СП,

- является безопасной в том случае, когда m₀ имеет только один маркер в любой позиции.

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

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

Динамические свойства маркированного графа(синхрографа)

Простой путь -это последовательность переходов t_j1,t_j2,...,t_js такая, что для каждой пары переходов t_jk¹t_jk+1 существует позиция p_ikÎO(t_jk) и p_ikÎI(t_jk+1).

Цикл - простой путь, для которого t_j1=t_jn.

Пустой цикл - это цикл, не содержащий ни одного маркера при заданной маркировке m.

t₂       p₃          t₄

    

p₁              p₂    p₅                  p₆

t₁        p₄             t₃

 

(t₃,t₄) - простой цикл,

(t₂,t₄,t₃,t₁) - пустой цикл.

Данная СП не является живой, т.к. есть пустой цикл.

Маркированный граф является живой СП, если:

- любой цикл - не пуст при начальной маркировке m₀,

- при функционировании маркированного графа число маркеров, содержащихся в любом его цикле, остается постоянным,

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

p₁                              p₁

  

    

       t₁        p₂      t₂           t₁          p₂      t₂     

 

 

             p₃                               p₃

 

p₄

                 p₅                        t₃           p₄      t₄

       t₃                 t₄

 

p₆                             p₅

 Пример живого синхрографа        Пример живого, но

                                   неограниченного синхрографа

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

  Методы анализа СП на основе построения покрывающего дерева

Покрывающее дерево - это ориентированное корневое дерево, вершинам которого соответствует достижимое из m₀ маркировки m₁,m₂,m₃..., а дугами являются разрешенные переходы t_i, определяющие отношение непосредственного следования:

m_a [t_i > m_b, где m_a,m_b - начало и конец дуги, помеченной символом t_i.

Для ограниченных СП покрывающее дерево - есть граф R(C,m₀).

Введем w для обозначения ¥-маркировки. Пусть w удовлетворяет следующим требованиям:

1). nÎN, w>n.

2). n+w = w+n = w+w = w-n = w-w = w.

3). w*n = n*w = w.

4). w*0 = 0*w =0.

Расширенная маркировка - это маркировка, в которой компоненты вектора m могут быть натуральными числами или w. Корневая вершина - вершина покрывающего дерева, соответствующая начальной маркировке m₀. Граничная вершина - вершинапокрывающего дерева, не обработанной алгоритмом. Дублирующая вершина - вершина покрывающего дерева, которая соответствует маркировке m, уже ранее встречающейся. Терминальная вершина - это вершина покрывающего дерева, которая соответствует тупиковой маркировке. Внутренняя вершина - это вершина покрывающего дерева, обработанной алгоритмом и не являющейся терминальной или дублирующейся.

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

1.Корневая вершина дерева: положим х(граничная вершина).

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

3.Если m(х) - тупиковая маркировка, то соответствующая ей вершина - терминальная.

4.Если существует вершина y ¹ x с m(y) такой, что m(y)=m(х), то вершина х - дублирующая.

5.Если х - внутренняя вершина, то для каждого разрешенного в m(х) перехода t_i имеется вершина z, которая соединяется дугой от х к z и помечается соответствующим символом t_i.

6.Вершине z соответствует маркировка  m(z), компоненты которой определяются следующим образом:

а). если  m_i(х) = w, то  m_i(z) = w.

b). если существует вершина y с m(y) такой, что: