Title :
On State Number Calculation Problem in Petri Nets
Author :
Bin Ahmadon, Mohd Anuaruddin ; Yamaguchi, Shingo
Author_Institution :
Grad. Sch. of Sci. & Eng., Yamaguchi Univ., Ube, Japan
Abstract :
The state number calculation problem is very important for model checking approach in Petri nets´ analysis. It is known that the problem is intractable for general Petri nets. In this paper, we showed that the problem is intractable for a popular subclass of Petri nets, called free choice workflow nets. Then we proposed a polynomial time algorithm to solve the problem for a subclass of free choice workflow nets. We also showed effectiveness of the algorithm through an application example.
Keywords :
Petri nets; computational complexity; Petri nets; free choice workflow nets; model checking approach; polynomial time algorithm; state number calculation problem; Algorithm design and analysis; Artificial neural networks; Computational complexity; Model checking; Nickel; Petri nets; Polynomials;
Conference_Titel :
Computing and Networking (CANDAR), 2014 Second International Symposium on
DOI :
10.1109/CANDAR.2014.114
