The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
Cette lettre traite de la complexité informatique du réseau de choix asymétriques bornés (AC). Le réseau AC est une sous-classe du réseau de Petri qui inclut correctement la classe bien connue des réseaux de libre choix étendu. Il est montré que le problème de satisfiabilité des expressions booléennes est un temps polynomial réductible au problème de vivacité des réseaux AC bornés. Cela implique que le problème est NP-difficile.
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.
Copier
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
Copier
@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},}
Copier
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 -