<p>Graph grammars have uses from software engineering to layout verification. <a href="http://tinkerpop.apache.org/gremlin.html" rel="nofollow noreferrer">Tinkerpop</a> is a fairly popular system for graph traversal.</p>
<p>So recall a regular grammar where you have rewrite rules as follows:</p>
<p><span class="math-container">$$S \to aSb$$</span></p>
<p><span class="math-container">$$S \to ba$$</span></p>
<p>This generates the infinite set</p>
<p><span class="math-container">$$\{a^nbab^n \mid n \geq 0 \} = \{ba, abab, aababb, aaababbb, \dotsc \}$$</span></p>
<p>(See <a href="https://en.wikipedia.org/wiki/Formal_grammar" rel="nofollow noreferrer">here</a>)</p>
<p>Now what if you wanted a similar construction on graphs? A graph grammar would be a grammar that would deal with graphs instead of strings.</p>
<p><a href="https://i.sstatic.net/j9L9D.png" rel="nofollow noreferrer">Here</a><span class="math-container">$^1$</span> is an example of a program that tells you if a graph is a forest or not.</p>
<p>So on the left hand side we have a graph for the transformation rules and on the right hand side we have the graph that we want to transform to.</p>
<p>For example for the subroutine RemoveLeaf if it sees a directed graph from y to x it will remove the edge to x and the vertex x. If loop returns something other than null then the program will return No based on line one and two.</p>
<p><span class="math-container">$^1$</span>Picture from <a href="https://www.cs.york.ac.uk/plasma/wiki/index.php?title=GP_(Graph_Programs)" rel="nofollow noreferrer">Chris Poskitt</a></p>

CC BY-SA 4.0
2017-10-28T04:57:56.473Z
2021-01-10T17:34:39.113Z
2021-01-10T17:34:39.113Z
Joshua Herman
<p><a href="http://www.sciencedirect.com/science/article/pii/089812219290124Z" rel="noreferrer">This paper</a> opens with an introductory survey on graph grammars and then advances two new applications. It’s dated (1992) but explains the concepts well enough that it seems like the kind of thing you’re interested in.</p>

CC BY-SA 3.0
2017-10-28T04:10:29.677Z
2017-10-28T04:10:29.677Z
Stella Biderman
<p>You may also want to look at the Book by Courcelle a,d J. Engelfriet <a href="https://hal.inria.fr/hal-00646514/document" rel="noreferrer">https://hal.inria.fr/hal-00646514/document</a> where links between graph grammars and MSOL-definable graph classes are discussed. You can also find in this book several references. </p>

CC BY-SA 3.0
2017-10-30T08:39:43.577Z
2017-10-30T08:39:43.577Z
M. kanté
<p>I have found information on graph grammars and <a href="https://en.wikipedia.org/wiki/Graph_rewriting" rel="noreferrer">graph rewriting</a>, but the papers that I find on it are a bit thick. Can someone give a quick overview of what graph grammars are, as well as an overview of the basic uses of them?</p>

<graph-theory><graph-algorithms><fl.formal-languages><grammars>
What are graph grammars?
CinchBlue
# What are graph grammars?

(Asked by: username_0 on 2017-10-28)

I have found information on graph grammars and [graph rewriting](https://en.wikipedia.org/wiki/Graph_rewriting), but the papers that I find on it are a bit thick. Can someone give a quick overview of what graph grammars are, as well as an overview of the basic uses of them?

**Tags:** graph-theory, graph-algorithms, fl.formal-languages, grammars

---

## 3 answers

### Answer by username_1 on 2017-10-28. Score: 6 | Accepted answer

Graph grammars have uses from software engineering to layout verification. [Tinkerpop](http://tinkerpop.apache.org/gremlin.html) is a fairly popular system for graph traversal.

So recall a regular grammar where you have rewrite rules as follows:

$$S \to aSb$$

$$S \to ba$$

This generates the infinite set

$$\{a^nbab^n \mid n \geq 0 \} = \{ba, abab, aababb, aaababbb, \dotsc \}$$

(See [here](https://en.wikipedia.org/wiki/Formal_grammar))

Now what if you wanted a similar construction on graphs? A graph grammar would be a grammar that would deal with graphs instead of strings.

[Here](https://i.sstatic.net/j9L9D.png)$^1$ is an example of a program that tells you if a graph is a forest or not.

So on the left hand side we have a graph for the transformation rules and on the right hand side we have the graph that we want to transform to.

For example for the subroutine RemoveLeaf if it sees a directed graph from y to x it will remove the edge to x and the vertex x. If loop returns something other than null then the program will return No based on line one and two.

$^1$Picture from [Chris Poskitt](https://www.cs.york.ac.uk/plasma/wiki/index.php?title=GP_(Graph_Programs))


---

### Answer by username_2 on 2017-10-28. Score: 6

[This paper](http://www.sciencedirect.com/science/article/pii/089812219290124Z) opens with an introductory survey on graph grammars and then advances two new applications. It’s dated (1992) but explains the concepts well enough that it seems like the kind of thing you’re interested in.


---

### Answer by username_3 on 2017-10-30. Score: 5

You may also want to look at the Book by Courcelle a,d J. Engelfriet <https://hal.inria.fr/hal-00646514/document> where links between graph grammars and MSOL-definable graph classes are discussed. You can also find in this book several references.


---

