
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

State Number Calculation Problem of Workflow Nets
Mohd Anuaruddin BIN AHMADON Shingo YAMAGUCHI
Publication
IEICE TRANSACTIONS on Information and Systems
Vol.E98D
No.6
pp.11281136 Publication Date: 2015/06/01
Online ISSN: 17451361
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)>>
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 P≠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.

