For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Verifying Structurally Weakly Persistent Net Is Co-NP Complete
Atsushi OHTA Kohkichi TSUJI
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2011/12/01
Online ISSN: 1745-1337
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)>>
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.