5
$\begingroup$

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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – MaiaVictor
    Dec 20, 2015 at 21:43
  • $\begingroup$ 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. $\endgroup$
    – Marc
    Dec 24, 2015 at 12:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.