For Full-Text 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
IEICE TRANSACTIONS on Information and Systems
Publication Date: 2015/06/01
Online ISSN: 1745-1361
Type of Manuscript: Special Section PAPER (Special Section on Formal Approach)
Category: Petri net
Petri net, state number calculation problem, process tree, solvability, computational complexity, model checking,
Full Text: PDF(1.1MB)>>
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.