Necessary and Sufficient Condition of Structural Liveness for General Petri Nets--Virtual Deadlock-Trap Properties--

Tadashi MATSUMOTO; Ken SAIKUSA; Kohkichi TSUJI

Necessary and Sufficient Condition of Structural Liveness for General Petri Nets--Virtual Deadlock-Trap Properties--

Tadashi MATSUMOTO, Ken SAIKUSA, Kohkichi TSUJI

Full Text Views

0

Cite this

Summary :

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 (SM). All the above subclasses are 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 N_T=(S_T, T_T, F_T, M_oT)) which is initially marked. However, the necessary and sufficient liveness conditions for EFCF, EBCF, EMGEFCFEBCF, AC (EFCFC), 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 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_DS_T, S_DS_T, S_DS_T (but N_D s.t. S_DS_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_DS_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 Ñ 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 for liveness of a new subclass N_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.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E78-A No.12 pp.1862-1874

Publication Date: 1995/12/25

Publicized

Online ISSN

DOI

Type of Manuscript: PAPER

Category: Concurrent Systems

Cite this

Copy

Tadashi MATSUMOTO, Ken SAIKUSA, Kohkichi TSUJI, "Necessary and Sufficient Condition of Structural Liveness for General Petri Nets--Virtual Deadlock-Trap Properties--" in IEICE TRANSACTIONS on Fundamentals, vol. E78-A, no. 12, pp. 1862-1874, December 1995, doi: .
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 (SM). All the above subclasses are 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 N_T=(S_T, T_T, F_T, M_oT)) which is initially marked. However, the necessary and sufficient liveness conditions for EFCF, EBCF, EMGEFCFEBCF, AC (EFCFC), 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 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_DS_T, S_DS_T, S_DS_T (but N_D s.t. S_DS_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_DS_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 Ñ 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 for liveness of a new subclass N_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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e78-a_12_1862/_p

Copy

@ARTICLE{e78-a_12_1862,
author={Tadashi MATSUMOTO, Ken SAIKUSA, Kohkichi TSUJI, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Necessary and Sufficient Condition of Structural Liveness for General Petri Nets--Virtual Deadlock-Trap Properties--},
year={1995},
volume={E78-A},
number={12},
pages={1862-1874},
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 (SM). All the above subclasses are 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 N_T=(S_T, T_T, F_T, M_oT)) which is initially marked. However, the necessary and sufficient liveness conditions for EFCF, EBCF, EMGEFCFEBCF, AC (EFCFC), 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 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_DS_T, S_DS_T, S_DS_T (but N_D s.t. S_DS_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_DS_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 Ñ 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 for liveness of a new subclass N_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={},
doi={},
ISSN={},
month={December},}

Copy

TY - JOUR
TI - Necessary and Sufficient Condition of Structural Liveness for General Petri Nets--Virtual Deadlock-Trap Properties--
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1862
EP - 1874
AU - Tadashi MATSUMOTO
AU - Ken SAIKUSA
AU - Kohkichi TSUJI
PY - 1995
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E78-A
IS - 12
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - December 1995
AB - 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 (SM). All the above subclasses are 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 N_T=(S_T, T_T, F_T, M_oT)) which is initially marked. However, the necessary and sufficient liveness conditions for EFCF, EBCF, EMGEFCFEBCF, AC (EFCFC), 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 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_DS_T, S_DS_T, S_DS_T (but N_D s.t. S_DS_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_DS_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 Ñ 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 for liveness of a new subclass N_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.
ER -