×

zbMATH — the first resource for mathematics

Rewriting logic as a unifying framework for Petri nets. (English) Zbl 1017.68080
Ehrig, Hartmut (ed.) et al., Unifying Petri nets. Advances in Petri nets. Berlin: Springer. Lect. Notes Comput. Sci. 2128, 250-303 (2001).
Summary: We propose rewriting logic as a unifying framework for a wide range of Petri nets models. We treat in detail place/transition nets and important extensions of the basic model by individual tokens, test arcs, and time. Based on the idea that “Petri nets are monoids” suggested by Meseguer and Montanari we define a rewriting semantics that maps place/transition nets into rewriting logic specifications. We furthermore generalize this result to a general form of algebraic net specifications subsuming also colored Petri nets as a special case. The soundness and completeness results we state relate the commutative process semantics of Petri nets proposed by Best and Devillers to the model-theoretic semantics of rewriting logic in the sense of natural isomorphisms between suitable functors. In addition we show how place/transition nets with test arcs and timed Petri nets can be equipped with a rewriting semantics and discuss how other extensions can be treated along similar lines. Beyond the conceptual unification of quite different kinds of Petri nets within a single framework, the rewriting semantics can provide a guide for future extensions of Petri nets and help to cope with the growing diversity of models in this field. On the practical side, a major application of the rewriting semantics is its use as a logical and operational representation of Petri net models for formal verification and for the efficient execution and analysis using a rewriting engine such as Maude, which also allows us to specify different execution and analysis strategies in the same rewriting logic language by means of reflection.
For the entire collection see [Zbl 0978.00023].

MSC:
68Q85 Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)
Software:
Maude
PDF BibTeX XML Cite
Full Text: Link