Minimum Number of Live Minimal Structural Traps to Make a Minimal Deadlock Locally Live in General Petri Nets

Tadashi MATSUMOTO; Ken SAIKUSA

Minimum Number of Live Minimal Structural Traps to Make a Minimal Deadlock Locally Live in General Petri Nets

Tadashi MATSUMOTO, Ken SAIKUSA

Full Text Views

0

Cite this

Summary :

Petri nets are one of useful models for discrete event systems in which liveness problem as well as reachability problem is one of big issues. But, it has not been completely solved from the point of view of useful initial-marking-based liveness conditions in general Petri nets. In this paper, to guarantee local liveness (i. e. , liveness underM_oD) for each minimal deadlock (MSDL),N_D=(S_D,T_D,F_D,M_oD), with real deadlock-trap structure, it is shown that the minimum number of required live minimal structural traps (MSTRs),N_T=(S_T,T_T,F_T,M_oT) s. t. S_D S_T, is conditionally (which means that the conditions of Lemma 4-9 are fulfilled for a bounded MSDL N_D containing at least one MSTR N_T s. t. S_D S_T and see also Remarks 4-2 (3) in Sect. 4. 3) "one. " Note that this local liveness for N_D s. t. S_D S_T is one of useful necessary conditions for liveness condition of general Petri nets N=(S,T,F,M_o) s. t. S S_D. However, because this has not been discussed in literature and is not trivial, some new concepts such as T-cornucopias and return paths are introduced into the real deadlock-trap structure s. t. S_D S_T in N and this is proven by dividing it into two cases: N_D s. t. S_D S_T is live and unbounded under M_oD and N_D s. t. S_D S_T is live and bounded under M_oD. Usefulness for the results obtained is also discussed.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E81-A No.1 pp.164-174

Publication Date: 1998/01/25

Publicized

Online ISSN

DOI

Type of Manuscript

Category: Concurrent Systems

Cite this

Copy

Tadashi MATSUMOTO, Ken SAIKUSA, "Minimum Number of Live Minimal Structural Traps to Make a Minimal Deadlock Locally Live in General Petri Nets" in IEICE TRANSACTIONS on Fundamentals, vol. E81-A, no. 1, pp. 164-174, January 1998, doi: .
Abstract: Petri nets are one of useful models for discrete event systems in which liveness problem as well as reachability problem is one of big issues. But, it has not been completely solved from the point of view of useful initial-marking-based liveness conditions in general Petri nets. In this paper, to guarantee local liveness (i. e. , liveness underM_oD) for each minimal deadlock (MSDL),N_D=(S_D,T_D,F_D,M_oD), with real deadlock-trap structure, it is shown that the minimum number of required live minimal structural traps (MSTRs),N_T=(S_T,T_T,F_T,M_oT) s. t. S_D S_T, is conditionally (which means that the conditions of Lemma 4-9 are fulfilled for a bounded MSDL N_D containing at least one MSTR N_T s. t. S_D S_T and see also Remarks 4-2 (3) in Sect. 4. 3) "one. " Note that this local liveness for N_D s. t. S_D S_T is one of useful necessary conditions for liveness condition of general Petri nets N=(S,T,F,M_o) s. t. S S_D. However, because this has not been discussed in literature and is not trivial, some new concepts such as T-cornucopias and return paths are introduced into the real deadlock-trap structure s. t. S_D S_T in N and this is proven by dividing it into two cases: N_D s. t. S_D S_T is live and unbounded under M_oD and N_D s. t. S_D S_T is live and bounded under M_oD. Usefulness for the results obtained is also discussed.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e81-a_1_164/_p

Copy

@ARTICLE{e81-a_1_164,
author={Tadashi MATSUMOTO, Ken SAIKUSA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Minimum Number of Live Minimal Structural Traps to Make a Minimal Deadlock Locally Live in General Petri Nets},
year={1998},
volume={E81-A},
number={1},
pages={164-174},
abstract={Petri nets are one of useful models for discrete event systems in which liveness problem as well as reachability problem is one of big issues. But, it has not been completely solved from the point of view of useful initial-marking-based liveness conditions in general Petri nets. In this paper, to guarantee local liveness (i. e. , liveness underM_oD) for each minimal deadlock (MSDL),N_D=(S_D,T_D,F_D,M_oD), with real deadlock-trap structure, it is shown that the minimum number of required live minimal structural traps (MSTRs),N_T=(S_T,T_T,F_T,M_oT) s. t. S_D S_T, is conditionally (which means that the conditions of Lemma 4-9 are fulfilled for a bounded MSDL N_D containing at least one MSTR N_T s. t. S_D S_T and see also Remarks 4-2 (3) in Sect. 4. 3) "one. " Note that this local liveness for N_D s. t. S_D S_T is one of useful necessary conditions for liveness condition of general Petri nets N=(S,T,F,M_o) s. t. S S_D. However, because this has not been discussed in literature and is not trivial, some new concepts such as T-cornucopias and return paths are introduced into the real deadlock-trap structure s. t. S_D S_T in N and this is proven by dividing it into two cases: N_D s. t. S_D S_T is live and unbounded under M_oD and N_D s. t. S_D S_T is live and bounded under M_oD. Usefulness for the results obtained is also discussed.},
keywords={},
doi={},
ISSN={},
month={January},}

Copy

TY - JOUR
TI - Minimum Number of Live Minimal Structural Traps to Make a Minimal Deadlock Locally Live in General Petri Nets
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 164
EP - 174
AU - Tadashi MATSUMOTO
AU - Ken SAIKUSA
PY - 1998
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E81-A
IS - 1
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - January 1998
AB - Petri nets are one of useful models for discrete event systems in which liveness problem as well as reachability problem is one of big issues. But, it has not been completely solved from the point of view of useful initial-marking-based liveness conditions in general Petri nets. In this paper, to guarantee local liveness (i. e. , liveness underM_oD) for each minimal deadlock (MSDL),N_D=(S_D,T_D,F_D,M_oD), with real deadlock-trap structure, it is shown that the minimum number of required live minimal structural traps (MSTRs),N_T=(S_T,T_T,F_T,M_oT) s. t. S_D S_T, is conditionally (which means that the conditions of Lemma 4-9 are fulfilled for a bounded MSDL N_D containing at least one MSTR N_T s. t. S_D S_T and see also Remarks 4-2 (3) in Sect. 4. 3) "one. " Note that this local liveness for N_D s. t. S_D S_T is one of useful necessary conditions for liveness condition of general Petri nets N=(S,T,F,M_o) s. t. S S_D. However, because this has not been discussed in literature and is not trivial, some new concepts such as T-cornucopias and return paths are introduced into the real deadlock-trap structure s. t. S_D S_T in N and this is proven by dividing it into two cases: N_D s. t. S_D S_T is live and unbounded under M_oD and N_D s. t. S_D S_T is live and bounded under M_oD. Usefulness for the results obtained is also discussed.
ER -