As of May 31, 2023, we have updated our Code of Conduct.

Questions tagged [interaction-combinators]

The tag has no usage guidance.

6 questions
Filter by
Sorted by
Tagged with
1 vote
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
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
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
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
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