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.
Implementations
Bawden introduces linear graphs in the context of a compiler for a fragment of the Scheme programming language. Bawden and Mairson (1998) describe the design of a distributed implementation in which the linear graph is spread across many computing nodes and may freely migrate in order to make rewrites possible.
References
Linear graph grammar Wikipedia(Text) CC BY-SA