The Algorithms For Computing Repetitive Vectors And Siphons Of Petri Nets

Repetitive vector and siphon are both important concepts of Petri nets. They play important roles in studying the liveness and fairness of Petri nets. Computing repetitive vector and siphon therefore becomes a key step. In this paper, the relations among T-invariants, repetitive vectors and siphons are investigated based on changing the structure of a net, and some new algorithms for computing repetitive vector and siphon are suggested.The transition-extended net of a net is defined and a relation is shown that there always exists a T-invariant of the transition-extended net corresponding to a repetitive vector of the original net, and vice versa. So computing repetitive vector can be converted into computing T-invariant of its transition-extended net. An algorithm that can compute a set of repetitive vectors of a net is presented. It is also proved that any repetitive vector of the net can be expressed as a linear combination of these repetitive vectors with nonnegative rational coefficients.Next, this paper presents a new method for generating siphon based on repetitive vector. The transition-split net of a net is defined. Siphons of a net are proved the same as ones of its transition-split net. Any siphon of the transition-split net is exactly the support of a repetitive vector of its dual net, and vice versa. Therefore, computing siphon can be converted into computing repetitive vector. Finally this work presents an algorithm that can generate a set of siphons of a net. These siphons contain all minimal siphons and any siphon of the net can be expressed as a union of them.It seems that all algorithms are based on changing the structure of a net. However, they can be carried out by transformation of the incidence matrix. And they are all concise and easy to be understood by readers and performed by computers.