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 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
- Bawden (1986) introduces the formalism calling them connection graphs.
- Bawden (1993) is the technical report based on the Ph.D. dissertation, Bawden (1992).
gollark: Can you not just swap the flash chip, or is that utterly impossible?
gollark: This would never be a problem for me, as a member of the superior "having a server with remote management hardware but never using it" gang.
gollark: An alleged interview.
gollark: Also, I can use HSTS to force HTTPS all the time and stop downgrade attacks.
gollark: Well, I don't, because:- things may default to HTTP, and redirecting them is good- if the user wants anything before TLS 1.2, they're wrong
References
- Bawden, Alan (1986), Connection graphs, In Proceedings of the 1986 ACM conference on LISP and functional programming, pp. 258–265, ACM Press.
- 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.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.