Graph transformation is a specification technique suitable for a wide range of applications, specially the ones that require a sophisticated notion of state. In graph transformation, states are represented by graphs and actions are specified by rules. Most algebraic approaches to graph transformation proposed in the literature ensure that if an item is preserved by a rule, so are its connections with the graph where it is embedded. But there are applications in which it is desirable to specify different embeddings. For example when cloning an item, there may be a need to handle the original and the copy in different ways. We propose a new algebraic approach to graph transformation, AGREE: Algebraic Graph Rewriting with controllEd Embedding, where rules allow one to specify how the embedding should be carried out. We define this approach in the framework of classified categories which are categories endowed with partial map classifiers. This new approach leads to graph transformations in which effects may be non-local, e.g. a rewrite step may alter a node of the host graph which is outside the image of the left-hand side of the considered rule. We propose a syntactic condition on AGREE rules which guarantees the locality of transformations. We also compare AGREE with other algebraic approaches to graph transformation.

Algebraic graph rewriting with controlled embedding

Abstract

Graph transformation is a specification technique suitable for a wide range of applications, specially the ones that require a sophisticated notion of state. In graph transformation, states are represented by graphs and actions are specified by rules. Most algebraic approaches to graph transformation proposed in the literature ensure that if an item is preserved by a rule, so are its connections with the graph where it is embedded. But there are applications in which it is desirable to specify different embeddings. For example when cloning an item, there may be a need to handle the original and the copy in different ways. We propose a new algebraic approach to graph transformation, AGREE: Algebraic Graph Rewriting with controllEd Embedding, where rules allow one to specify how the embedding should be carried out. We define this approach in the framework of classified categories which are categories endowed with partial map classifiers. This new approach leads to graph transformations in which effects may be non-local, e.g. a rewrite step may alter a node of the host graph which is outside the image of the left-hand side of the considered rule. We propose a syntactic condition on AGREE rules which guarantees the locality of transformations. We also compare AGREE with other algebraic approaches to graph transformation.
Scheda breve Scheda completa Scheda completa (DC)
2020
Corradini, A.; Duval, D.; Echahed, R.; Prost, F.; Ribeiro, L.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: `https://hdl.handle.net/11568/1081103`
Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

• ND
• 5
• 3