Paper Info
Title
Verifying Structurally Weakly Persistent Net Is Co-Np Complete
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.
Year
DOI
Venue
2011
10.1587/transfun.E94.A.2832
IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES
Keywords
Field
DocType
concurrent system, Petri net, subclass, computational complexity
Discrete mathematics,Petri net,co-NP-complete,Theoretical computer science,Stochastic Petri net,Time complexity,Completeness (statistics),Mathematics,Liveness,Computational complexity theory
Journal
Volume
Issue
ISSN
E94A
12
0916-8508
Citations 
PageRank 
References 
0
0.34
6
Authors
2
Name
Order
Citations
PageRank
atsushi ohta16615.31
Kohkichi Tsuji232.44