Finding Minimal Siphons in General Petri Nets

Shinji TANIMOTO; Masahiro YAMAUCHI; Toshimasa WATANABE

Finding Minimal Siphons in General Petri Nets

Shinji TANIMOTO, Masahiro YAMAUCHI, Toshimasa WATANABE

Full Text Views

0

Share
Cite this

Summary :

A siphon (or alternatively a structutal deadlock) of a Petri net is defined as a set S of places such that existence of any edge from a transition t to a place of S implies that there is an edge from some place of S to t. A minimal siphon is a siphon such that any proper subset is not a siphon. The results of the paper are as follows. (1) The problem of deciding whether or not a given Petri net has a minimum siphon (i.e., a minimum-cardinality minimal siphon) is NP-complete. (2) A polynomial-time algorithm to find, if any, a minimal siphon or even a maximal calss of mutually disjoint minimal siphons of a general Petri net is proposed.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E79-A No.11 pp.1817-1824

Publication Date: 1996/11/25

Publicized

Online ISSN

DOI

Type of Manuscript: Special Section PAPER (Special Section on Description Models for Concurrent Systems and Their Applications)

Category

Cite this

Copy

Shinji TANIMOTO, Masahiro YAMAUCHI, Toshimasa WATANABE, "Finding Minimal Siphons in General Petri Nets" in IEICE TRANSACTIONS on Fundamentals, vol. E79-A, no. 11, pp. 1817-1824, November 1996, doi: .
Abstract: A siphon (or alternatively a structutal deadlock) of a Petri net is defined as a set S of places such that existence of any edge from a transition t to a place of S implies that there is an edge from some place of S to t. A minimal siphon is a siphon such that any proper subset is not a siphon. The results of the paper are as follows. (1) The problem of deciding whether or not a given Petri net has a minimum siphon (i.e., a minimum-cardinality minimal siphon) is NP-complete. (2) A polynomial-time algorithm to find, if any, a minimal siphon or even a maximal calss of mutually disjoint minimal siphons of a general Petri net is proposed.
URL: https://globals.ieice.org/en_transactions/fundamentals/10.1587/e79-a_11_1817/_p

Copy

@ARTICLE{e79-a_11_1817,
author={Shinji TANIMOTO, Masahiro YAMAUCHI, Toshimasa WATANABE, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Finding Minimal Siphons in General Petri Nets},
year={1996},
volume={E79-A},
number={11},
pages={1817-1824},
abstract={A siphon (or alternatively a structutal deadlock) of a Petri net is defined as a set S of places such that existence of any edge from a transition t to a place of S implies that there is an edge from some place of S to t. A minimal siphon is a siphon such that any proper subset is not a siphon. The results of the paper are as follows. (1) The problem of deciding whether or not a given Petri net has a minimum siphon (i.e., a minimum-cardinality minimal siphon) is NP-complete. (2) A polynomial-time algorithm to find, if any, a minimal siphon or even a maximal calss of mutually disjoint minimal siphons of a general Petri net is proposed.},
keywords={},
doi={},
ISSN={},
month={November},}

Copy

TY - JOUR
TI - Finding Minimal Siphons in General Petri Nets
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1817
EP - 1824
AU - Shinji TANIMOTO
AU - Masahiro YAMAUCHI
AU - Toshimasa WATANABE
PY - 1996
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E79-A
IS - 11
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - November 1996
AB - A siphon (or alternatively a structutal deadlock) of a Petri net is defined as a set S of places such that existence of any edge from a transition t to a place of S implies that there is an edge from some place of S to t. A minimal siphon is a siphon such that any proper subset is not a siphon. The results of the paper are as follows. (1) The problem of deciding whether or not a given Petri net has a minimum siphon (i.e., a minimum-cardinality minimal siphon) is NP-complete. (2) A polynomial-time algorithm to find, if any, a minimal siphon or even a maximal calss of mutually disjoint minimal siphons of a general Petri net is proposed.
ER -