Model checking of persistent Petri nets

From MaRDI portal





The paper investigates the possibility of obtaining model checkers that work directly on the syntax of persistent Petri nets which do not require at all to construct the associated transition system. The modal logic S4 is considered for modelling the particular subclass of safe persistent Petri nets, expressing useful safety properties such as reachability of a marking, liveness of a transition, or mutual exclusion of a set of transitions (but not being able to express liveness properties). The authors designed a model checking algorithm which shows, for a given safe persistent system \(\Sigma\) and a formula \(\Phi\), how to reduce the model checking problem to a set of linear programming problems. For the subclass of safe \(T\)-systems, the model checker is proved to be polynomial in the size of \(\Sigma\), but exponential in the length of \(\Phi\) (polynomial complexity of the model checker for both the size of \(\Sigma\) and length of \(\Phi\) being equivalent with the P\(=\)NP problem). For the entire collection see [Zbl 0772.68004].











This page was built for publication: Model checking of persistent Petri nets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4202931)