IEICE TRANSACTIONS on Information
Petri Nets with Simple Circuits
Summary :
We study the complexity of the reachability problem for a new subclass of Petri nets called simple-circuit Petri nets, which properly contains several well known subclasses such as conflict-free, BPP, normal Petri nets and more. A new decomposition approach is applied to developing an integer linear programming formulation for characterizing the reachability sets of such Petri nets. Consequently, the reachability problem is shown to be NP-complete. The model checking problem for some temporal logics is also investigated for simple-circuit Petri nets.
- Publication
- IEICE TRANSACTIONS on Information Vol.E88-D No.9 pp.2113-2125
- Publication Date
- 2005/09/01
- Publicized
- Online ISSN
- DOI
- 10.1093/ietisy/e88-d.9.2113
- Type of Manuscript
- PAPER
- Category
- Fundamentals of Software and Theory of Programs
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Hsu-Chun YEN, Lien-Po YU, "Petri Nets with Simple Circuits" in IEICE TRANSACTIONS on Information,
vol. E88-D, no. 9, pp. 2113-2125, September 2005, doi: 10.1093/ietisy/e88-d.9.2113.
Abstract: We study the complexity of the reachability problem for a new subclass of Petri nets called simple-circuit Petri nets, which properly contains several well known subclasses such as conflict-free, BPP, normal Petri nets and more. A new decomposition approach is applied to developing an integer linear programming formulation for characterizing the reachability sets of such Petri nets. Consequently, the reachability problem is shown to be NP-complete. The model checking problem for some temporal logics is also investigated for simple-circuit Petri nets.
URL: https://global.ieice.org/en_transactions/information/10.1093/ietisy/e88-d.9.2113/_p
Copy
@ARTICLE{e88-d_9_2113,
author={Hsu-Chun YEN, Lien-Po YU, },
journal={IEICE TRANSACTIONS on Information},
title={Petri Nets with Simple Circuits},
year={2005},
volume={E88-D},
number={9},
pages={2113-2125},
abstract={We study the complexity of the reachability problem for a new subclass of Petri nets called simple-circuit Petri nets, which properly contains several well known subclasses such as conflict-free, BPP, normal Petri nets and more. A new decomposition approach is applied to developing an integer linear programming formulation for characterizing the reachability sets of such Petri nets. Consequently, the reachability problem is shown to be NP-complete. The model checking problem for some temporal logics is also investigated for simple-circuit Petri nets.},
keywords={},
doi={10.1093/ietisy/e88-d.9.2113},
ISSN={},
month={September},}
Copy
TY - JOUR
TI - Petri Nets with Simple Circuits
T2 - IEICE TRANSACTIONS on Information
SP - 2113
EP - 2125
AU - Hsu-Chun YEN
AU - Lien-Po YU
PY - 2005
DO - 10.1093/ietisy/e88-d.9.2113
JO - IEICE TRANSACTIONS on Information
SN -
VL - E88-D
IS - 9
JA - IEICE TRANSACTIONS on Information
Y1 - September 2005
AB - We study the complexity of the reachability problem for a new subclass of Petri nets called simple-circuit Petri nets, which properly contains several well known subclasses such as conflict-free, BPP, normal Petri nets and more. A new decomposition approach is applied to developing an integer linear programming formulation for characterizing the reachability sets of such Petri nets. Consequently, the reachability problem is shown to be NP-complete. The model checking problem for some temporal logics is also investigated for simple-circuit Petri nets.
ER -
English
