State Number Calculation Problem of Workflow Nets

Mohd Anuaruddin BIN AHMADON  Shingo YAMAGUCHI  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E98-D   No.6   pp.1128-1136
Publication Date: 2015/06/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.2014FOP0009
Type of Manuscript: Special Section PAPER (Special Section on Formal Approach)
Category: Petri net
Keyword: 
Petri net,  state number calculation problem,  process tree,  solvability,  computational complexity,  model checking,  

Full Text: PDF(1.1MB)>>
Buy this Article




Summary: 
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 PNP. 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.