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
    Bin Ahmadon, Mohd Anuaruddin
    Yamaguchi, Shingo
    [J]. 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
    HOWELL, RR
    ROSIER, LE
    YEN, HC
    [J]. JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1993, 46 (01) : 1 - 26
12