Linear behaviour of term graph rewriting programs

Abstract

The generalized term graph rewriting computational model is exploited to implement concurrent languages based on Girard's Linear Logic (LL). In particular a fragment of LL is identified which is able to serve as a `process calculus' and on which the design of a number of languages can be based. It is then shown how this fragment can be mapped onto equivalent sets of graph rewriting rules that both preserve the functionality of the LL connectives and also exploit the properties of linearity for efficient implementation on a distributed architecture. Notions such as channels, production and consumption of messages, and N-to-N communication between agents, are interpreted in the world of (term) graph rewriting. This work serves two purposes: i) to extend the notion of Term Graph Rewriting as a generalized computational model for the case of linear concurrent languages, and ii) to act as an initial investigation towards a fully linear term graph rewriting model of computation able to be implemented efficiently on distributed architectures.