Complexity of the Soundness Problem of Workflow Nets

被引：13

作者：

Liu, GuanJun ^{[1
]}

Sun, Jun ^{[2
]}

Liu, Yang ^{[3
]}

Dong, JinSong ^{[4
]}

机构：

[1] Tongji Univ, Dept Comp Sci & Technol, Shanghai 201804, Peoples R China

[2] Singapore Univ Technol & Design, ISTD, Singapore 138682, Singapore

[3] Nanyang Technol Univ, Sch Comp Engn, Singapore 639798, Singapore

[4] Natl Univ Singapore, Sch Comp, Singapore 117417, Singapore

来源：

FUNDAMENTA INFORMATICAE | 2014年 / 131卷 / 01期

基金：

中国国家自然科学基金;

关键词：

Workflow Nets; Soundness; Complexity; PSPACE-hardness; co-NP-hardness;

D O I：

10.3233/FI-2014-1005

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

Classical workflow nets (WF-nets for short) are an important subclass of Petri nets that are widely used to model and analyze workflow systems. Soundness is a crucial property of workflow systems and guarantees that these systems are deadlock-free and bounded. Aalst et al. proved that the soundness problem is decidable for WF-nets and can be polynomially solvable for free-choice WF-nets. This paper proves that the soundness problem is PSPACE-hard for WF-nets. Furthermore, it is proven that the soundness problemis PSPACE-complete for boundedWF-nets. Based on the above conclusion, it is derived that the soundness problem is also PSPACE-complete for bounded WF-nets with reset or inhibitor arcs (ReWF-nets and InWF-nets for short, resp.). ReWF- and InWF-nets are two extensions to WF-nets and their soundness problems were proven by Aalst et al. to be undecidable. Additionally, we prove that the soundness problem is co-NP-hard for asymmetric-choice WF-nets that are a larger class and can model more cases of interaction and resource allocation than free-choice ones.

引用

页码：81 / 101

页数：21

共 27 条

[1]

Barkaoui K, 2007, International Journal of Computing and Information Sciences (IJCIS), V5, P51

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

CHENG, A ;

ESPARZA, J ;

PALSBERG, J .

THEORETICAL COMPUTER SCIENCE, 1995, 147 (1-2) :117-136

[3] Deadlock analysis of Petri nets using siphons and mathematical programming [J].

Chu, F ;

Xie, XL .

IEEE TRANSACTIONS ON ROBOTICS AND AUTOMATION, 1997, 13 (06) :793-804

[4]

DESEL J, 1995, FREE CHOICE PETRI NE

[5]

Dufourd C., 1998, LNCS, V1433

[6]

Dufourd C., 1999, LNCS, V1644

[7]

Garey M. R., 1976, COMPUTER INTRACTABIL

[8]

Hack M., 1976, 159 MIT CAMBRIDGE

[9]

Jones N., 1977, THEORETICAL COMPUTER, V4, P277

[10]

Kang M.H., 2001, P 6 ACM S ACC CONTR

← 1 2 3 →