On GS-Monoidal Theories for Graphs with Nesting

Roberto Bruni, Andrea Corradini, Fabio Gadducci, Alberto Lluch Lafuente, Ugo Montanari

Research output: Chapter in Book/Report/Conference proceedingBook chapterResearchpeer-review

Abstract

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.
Original languageEnglish
Title of host publicationGraph Transformations and Model-Driven Engineering : Essays Dedicated to Manfred Nagl on the Occasion of his 65th Birthday
PublisherSpringer Berlin Heidelberg
Publication date2008
Pages59-86
ISBN (Print)978-3-642-17321-9
ISBN (Electronic)978-3-642-17322-6
DOIs
Publication statusPublished - 2008
Externally publishedYes
SeriesLecture Notes in Computer Science
Volume5765
ISSN0302-9743

Cite this

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