Abstract | ||
---|---|---|
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. |
Year | DOI | Venue |
---|---|---|
2015 | 10.1587/transinf.2014FOP0009 | IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS |
Keywords | Field | DocType |
Petri net, state number calculation problem, process tree, solvability, computational complexity, model checking | Model checking,Petri net,Computer science,Theoretical computer science,Stochastic Petri net,Process architecture,Workflow nets,Computational complexity theory | Journal |
Volume | Issue | ISSN |
E98D | 6 | 1745-1361 |
Citations | PageRank | References |
3 | 0.54 | 6 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Mohd Anuaruddin Bin Ahmadon | 1 | 6 | 10.13 |
Yamaguchi, S. | 2 | 12 | 7.14 |