JISE


  [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18]


Journal of Information Science and Engineering, Vol. 25 No. 1, pp. 121-136


Incidence Matrix Based Methods for Computing Repetitive Vectors and Siphons of Petri Net


Guan-Jun Liu and Chang-Jun Jiang 
Department of Computer Science and Engineering 
Tongji University 
Shanghai 201804, P.R. China


    In this paper, the relations among T-invariants, repetitive vectors and siphons are investigated and new methods for computing repetitive vectors and siphons are suggested based on them. The transition-added net of a net is defined and a relation is shown that there always exists a T-invariant of the transition-added net corresponding to a repetitive vector of the original net, and vice versa. Based on this relation, an algorithm that can compute a set of repetitive vectors of a net is presented. It is proved that any repetitive vector of a 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 siphons based on repetitive vectors. The transition-split net of a net is defined. It can be proved that all siphons of a net are siphons of the associated transition-split net, and vice versa. Any siphon of the transition-split net is exactly the support of a repetitive vector of its dual net, and vice versa. Therefore, computing siphons can be converted into computing repetitive vectors. Finally this paper 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. These algorithms, which like FM algorithm computing T-invariants, can be carried out through the linear transformation of the incidence matrix.


Keywords: Petri net, repetitive vector, siphon, T-invariant, trap, incidence matrix, FM algorithm, dual net

  Retrieve PDF document (JISE_200901_07.pdf)