I have found information on graph grammars and 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?
$\begingroup$
$\endgroup$
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
Graph grammars have uses from software engineering to layout verification. Tinkerpop 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)
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$^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
$\begingroup$
$\endgroup$
This paper 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.
$\begingroup$
$\endgroup$
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.
