Abstract
The symmetric interaction combinators are a variant of Lafont's interaction combinators. They enjoy a weaker universality property with respect to interaction nets, but are equally expressive. They are a model of deterministic distributed computation and share the good properties of Turing machines (elementary reductions) and of the -calculus (higher-order functions and parallel execution). We introduce a denotational semantics for this system, which is inspired by the relational semantics for linear logic, and prove an injectivity and full completeness result for it. We also consider the algebraic semantics defined by Lafont, and prove that the two are strongly related.
| Original language | English |
|---|---|
| Pages (from-to) | 527-562 |
| Number of pages | 36 |
| Journal | Mathematical Structures in Computer Science |
| Volume | 17 |
| Issue number | 3 |
| DOIs | |
| Publication status | Published - 1 Jun 2007 |
| Externally published | Yes |