On Reachability in Acyclic Well-Structured Workflow Nets

被引：3

作者：

Yamaguchi, Shingo ^{[1
]}

机构：

[1] Yamaguchi Univ, Grad Sch Sci & Engn, Ube, Yamaguchi 7558611, Japan

来源：

2012 THIRD INTERNATIONAL CONFERENCE ON NETWORKING AND COMPUTING (ICNC 2012) | 2012年

关键词：

PETRI NETS; TIME;

D O I：

10.1109/ICNC.2012.83

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

Workflow net is a particular class of Petri net for verifying the correctness of workflows. Reachability problem for workflow nets plays an important role in the verification, but the problem is known to be intractable. Limiting our analysis to a subclass of workflow net, called acyclic well-structured workflow net, we gave a necessary and sufficient condition on the reachability problem. Based on this condition, we also constructed a polynomial time procedure for solving the problem.

引用

页码：441 / 446

页数：6

共 15 条

[1]

Desel J., 1995, FREE CHOICE PETRINET

[2]

Ellis C., 1995, P C ORG COMP SYST CO, V95, P10

[3] Reachability in live and safe free-choice Petri nets is NP-complete [J].

Esparza, J .

THEORETICAL COMPUTER SCIENCE, 1998, 198 (1-2) :211-224

[4]

Esparza J., 1990, LECT NOTES COMPUTER, V483, P210

[5] PETRI NETS - PROPERTIES, ANALYSIS AND APPLICATIONS [J].

MURATA, T .

PROCEEDINGS OF THE IEEE, 1989, 77 (04) :541-580

[6]

Ohta A., 2002, SICE S SYST INF, P489

[7] Managing change and time in dynamic workflow processes [J].

Sadiq, SW ;

Marjanovic, O ;

Orlowska, ME .

INTERNATIONAL JOURNAL OF COOPERATIVE INFORMATION SYSTEMS, 2000, 9 (1-2) :93-116

[8]

van der Aalst W.M.P., 2002, Workflow management: models, methods, and systems

[9]

van der Aalst WMP, 1997, LECT NOTES COMPUT SC, V1248, P407

[10] The application of Petri nets to workflow management [J].

Van der Aalst, WMP .

JOURNAL OF CIRCUITS SYSTEMS AND COMPUTERS, 1998, 8 (01) :21-66

← 1 2 →