<p>Belatedly posting this answer:</p>

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

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

<p>Thanks to Reiko Heckel for providing me this answer 1 year ago.</p>

CC BY-SA 4.0
2018-06-30T04:26:32.537Z
2018-06-30T04:26:32.537Z
James Koppel
<p>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.</p>

<p>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 <strong>not</strong> be a valid match for any graph that contains $X \rightarrow Y \leftarrow Z$ as a subgraph.</p>

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

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

<p>desugars to:</p>

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

<p>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).</p>

CC BY-SA 3.0
2017-06-20T19:44:59.333Z
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
CC BY-SA 3.0
2017-06-21T01:58:04.933Z
Thanks for the reference. Also, you can stop talking about tree transformations; they're not relevant to the question.
James Koppel
CC BY-SA 3.0
2017-06-21T02:05:25.077Z
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
CC BY-SA 3.0
2017-06-22T03:09:43.390Z
Hey Jimmy!!  Neat question.  :)
Michael Wehar
CC BY-SA 3.0
2017-06-22T05:48:56.380Z
Best comment I could receive on this. Good to hear from you Mike! Do you theorists need graph rewriting for something?
James Koppel
CC BY-SA 3.0
2017-06-26T05:01:33.477Z
I actually don't know about graph rewriting.  I'm familiar with string rewriting and I'm also familiar with graph automata, but I've never learned much about graph rewriting.  I want to learn more!  :)
Michael Wehar
CC BY-SA 3.0
2017-06-26T05:12:41.590Z
I'm searching a bit now, but it seems that graph automata and graph rewriting automata are different things (at least I think so).  Now, I got to learn more about graph rewriting automata!  :)
Michael Wehar
<graph-theory><pl.programming-languages><term-rewriting-systems>
Graph rewriting with one-to-many pattern matching?
James Koppel
# Graph rewriting with one-to-many pattern matching?

(Asked by: username_0 on 2017-06-19)

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).

**Tags:** graph-theory, pl.programming-languages, term-rewriting-systems

> **Comments:**
> **username_0**: 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.  
> **username_0**: Thanks for the reference. Also, you can stop talking about tree transformations; they're not relevant to the question.  
> **username_0**: 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.  
> **username_1**: Hey Jimmy!!  Neat question.  :)  
> **username_0**: Best comment I could receive on this. Good to hear from you Mike! Do you theorists need graph rewriting for something?  
> **username_1**: I actually don't know about graph rewriting.  I'm familiar with string rewriting and I'm also familiar with graph automata, but I've never learned much about graph rewriting.  I want to learn more!  :)  
> **username_1**: I'm searching a bit now, but it seems that graph automata and graph rewriting automata are different things (at least I think so).  Now, I got to learn more about graph rewriting automata!  :)  

---

## 1 answers

### Answer by username_0 on 2018-06-30. Score: 2 | Accepted 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.


---

