Abstract | ||
---|---|---|
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. |
Year | Venue | Keywords |
---|---|---|
2002 | IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES | concurrent system, Petri net, liveness, computational complexity |
DocType | Volume | Issue |
Journal | E85A | 5 |
ISSN | Citations | PageRank |
0916-8508 | 6 | 0.58 |
References | Authors | |
0 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
atsushi ohta | 1 | 66 | 15.31 |
Kohkichi Tsuji | 2 | 6 | 0.58 |