On the Complexity of Deciding Soundness of Acyclic Workflow Nets

被引：6

作者：

Tiplea, Ferucio Laurentiu ^{[1
]}

Bocaneala, Corina ^{[2
]}

Chirosca, Raluca ^{[1
]}

机构：

[1] Alexandru Ioan Cuza Univ, Dept Comp Sci, Iasi 700506, Romania

[2] Dunarea de Jos Univ Galati, Dept Math & Comp Sci, Galati 800201, Romania

来源：

IEEE TRANSACTIONS ON SYSTEMS MAN CYBERNETICS-SYSTEMS | 2015年 / 45卷 / 09期

关键词：

Complexity; decidability; Petri net; soundness; workflow (WF) net; WF system; PETRI NETS;

D O I：

10.1109/TSMC.2015.2394735

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

This paper focuses on the complexity of the (weak) soundness problem of acyclic workflow (WF) nets, and two main results are established: 1) soundness of 1-bounded acyclic WF nets is co-NP-complete and 2) weak soundness of 3-bounded acyclic asymmetric-choice WF nets is co-NP-complete.

引用

页码：1292 / 1298

页数：7

共 29 条

[1]

[Anonymous], 2013, Introduction to the Theory of Computation

[2]

[Anonymous], 2003, GUIDE MODELING VERIF

[3] COMPLEXITY RESULTS FOR 1-SAFE NETS [J].