<p>The answer is yes.  It is an immediate consequence of the definition of <em>translation</em> used by Lafont in <a href="http://iml.univ-mrs.fr/~lafont/pub/combinators.ps" rel="nofollow">his paper</a> introducing the interaction combinators.</p>

<p>A <em>Lafont translation</em> $\Phi$ from an interaction net system to another is an arity-preserving map from the symbols (i.e. the atomic agents) of the first system to <em>principal nets</em> of the other.  Basically, a principal net of arity $n$ is a "tree" of agents with some leaves connected to each other and with exactly $n$ free leaves.  In particular, it has exactly one free principal port and $n$ free auxiliary ports, so it may be seen as a "macro-agent".  See Lafont's paper for the exact definition.</p>

<p>A translation $\Phi$ must also satisfy the following <em>simulation property</em>: for all symbols (i.e. agents) $\alpha,\beta$ of the source system,</p>

<p>$$\alpha\bowtie\beta\to\nu\qquad\text{implies}\qquad\Phi(\alpha)\bowtie\Phi(\beta)\to^\ast\Phi(\nu)$$</p>

<p>where the notation $\alpha\bowtie\beta$ stands for an active pair, and $\Phi(\alpha)\bowtie\Phi(\beta)=\Phi(\alpha\bowtie\beta)$ for its translation.</p>

<p>Now, let $M$ be the longest simulating reduction $\Phi(\alpha)\bowtie\Phi(\beta)\to^\ast\Phi(\nu)$ (such $M$ exists because the number of possible active pairs is finite).  It is clear that, if $\mu\to^\ast\mu'$ in $n$ steps the source system, then $\Phi(\mu)\to^\ast\Phi(\mu')$ in at most $M\cdot n$ steps in the target system.  This is stated as Proposition 4 in Lafont's paper.  So the simulation is efficient according to the notion of efficiency given in the question.</p>

<p>The interaction combinators are universal in the sense that every system of interaction nets may be translated in the interaction combinators, in the above sense.  Hence the claim.</p>

CC BY-SA 3.0
2015-10-06T14:15:28.560Z
2015-10-06T19:29:59.763Z
2015-10-06T19:29:59.763Z
Damiano Mazza
<p>It is widely known that interaction combinators can implement any interaction net. My question is, can they do so efficiently? I.e., is it possible to prove that there is no interaction net system that can't be emulated on interaction combinators with the same number of reductions up to a finite constant?</p>

<cc.complexity-theory><computability>
Can interaction combinators implement any interaction net efficiently?
MaiaVictor
# Can interaction combinators implement any interaction net efficiently?

(Asked by: username_0 on 2015-10-05)

It is widely known that interaction combinators can implement any interaction net. My question is, can they do so efficiently? I.e., is it possible to prove that there is no interaction net system that can't be emulated on interaction combinators with the same number of reductions up to a finite constant?

**Tags:** cc.complexity-theory, computability

---

## 1 answers

### Answer by username_1 on 2015-10-06. Score: 3 | Accepted answer

The answer is yes. It is an immediate consequence of the definition of *translation* used by Lafont in [his paper](http://iml.univ-mrs.fr/~lafont/pub/combinators.ps) introducing the interaction combinators.

A *Lafont translation* $\Phi$ from an interaction net system to another is an arity-preserving map from the symbols (i.e. the atomic agents) of the first system to *principal nets* of the other. Basically, a principal net of arity $n$ is a "tree" of agents with some leaves connected to each other and with exactly $n$ free leaves. In particular, it has exactly one free principal port and $n$ free auxiliary ports, so it may be seen as a "macro-agent". See Lafont's paper for the exact definition.

A translation $\Phi$ must also satisfy the following *simulation property*: for all symbols (i.e. agents) $\alpha,\beta$ of the source system,

$$\alpha\bowtie\beta\to\nu\qquad\text{implies}\qquad\Phi(\alpha)\bowtie\Phi(\beta)\to^\ast\Phi(\nu)$$

where the notation $\alpha\bowtie\beta$ stands for an active pair, and $\Phi(\alpha)\bowtie\Phi(\beta)=\Phi(\alpha\bowtie\beta)$ for its translation.

Now, let $M$ be the longest simulating reduction $\Phi(\alpha)\bowtie\Phi(\beta)\to^\ast\Phi(\nu)$ (such $M$ exists because the number of possible active pairs is finite). It is clear that, if $\mu\to^\ast\mu'$ in $n$ steps the source system, then $\Phi(\mu)\to^\ast\Phi(\mu')$ in at most $M\cdot n$ steps in the target system. This is stated as Proposition 4 in Lafont's paper. So the simulation is efficient according to the notion of efficiency given in the question.

The interaction combinators are universal in the sense that every system of interaction nets may be translated in the interaction combinators, in the above sense. Hence the claim.


---

