Linear graph grammar

In computer science, a linear graph grammar (also a connection graph reduction system or a port graph grammar[1]) 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.[2] Bawden and Mairson (1998) describe a 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.

Notes

  1. Bawden (1986) introduces the formalism calling them connection graphs.
  2. Bawden (1993) is the technical report based on the Ph.D. dissertation, Bawden (1992).

References

This article is issued from Wikipedia - version of the 10/1/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.