An algorithm for legal firing sequence problem of Petri nets based on partial order method
The legal firing sequence problem of Petri nets (LFS) is one of fundamental problems in the analysis of Petri nets, because it appears as a subproblem of various basic problems. Since LFS is shown to be NP-hard, various heuristics has been proposed to solve the problem of practical size in a reasonable time. In this paper, we propose a new algorithm for this problem. It is based oil the partial order verification technique, and reduces redundant branches in the search tree. Moreover, the proposed algorithm can be combined with various types. of heuristics.
legal firing sequence problem petri nets partial order methods stubborn sets state space explosion