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 条

[1] Convertibility and Conversion Algorithm of Well-Structured Workflow Net to Process Tree [J].

Bin Ahmadon, Mohd Anuaruddin ;

Yamaguchi, Shingo .

2013 FIRST INTERNATIONAL SYMPOSIUM ON COMPUTING AND NETWORKING (CANDAR), 2013, :122-127

[2]

Chao DY, 2011, IEEE IND ELEC, P3788

[3]

Cormen T. H., 2001, INTRO ALGORITHMS, P998

[4]

Desel J., 1995, FREE CHOICE PETRI NE

[5]

Dohi S., 2014, MSS201394 IEICE

[6]

El Hichami O., 2014, J THEORETICAL APPL I, V61, P486

[7]

Janicki R., 1994, Journal of Information Processing and Cybernetics, V30, P143

[8]

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

[9]

Holzmann Gerard J., 2004, The SPIN Model Checker-Primer and Reference Manual

[10] NORMAL AND SINKLESS PETRI NETS [J].

HOWELL, RR ;

ROSIER, LE ;

YEN, HC .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1993, 46 (01) :1-26

← 1 2 →