A structural approach to graph transformation based on symmetric Petri nets

摘要

Graph Transformation Systems (GTS) and Petri Nets (PN) are two central, theoretically sound, formal models for concurrent or distributed systems. A lot of papers have focused on the relationship between GTS and PN. It is generally accepted that PN are instances of GTS due to the lack of ability to adapt or reconfigure their structure. In this paper, which extends a recent one, we reverse this perspective by presenting a formal definition of GTS in terms of Symmetric Nets (SN). SN are a standard High-Level PN formalism featuring a compact syntax which highlights behavioral symmetries of systems. The major strength lies in the possibility of using well-established tools to edit/efficiently analyze (SN-based) graph transformation models. We follow a structural approach, based on a newly implemented symbolic calculus, to validate Graph Transformation Rules (GTR) and formally verify GTS properties.In the second part of the paper, we supply a semantic characterization of the SN-based graph transformation model, by carrying out a thorough comparison with the classical, algebraic double-pushout (DPO) approach. We constructively and formally show how to translate any DPO rule to a corresponding, elementary or composite, SN rule. We treat both injective and non-injective DPO rules/rule matches. The comparison shows that the SN approach is, in some sense, a generalization of the DPO.