¡@

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 (200901_07.pdf)

Received April 3, 2007; revised December 11, 2007; accepted January 17, 2008.
Communicated by Jonathan Lee.
^* This paper was partially supported by the National Natural Science Foundation of P.R. China under grant No. 60534060 and by the National Basic Research Program of P.R. China (973 Program) under grants No. 2003 CB316902 and No. 2004CB318001-03.