NP-Hardness of Liveness Problem of Bounded Asymmetric Choice Net

Atsushi OHTA  Kohkichi TSUJI  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E85-A   No.5   pp.1071-1074
Publication Date: 2002/05/01
Online ISSN: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section LETTER (Special Section on Discrete Mathematics and Its Applications)
concurrent system,  Petri net,  liveness,  computational complexity,  

Full Text: PDF(263.3KB)>>
Buy this Article

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.