On the Flatness of Immediate Observation Petri Nets
share
In a previous paper we introduced immediate observation (IO) Petri nets, a class of interest in the study of population protocols (a model of distributed computation), and enzymatic chemical networks. We showed that many problems for this class are PSPACE-complete, including parameterized problems asking whether an infinite set of Petri nets with the same underlying net but different initial markings satisfy a given property. The proofs of PSPACE inclusion did not provide explicit algorithms, leaving open the question of practical verification procedures. In the first part of this paper we show that IO Petri nets are globally flat, thus allowing their safety properties to be checked by efficient symbolic model checking tools using acceleration techniques, like FAST. In the second part, we extend IO nets in two natural ways: by lifting the restriction on the number of so-called "observed" places, and by lifting the restriction on so-called "destination" places. The first extension proves to be essentially equivalent to the IO model. The second extension however is much more expressive and is no longer globally flat, but we show that its parametrized reachability, coverability and liveness problems remain decidable in PSPACE. Additionally, we observe that the pre-image computation for this second extension is locally flat, which allows application of tools like FAST to the reachability problem. This second class captures in a simple way the core reason that the IO models allow verification in PSPACE, and we believe it is of independent theoretical interest.
READ FULL TEXT