Verifying Structurally Weakly Persistent Net Is Co-NP Complete

Atsushi OHTA  Kohkichi TSUJI  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E94-A   No.12   pp.2832-2835
Publication Date: 2011/12/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E94.A.2832
Print ISSN: 0916-8508
Type of Manuscript: Special Section LETTER (Special Section on Mathematical Systems Science and its Applications)
concurrent system,  Petri net,  subclass,  computational complexity,  

Full Text: PDF(139.6KB)>>
Buy this Article

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.