Linear graph grammar

In computer science, a linear graph grammar (also a connection graph reduction system or a port graph grammar) is a class of graph grammar on which nodes have a number of ports connected together by edges and edges connect exactly two ports together. Interaction nets are a special subclass of linear graph grammars in which rewriting is confluent.

Implementation

Bawden (1993) describes a distributed implemntation in which the linear graph is spread across many computing nodes and may freely migrate in order to make rewrites possible.

Notes

References

Bawden, Alan (1993), [http://dspace.mit.edu/bitstream/handle/1721.1/7085/AITR-1627.pdf?sequence%3D2 Implementing

Distributed Systems Using Linear Naming], A.I. Technical Report No. 1627, MIT.

Rozenberg, Grzegorz (1997), Handbook of Graph Grammars and Computing by Graph Transformations, World Scientific Publishing, volumes 1–3, ISBN 9810228848.
Ehrig, Heckel, Korff, Lowe, Ribeiro, Wagner and Corradini, 1997. Algebraic Approaches to Graph Transformation - Part II: Single Pushout Approach and Comparison with Double Pushout Approach. Pp. 247-312 of (Rozenberg, 1997).