IEICE TRANSACTIONS on Fundamentals
NP-Hardness of Liveness Problem of Bounded Asymmetric Choice Net
Summary :
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.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E85-A No.5 pp.1071-1074
- Publication Date
- 2002/05/01
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- Special Section LETTER (Special Section on Discrete Mathematics and Its Applications)
- Category
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Atsushi OHTA, Kohkichi TSUJI, "NP-Hardness of Liveness Problem of Bounded Asymmetric Choice Net" in IEICE TRANSACTIONS on Fundamentals,
vol. E85-A, no. 5, pp. 1071-1074, May 2002, doi: .
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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e85-a_5_1071/_p
Copy
@ARTICLE{e85-a_5_1071,
author={Atsushi OHTA, Kohkichi TSUJI, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={NP-Hardness of Liveness Problem of Bounded Asymmetric Choice Net},
year={2002},
volume={E85-A},
number={5},
pages={1071-1074},
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.},
keywords={},
doi={},
ISSN={},
month={May},}
Copy
TY - JOUR
TI - NP-Hardness of Liveness Problem of Bounded Asymmetric Choice Net
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1071
EP - 1074
AU - Atsushi OHTA
AU - Kohkichi TSUJI
PY - 2002
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E85-A
IS - 5
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - May 2002
AB - 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.
ER -
English
