We tackle the problem of graph transformation with a particular focus on node cloning. We propose a new approach to graph rewriting where nodes can be cloned zero, one or more times. A node can be cloned together with all its incident edges, with only its outgoing edges, with only its incoming edges or with none of its incident edges. We thus subsume previous works such as the sesqui-pushout, the heterogeneous pushout and the adaptive star grammars approaches. A rewrite rule is defined as a span where the right-hand and left-hand sides are graphs while the interface is a polarized graph. A polarized graph is a graph endowed with some annotations on nodes. The way a node is cloned is indicated by its polarization annotation. We use these annotations for designing graph transformation with polarized cloning. We show how a clone of a node can be built according to the different possible polarizations and define a rewrite step as a final pullback complement followed by a pushout. This is called the polarized sesqui-pushout approach. We also provide an algorithmic presentation of the proposed graph transformation with polarized cloning.
Cloning is also one of the features of the sesqui-pushout approach to graph transformation @cite_0 . In this approach, a rule is a span @math of multigraphs and the application of a rule to a graph @math can be illustrated by the same figure as for a DPO step (as in the introduction), where the right-hand side is a pushout as in the DPO approach but the left-hand side is a pullback, and moreover it is a final pullback complement. The sesqui-pushout approach and ours mainly differ in the way of handling cloning. In @cite_0 , the cloning of a node is performed by copying all incident edges (incoming and outgoing edges) of the cloned node. This is a particular case of our way of cloning nodes. The use of polarized multigraphs helped us to specify for every clone, the way incident edges can be copied. Therefore, a sesqui-pushout rewriting step can be simulated by a rewriting step with polarized rules, but the converse does not hold in general.
@cite_0
2092445638
Abstract The purpose of the present paper is twofold: Firstly, show that it is possible to rewrite graphs in a way equivalent to, and in fact slightly more powerful than that of Ehrig, Pfender and Schneider (1973), which has, since then, been developed mainly by the Berlin school. Our method consists in using a single push-out of partial morphisms and is described in Section 3. Section 1 is devoted to the elementary definitions concerning graphs and related terms. Section 2 contains the set-theoretic prerequisites for the sequel but the proofs have been moved into an appendix, for easier reading. Secondly, we indicate in Section 4 why this method is not really fit for rewriting graphs that represent collapsed terms (i.e., sharing common subterms) and we introduce pushouts of total functions, which are not morphisms everywhere on their domain. This method is connected to the classical rewriting of the corresponding terms. The adequacy of these new rewriting rules is then tested to prove a local confluence criterion a la Knuth-Bendix (1970) in Section 5, the proof of which turns out to be very short.