Graph rewriting with polarized cloningReport as inadecuate

Graph rewriting with polarized cloning - Download this document for free, or read online. Document in PDF available to download.

1 CASYS - Calculs Algébriques et Systèmes Dynamiques LJK - Laboratoire Jean Kuntzmann 2 LIG - Laboratoire d-Informatique de Grenoble

Abstract : We tackle the problem of graph transformation with a particular focus on node cloning. We propose a graph rewriting framework where nodes can be cloned zero, one or more times. A node can be cloned together with all its incident edges, with only the outgoing edges, with only the incoming edges or without any of the incident edges. We thus subsume previous works such as the sesqui-pushout, the heterogeneous pushout and the adaptive star grammars approaches. A rule is defined as a span $\mathbb{L} \stackrel{l}{\longleftarrow} \mathbb{K} \stackrel{r}{\longrightarrow} R$ where the right-hand side $R$ is a multigraph, the left-hand side $\mathbb{L}$ and the interface $\mathbb{K}$ are polarized multigraphs. A polarized multigraph is a multigraph endowed with some cloning annotations on nodes and edges. We introduce the notion of polarized multigraphs and define a rewriting step as pushback followed by a pushout in the same way as in the sesqui-pushout approach.

Keywords : Categories Graph transformations Cloning

Author: Dominique Duval - Rachid Echahed - Frédéric Prost -



Related documents