Questions tagged [interaction-combinators]
The interaction-combinators tag has no usage guidance.
6
questions
1
vote
1
answer
71
views
What is an efficient algorithm to check for equivalence on symmetric interaction combinators?
Symmetric interaction combinators are a graph-rewriting model of deterministic computation derived from Lafont's interaction nets. In the paper "Observational Equivalence and Full Abstraction in ...
- 3,087
3
votes
1
answer
147
views
Is there an efficient algorithm to check for duplicator-invariant equivalence on symmetric interaction combinators?
Consider the 3 symmetric interaction combinator nets below:
Despite being different nets, they are equal, in the sense that, if we view white nodes as lambdas and applications, and black nodes as ...
- 3,087
0
votes
0
answers
37
views
Combinations of subsets
Problem. Let $x = (x_1,...,x_N) \in K^{N}$, i.e., each element $x_j$ of $x$ can take $K$ discrete values. Let $x_{(i)}$, for $i \in 1,...,I,$ be a vector of overlapping subsets of $x$. For example, ...
- 101
1
vote
0
answers
54
views
How to read this formula for composition in an asynchronous interaction category?
The paper is available here Interaction Categories and the Foundations of Typed Concurrent Programming Abramsky, Gay, Nagarajan
p.38 composition of two processes $p:A \rightarrow B$, $q:B \rightarrow ...
- 11
1
vote
0
answers
56
views
Efficient compilation of interaction combinators with infinite cell types to usual interaction combinators?
It is known that interaction combinators can implement any interaction net system efficiently. Now, let us define a modification of interaction combinators, which, instead of two types of fan cells, ...
- 3,087
5
votes
1
answer
98
views
Is it possible to evaluate interaction combinators efficiently using a path-traveling strategy?
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-...
- 3,087