La fonctionnalité de recherche est en construction.
La fonctionnalité de recherche est en construction.

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

NP-Hardness of Liveness Problem of Bounded Asymmetric Choice Net NP-Dureté de la vivacité Problème du réseau de choix asymétrique borné

Atsushi OHTA, Kohkichi TSUJI

  • Vues en texte intégral

    2

  • Citer

Résumé:

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.

Publication
IEICE TRANSACTIONS on Fundamentals Vol.E85-A No.5 pp.1071-1074
Date de publication
2002/05/01
Publicisé
ISSN en ligne
DOI
Type de manuscrit
Special Section LETTER (Special Section on Discrete Mathematics and Its Applications)
Catégories

Auteurs

Mots-clés

Table des matières