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 heuri stics has been proposed to solve the problem of practical size in a reasona ble 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 combin ed with various types. of heuristics.