We propose a sound and complete axiomatisation of a class of graphs with nesting and either locally or globally restricted nodes. Such graphs allow to represent explicitly and at the right level of abstraction some relevant topological and logical features of models and systems, including nesting, hierarchies, sharing of resources, and pointers or links. We also provide an encoding of the proposed algebra into terms of a gs-monoidal theory, and through these into a suitable class of ”wellscoped” term graphs, showing that this encoding is sound and complete with respect to the axioms of the algebra.
|Title of host publication||Graph Transformations and Model-Driven Engineering : Essays Dedicated to Manfred Nagl on the Occasion of his 65th Birthday|
|Publisher||Springer Berlin Heidelberg|
|Publication status||Published - 2008|
|Series||Lecture Notes in Computer Science|
Bruni, R., Corradini, A., Gadducci, F., Lluch Lafuente, A., & Montanari, U. (2008). On GS-Monoidal Theories for Graphs with Nesting. In Graph Transformations and Model-Driven Engineering: Essays Dedicated to Manfred Nagl on the Occasion of his 65th Birthday (pp. 59-86). Springer Berlin Heidelberg. Lecture Notes in Computer Science, Vol.. 5765 https://doi.org/10.1007/978-3-642-17322-6_4