Verifying Structurally Weakly Persistent Net Is Co-NP Complete

Atsushi OHTA; Kohkichi TSUJI

doi:10.1587/transfun.E94.A.2832

Verifying Structurally Weakly Persistent Net Is Co-NP Complete

Atsushi OHTA, Kohkichi TSUJI

Full Text Views

0

Share
Cite this

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

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://globals.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 -