# Graph rewriting with one-to-many pattern matching?

In the single-pushout approach to graph rewriting, many nodes in a pattern graph can be matched to a single node of a target graph.

My question is if there is a notion of graph rewriting where the inverse is true: that a single node in the pattern graph can match to many nodes of the target graph. For example, the pattern graph $A \rightarrow B$ should be able to match a subgraph isomorphic to $X \rightarrow Y \leftarrow Z$, with the mapping $A \mapsto \{ X, Z \}, B \mapsto \{Y$}. I'm especially interested in a definition where $A \mapsto \{X\}, B \mapsto \{ Y\}$ would not be a valid match for any graph that contains $X \rightarrow Y \leftarrow Z$ as a subgraph.

As an example application, consider the problem of for-loop desugaring. This for-loop:

for (int i = 0; i < n; i++) {
if ( i % 3 == 0) {
printf("Divisible by 3\n");
continue;
}
printf("%d\n", i);
}


desugars to:

int i = 0;
while (i < n) {
if (i % 3 == 0) {
printf("Divisible by 3\n");
i++;
continue;
}
printf("%d\n", i);
i++;
}


A key part of this desugaring -- that the "step" part of the for loop be inserted at the end of the loop and before every "continue" statement -- is most easily expressed as a rewrite on the control-flow graph, where that statement is inserted before every predecessor of the condition (except for before the loop runs).

• I don't understand your objection. Yes, I'm doing graph rewriting. I envision the example I wrote working via a source -> AST -> CFG -> CFG -> AST -> source transformation, but right now I'm just asking about the CFG -> CFG part. – James Koppel Jun 20 '17 at 19:44
• Thanks for the reference. Also, you can stop talking about tree transformations; they're not relevant to the question. – James Koppel Jun 21 '17 at 1:58
• From that paper: "An embedding... is a total mapping i : M -> N" . So, no, it doesn't allow one node in the pattern to match multiple nodes of a graph. So, that paper seems irrelevant. – James Koppel Jun 21 '17 at 2:05
• Hey Jimmy!! Neat question. :) – Michael Wehar Jun 22 '17 at 3:09
• Best comment I could receive on this. Good to hear from you Mike! Do you theorists need graph rewriting for something? – James Koppel Jun 22 '17 at 5:48

## 1 Answer

Belatedly posting this answer:

This is called set node or multi-object matching. This is implemented in tools like Henshin https://www.eclipse.org/henshin/publications.php and described informally in http://www.cs.le.ac.uk/people/rh122/papers/2006/Hec06Nutshell.pdf, see 3.2.

A more formal account is in "Formal foundation of consistent EMF model transformations by algebraic graph transformation."

Thanks to Reiko Heckel for providing me this answer 1 year ago.