Verifying Structurally Weakly Persistent Net Is Co-NP Complete
スポンサーリンク
概要
- 論文の詳細を見る
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.
- 2011-12-01
著者
-
OHTA Atsushi
Faculty of Engineering, Kansai University
-
Tsuji Kohkichi
Faculty Of Engineering Fukui University
-
Tsuji Kohkichi
Faculty Of Information Science And Technology Aichi Prefectural University
関連論文
- Optical Resolution by Preferential Crystallization of(RS)-α-Amino-γ-butyrolactone Hydrochloride
- On Liveness of Extended Partially Ordered Condition Nets (Special Section on Concurrent Systems Technology)
- Necessary and Sufficient Condition of Structural Liveness for General Petri Nets : Virtual Deadlock-Trap Properties
- A Method to Validate the Correctness of Test Logic Programs Applied in a Protocol Conformance Test System Using Petri Nets (Special Section on Net Theory and Its Applications)
- Computational Complexity of Liveness Problem of Normal Petri Net
- On Liveness of Time POC Nets with the Static Fair Condition
- Special Section on Selected Papers from the 16th Workshop on Circuits and Systems in Karuizawa
- An Equivalence Net-Condition between Place-Liveness and Transition-Liveness of Petri Nets and Their Initial-Marking-Based Necessary and Sufficient Liveness Conditions
- Verifying Structurally Weakly Persistent Net Is Co-NP Complete
- Special Section on Concurrent/Hybrid Systems : Theory and Applications
- Facile Production of D-Histidine by Asymmetric Transformation of L-Histidine.