TY - JOUR
T1 - Full Abstraction for Set-Based Models of the Symmetric Interaction Combinators
JF - Proceedings of the 15th International Conference on Foundations of Software Science and Computation Structures
Y1 - 2012
A1 - Damiano Mazza
A1 - Neil J. Ross
AB - The symmetric interaction combinators are a model of distributed and deterministic computation based on Lafontâ€™s interaction nets, a special form of graph rewriting. The interest of the symmetric interaction combinators lies in their universality, that is, the fact that they may encode all other interaction net systems; for instance, several implementations of the lambda-calculus in the symmetric interaction combinators exist, related to Lampingâ€™s sharing graphs for optimal reduction. A certain number of observational equivalences were introduced for this system, by Lafont, Fernandez and Mackie, and the first author. In this paper, we study the problem of full abstraction with respect to one of these equivalences, using a class of very simple denotational models based on pointed sets.
VL - 7213
U4 - 316-330
UR - https://lipn.univ-paris13.fr/~mazza/papers/CombSetSem-FOSSACS2012.pdf
ER -