For the most recent entries see the Petri Nets Newsletter.

Necessary and sufficient conditions of structural liveness for general Petri nets - virtual deadlock-trap properties.

Matsumoto, T.; Saikusa, K.; Tsuji, K.

In: IEICE Trans. on Fundamentals of Electronics, Communications and Computer Science, Vol. E78-A, No. 12, pages 1862-1874. 1996.

Abstract: Up to now, the only useful and well-known structural or initial-marking-based necessary and sufficient liveness conditions of Petri nets have only been those of an extended free-choice (EFC) net and its subclasses such as a free-choice (FC) net, a forward conflict free (FCF) net, a marked graph (MG), and a state machine (ISM). all the above subclasses tire activated only by deadlock-trap properties (i.e., real d-t properties in this paper), which mean that every minimal structural deadlock (MSDL N-D = (S-D,T-D,F-D,M(oD))) in a net contains at least one Live minimal structural trap (MSTR NT = (S-T,T-T,M(oT),MoT)) which is initially marked. However, the necessary and sufficient liveness conditions for EFCF, EBCF, EMG subset of EFCF subset of EBCF, AC (superset of EFC superset of FC), and the net with kindling traps N-KT have recently been determined, in which each MSDL without real d-t properties was also activated by a new type of trap, i.e., behavioral traps (BTRs), which are defined by introducing a virtual MSTR, a virtual maximal structural trap (virtual STR), a virtual MSDL, and a virtual maximal structural deadlock (virtual SDL) into a target MSDL. In this paper, a structural or initial-marking-based necessary and sufficient condition For local liveness (i.e., virtual deadlock-trap properties) of each MSDL N-D s.t. S-D subset of or equal to S-T, S-D (sic) S-T, S-D superset of or equal to S-T (but N-D s.t. S-D superset of or equal to S-T is dead owing to real deadlock-trap properties) in a general Petri net N is presented by extending that in N-KT. Specifically, live minimal behavioral traps (MBTRs) as well as live maximal behavioral traps (BTRs), i.e., virtual deadlock-trap properties, in a general Petri net N are characterized using the real d-t properties of each MSDL N-D s.t. S-D superset of or equal to S-T for a general Petri net N, which were also obtained by extending the concept of return paths in N-KT in connection with an MSDL which contains at least one MSTR and by using the concepts of T-cornucopias and absolute T-cornucopias in a subclass N of N. In other words, BTRs are defined by introducing a virtual MSTR, a virtual STR, a virtual MSDL, and a virtual SDL into a target MSDL without real d-t properties. Additionally, a structural or initial-marking-based necessary and sufficient condition far liveness of a new subclass N, of a general Petri net N (i.e., a general Petri net without time) is derived, and the usefulness of the obtained results is also discussed.

Keywords: Petri nets, behavioral traps, structural liveness, virtual deadlock-trap.


Do you need a refined search? Try our search engine which allows complex field-based queries.

Back to the Petri Nets Bibliography