IEICE TRANSACTIONS on Fundamentals
Verifying Structurally Weakly Persistent Net Is Co-NP Complete
Summary :
Petri net is a powerful modeling tool for concurrent systems. Subclasses of Petri net are suggested to model certain realistic applications with less computational cost. Structurally weakly persistent net (SWPN) is one of such subclasses where liveness is verified in deterministic polynomial time. This paper studies the computational complexity to verify whether a give net is SWPN. 3UNSAT problem is reduced to the problem to verify whether a net is not SWPN. This implies co-NP completeness of verification problem of SWPN.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E94-A No.12 pp.2832-2835
- Publication Date
- 2011/12/01
- Publicized
- Online ISSN
- 1745-1337
- DOI
- 10.1587/transfun.E94.A.2832
- Type of Manuscript
- Special Section LETTER (Special Section on Mathematical Systems Science and its Applications)
- Category
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
Atsushi OHTA, Kohkichi TSUJI, "Verifying Structurally Weakly Persistent Net Is Co-NP Complete" in IEICE TRANSACTIONS on Fundamentals,
vol. E94-A, no. 12, pp. 2832-2835, December 2011, doi: 10.1587/transfun.E94.A.2832.
Abstract: Petri net is a powerful modeling tool for concurrent systems. Subclasses of Petri net are suggested to model certain realistic applications with less computational cost. Structurally weakly persistent net (SWPN) is one of such subclasses where liveness is verified in deterministic polynomial time. This paper studies the computational complexity to verify whether a give net is SWPN. 3UNSAT problem is reduced to the problem to verify whether a net is not SWPN. This implies co-NP completeness of verification problem of SWPN.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E94.A.2832/_p
Copy
@ARTICLE{e94-a_12_2832,
author={Atsushi OHTA, Kohkichi TSUJI, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Verifying Structurally Weakly Persistent Net Is Co-NP Complete},
year={2011},
volume={E94-A},
number={12},
pages={2832-2835},
abstract={Petri net is a powerful modeling tool for concurrent systems. Subclasses of Petri net are suggested to model certain realistic applications with less computational cost. Structurally weakly persistent net (SWPN) is one of such subclasses where liveness is verified in deterministic polynomial time. This paper studies the computational complexity to verify whether a give net is SWPN. 3UNSAT problem is reduced to the problem to verify whether a net is not SWPN. This implies co-NP completeness of verification problem of SWPN.},
keywords={},
doi={10.1587/transfun.E94.A.2832},
ISSN={1745-1337},
month={December},}
Copy
TY - JOUR
TI - Verifying Structurally Weakly Persistent Net Is Co-NP Complete
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 2832
EP - 2835
AU - Atsushi OHTA
AU - Kohkichi TSUJI
PY - 2011
DO - 10.1587/transfun.E94.A.2832
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E94-A
IS - 12
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - December 2011
AB - Petri net is a powerful modeling tool for concurrent systems. Subclasses of Petri net are suggested to model certain realistic applications with less computational cost. Structurally weakly persistent net (SWPN) is one of such subclasses where liveness is verified in deterministic polynomial time. This paper studies the computational complexity to verify whether a give net is SWPN. 3UNSAT problem is reduced to the problem to verify whether a net is not SWPN. This implies co-NP completeness of verification problem of SWPN.
ER -
English
