computer science Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...

, 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 In mathematics, computer science, and logic, rewriting covers a wide range of methods of replacing subterms of a well-formed formula, formula with other terms. Such methods may be achieved by rewriting systems (also known as rewrite systems, rewr ...

is confluent.

Implementations

Bawden introduces linear graphs in the context of a compiler for a fragment of the

Scheme programming language Scheme is a dialect of the Lisp family of programming languages. Scheme was created during the 1970s at the MIT AI Lab and released by its developers, Guy L. Steele and Gerald Jay Sussman, via a series of memos now known as the Lambda Papers. It ...

.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

References

*Bawden, Alan (1986)
Connection graphs
In ''Proceedings of the 1986 ACM conference on LISP and functional programming'', pp. 258–265,

ACM Press The Association for Computing Machinery (ACM) is a US-based international learned society for computing. It was founded in 1947 and is the world's largest scientific and educational computing society. The ACM is a non-profit professional member ...

. *Bawden, Alan (1992)
Linear graph reduction: confronting the cost of naming
PhD dissertation, MIT. *Bawden, Alan (1993)
Implementing Distributed Systems Using Linear Naming
A.I. Technical Report No. 1627, MIT. *Bawden and Mairson (1998)
Linear naming: experimental software for optimizing communication protocols
Working paper #1, Dept. Computer Science,

Brandeis University , mottoeng = "Truth even unto its innermost parts" , established = , type = Private research university , accreditation = NECHE , president = Ronald D. Liebowitz , pro ...

. Graph rewriting {{computer-science-stub