State Number Calculation Problem of Workflow Nets

被引：13

作者：

Bin Ahmadon, Mohd Anuaruddin ^{[1
]}

Yamaguchi, Shingo ^{[1
]}

机构：

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

来源：

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS | 2015年 / E98D卷 / 06期

关键词：

Petri net; state number calculation problem; process tree; solvability; computational complexity; model checking; PETRI NETS; VERIFICATION; SOUNDNESS;

D O I：

10.1587/transinf.2014FOP0009

中图分类号：

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

学科分类号：

0812 ;

摘要：

The number of states is a very important matter for model checking approach in Petri net's analysis. We first gave a formal definition of state number calculation problem: For a Petri net with an initial state (marking), how many states does it have? Next we showed the problem cannot be solved in polynomial time for a popular subclass of Petri nets, known as free choice workflow nets, if P not equal NP. Then we proposed a polynomial time algorithm to solve the problem by utilizing a representational bias called as process tree. We also showed effectiveness of the algorithm through an application example.

引用

页码：1128 / 1136

页数：9

共 20 条

[11]

Murata T., 1989, IEEE, V77, P541, DOI DOI 10.1109/5.24143

[12]

Ohta A, 2002, IEICE T FUND ELECTR, VE85A, P1071

[13]

Susaki T., 2013, P ITC CSCC 2013, P84

[14]

Tarjan R., 1971, Conference record 1971 12th annual symposium on switching and automata theory, P114, DOI 10.1137/0201010

[15]

van der Aalst W, 2012, LECT NOTES BUS INF P, V116, P39

[16]

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

[17]

van der Aalst WMP, 2002, WORKFLOW MANAGEMENT

[18]

van Hee K, 2003, LECT NOTES COMPUT SC, V2679, P337

[19] Polynomial Time Verification of Reachability in Sound Extended Free-Choice Workflow Nets [J].

Yamaguchi, Shingo .

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES, 2014, E97A (02) :468-475

[20]

Yamaguchi S, 2009, INFORMATION-TOKYO, V12, P163

← 1 2 →