A Framework for Classical Petri Net Problems: Conservative Petri Nets as an Application

摘要

We present a framework based on permutations of firing sequences and on canonical firing sequences to approach computational problems involving classes of Petri nets with arbitrary arc multiplicities. As an example of application, we use these techniques to obtain PSPACE-completeness for the reachability and the covering problems of conservative Petri nets, generalizing known results for ordinary 1-conservative Petri nets. We also prove PSPACE-completeness for the RecLFS and the liveness problems of conservative Petri nets, for which, in case of ordinary 1-conservative Petri nets, PSPACE-membership but no matching lower bound has been known. Last, we show PSPACE-completeness for the containment and equivalence problems of conservative Petri nets. PSPACE-hardness of the problems mentioned above still holds if they are restricted to ordinary 1-conservative Petri nets.