NP-Hardness of Liveness Problem of Bounded Asymmetric Choice Net(Special Section on Discrete Mathematics and Its Applications)
スポンサーリンク
概要
- 論文の詳細を見る
This letter treats computational complexity of bounded asymmetric choice (AC) net. AC net is a subclass of Petri net that properly includes the class of well-known extended free choice net. It is shown that satisfiability problem of Boolean expressions is polynomial time reducible to liveness problem of bounded AC nets. This implies that the problem is NP-hard.
- 社団法人電子情報通信学会の論文
- 2002-05-01
著者
-
Tsuji Kohkichi
The Authors Are With The Faculty Of Information Science And Technology Aichi Prefectural University
-
OHTA Atsushi
The authors are with the Faculty of Information Science and Technology, Aichi Prefectural University
-
Ohta Atsushi
The Author Is With The Faculty Of Information Science And Technology Aichi Prefectural University
-
Ohta Atsushi
The Authors Are With The Faculty Of Information Science And Technology Aichi Prefectural University
関連論文
- NP-Hardness of Liveness Problem of Bounded Asymmetric Choice Net(Special Section on Discrete Mathematics and Its Applications)
- An Algebraic Criterion for State Machine Allocatable Nets(Special Section on Concurrent Systems Technology)