<p>This has been a subject of investigation for the Implicit Computational Complexity (ICC) community recently. </p>

<p>It is known that in certain cases, when the graph you want to evaluate is of a specific type (be it from typing or a global shape restriction, see references) there is a path-based evaluation strategy that is more efficient than the naive one, allowing for instance to evaluate in Logspace [1,2] or Ptime [3].</p>

<p>The jump approach you mention has been studied by Danos &amp; Regnier [4]. They proved it correct (you get the same output) but do not provide an evaluation of the performance gain. I do not know of any work carrying on this analysis (in full generality) so far.</p>

<p>[1] <a href="http://www2.tcs.ifi.lmu.de/~schoepp/Docs/intml_long.pdf" rel="nofollow">http://www2.tcs.ifi.lmu.de/~schoepp/Docs/intml_long.pdf</a></p>

<p>[2] <a href="http://arxiv.org/pdf/1406.2110.pdf" rel="nofollow">http://arxiv.org/pdf/1406.2110.pdf</a></p>

<p>[3] <a href="http://arxiv.org/pdf/1501.05104v2.pdf" rel="nofollow">http://arxiv.org/pdf/1501.05104v2.pdf</a></p>

<p>[4] <a href="http://ac.els-cdn.com/S0304397599000493/1-s2.0-S0304397599000493-main.pdf?_tid=09e49fd8-768c-11e5-a270-00000aacb360&amp;acdnat=1445278134_7609d8ba21c272fe7eab424d38c3f225" rel="nofollow">http://ac.els-cdn.com/S0304397599000493/1-s2.0-S0304397599000493-main.pdf?_tid=09e49fd8-768c-11e5-a270-00000aacb360&amp;acdnat=1445278134_7609d8ba21c272fe7eab424d38c3f225</a></p>

CC BY-SA 3.0
2015-12-20T21:43:59.557Z
I see you have a wide understanding of the field, to be able to point to so specific resources. How can I get that kind of knowledge? What process, exactly, did you go through to know what you do? I'm assuming you're not just opening random papers and googling their references, which, honestly, is the best I know.
MaiaVictor
CC BY-SA 3.0
2015-12-24T12:43:43.043Z
Well I've done my PhD on these topics and I coauthor 2&3 in case did not guess :) ... that helps.
About methodology, well unfortunately sometimes grinding through litterature is necessary, when asking around does not yield results.
Marc
CC BY-SA 3.0
2015-10-19T18:16:11.617Z
2015-10-19T18:16:11.617Z
Marc
<p>Interaction combinators can be evaluated using a path traversing strategy. That is, instead of applying annihilation/commutation rules to active pairs, one simply walks through the graph using a 2-stack machine to keep track of the exit ports.</p>

<p>It is known that this strategy, used naively, can have an exponential slowdown in relation to the former strategy. But that doesn't consider the possibility of jumps. Suppose that, instead of merely walking through the graph, the cursor also keeps track of the nodes it passed through. It it comes back to the same node, it jumps directly to the node whose active port would-be to interact with that one.</p>

<p>Is it possible to use this strategy to evaluate interaction combinators? Can it be as efficient as the graph-reduction view?</p>

<lambda-calculus><interaction-nets><interaction-combinators>
Is it possible to evaluate interaction combinators efficiently using a path-traveling strategy?
MaiaVictor
# Is it possible to evaluate interaction combinators efficiently using a path-traveling strategy?

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

Interaction combinators can be evaluated using a path traversing strategy. That is, instead of applying annihilation/commutation rules to active pairs, one simply walks through the graph using a 2-stack machine to keep track of the exit ports.

It is known that this strategy, used naively, can have an exponential slowdown in relation to the former strategy. But that doesn't consider the possibility of jumps. Suppose that, instead of merely walking through the graph, the cursor also keeps track of the nodes it passed through. It it comes back to the same node, it jumps directly to the node whose active port would-be to interact with that one.

Is it possible to use this strategy to evaluate interaction combinators? Can it be as efficient as the graph-reduction view?

**Tags:** lambda-calculus, interaction-nets, interaction-combinators


---

## 1 answers

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

This has been a subject of investigation for the Implicit Computational Complexity (ICC) community recently.

It is known that in certain cases, when the graph you want to evaluate is of a specific type (be it from typing or a global shape restriction, see references) there is a path-based evaluation strategy that is more efficient than the naive one, allowing for instance to evaluate in Logspace [1,2] or Ptime [3].

The jump approach you mention has been studied by Danos & Regnier [4]. They proved it correct (you get the same output) but do not provide an evaluation of the performance gain. I do not know of any work carrying on this analysis (in full generality) so far.

[1] <http://www2.tcs.ifi.lmu.de/~schoepp/Docs/intml_long.pdf>

[2] <http://arxiv.org/pdf/1406.2110.pdf>

[3] <http://arxiv.org/pdf/1501.05104v2.pdf>

[4] <http://ac.els-cdn.com/S0304397599000493/1-s2.0-S0304397599000493-main.pdf?_tid=09e49fd8-768c-11e5-a270-00000aacb360&acdnat=1445278134_7609d8ba21c272fe7eab424d38c3f225>

> **Comments:**
> **username_0**: I see you have a wide understanding of the field, to be able to point to so specific resources. How can I get that kind of knowledge? What process, exactly, did you go through to know what you do? I'm assuming you're not just opening random papers and googling their references, which, honestly, is the best I know.  
> **username_1**: Well I've done my PhD on these topics and I coauthor 2&3 in case did not guess :) ... that helps. About methodology, well unfortunately sometimes grinding through litterature is necessary, when asking around does not yield results.  

---

