01302nas a2200145 4500008004100000245008300041210006900124260001500193300001200208490000900220520081500229100001901044700001901063856007401082 2012 eng d00aFull Abstraction for Set-Based Models of the Symmetric Interaction Combinators0 aFull Abstraction for SetBased Models of the Symmetric Interactio c2012/01/01 a316-3300 v72133 aThe 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.1 aMazza, Damiano1 aRoss, Neil, J. uhttps://lipn.univ-paris13.fr/~mazza/papers/CombSetSem-FOSSACS2012.pdf