Interaction Nets vs. the ρ-calculus: Introducing Bigraphical Nets |
| |
Authors: | Maribel Fernndez Ian Mackie Franois-Rgis Sinot |
| |
Affiliation: | aDepartment of Computer Science, King's College London, Strand, London WC2R 2LS, UK;bLIX, École Polytechnique, 91128 Palaiseau, France |
| |
Abstract: | The ρ-calculus generalises both term rewriting and the λ-calculus in a uniform framework. Interaction nets are a form of graph rewriting which proved most successful in understanding the dynamics of the λ-calculus, the prime example being the implementation of optimal β-reduction. It is thus natural to study interaction net encodings of the ρ-calculus as a first step towards the definition of efficient reduction strategies. We give two interaction net encodings which bring a new understanding to the operational semantics of the ρ-calculus; however, these encodings have some drawbacks and to overcome them we introduce bigraphical nets—a new paradigm of computation inspired by Lafont's interactions nets and Milner's bigraphs. |
| |
Keywords: | Rewriting Calculus Interaction Nets Bigraphs |
本文献已被 ScienceDirect 等数据库收录! |
|