linear graph grammar

In computer science, a linear graph grammar (also a connection graph reduction system or a port graph grammarBawden (1986) introduces the formalism calling them connection graphs. ) 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 (1993) is the technical report based on the Ph.D. dissertation, Bawden (1992). 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.

Notes

{{reflist}}

References

  • Bawden, Alan (1986), [http://dl.acm.org/citation.cfm?id=319868 Connection graphs], In Proceedings of the 1986 ACM conference on LISP and functional programming, pp. 258–265, ACM Press.
  • Bawden, Alan (1992), [http://dspace.mit.edu/bitstream/handle/1721.1/13191/26680868-MIT.pdf?sequence=2 Linear graph reduction: confronting the cost of naming], PhD dissertation, MIT.
  • 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.
  • Bawden and Mairson (1998), [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.25.5189&rep=rep1&type=pdf Linear naming: experimental software for optimizing communication protocols], Working paper #1, Dept. Computer Science, Brandeis University.

Category:Graph rewriting

{{computer-science-stub}}

{{graph-stub}}