Graph transformation

Graph transformation concerns the technique to create a new graph out of an original graph using some automatic machine. It has numerous applications, ranging from software verification to layout algorithms.

Graph transformations can be used as a computation abstraction. The basic idea is that the state of a computation can be represented as a graph, further steps in that computation can then be represented as transformation rules on that graph. Such rules consist of a original graph, which is to be matched to a subgraph in the complete state, and a replacing graph, which wil replace the matched subgraph.

References

• Graph Transformation and Graph Grammars
• Heckel, R. (2006). Graph transformation in a nutshell. Electronic Notes in Theoretical Computer Science 148 (1 SPEC. ISS.), pp. 187-198.