Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
423129 | Electronic Notes in Theoretical Computer Science | 2006 | 14 Pages |
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics