Full abstraction for set-based models of the symmetric interaction combinators

Damiano Mazza; Neil J. Ross

doi:10.1007/978-3-642-28729-9_21

Full abstraction for set-based models of the symmetric interaction combinators

Damiano Mazza
, Neil J. Ross

University Paris 13
Dalhousie University

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Abstract

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.

Original language	English
Title of host publication	Foundations of Software Science and Computational Structures - 15th Int. Conf., FOSSACS 2012, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2012, Proceedings
Pages	316-330
Number of pages	15
DOIs	https://doi.org/10.1007/978-3-642-28729-9_21
Publication status	Published - 3 Apr 2012
Externally published	Yes
Event	15th International Conference on Foundations of Software Science and Computational Structures, FOSSACS 2012, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2012 - Tallinn, Estonia Duration: 24 Mar 2012 → 1 Apr 2012

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	7213 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	15th International Conference on Foundations of Software Science and Computational Structures, FOSSACS 2012, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2012
Country/Territory	Estonia
City	Tallinn
Period	24/03/12 → 1/04/12

Keywords

Denotational semantics
Interaction nets
Observational equivalence

Access to Document

10.1007/978-3-642-28729-9_21

Cite this

Mazza, D., & Ross, N. J. (2012). Full abstraction for set-based models of the symmetric interaction combinators. In Foundations of Software Science and Computational Structures - 15th Int. Conf., FOSSACS 2012, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2012, Proceedings (pp. 316-330). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7213 LNCS). https://doi.org/10.1007/978-3-642-28729-9_21

Mazza, Damiano ; Ross, Neil J. / Full abstraction for set-based models of the symmetric interaction combinators. Foundations of Software Science and Computational Structures - 15th Int. Conf., FOSSACS 2012, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2012, Proceedings. 2012. pp. 316-330 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{cf634165df7a46b699ccf58877c9b6b8,

title = "Full abstraction for set-based models of the symmetric interaction combinators",

abstract = "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.",

keywords = "Denotational semantics, Interaction nets, Observational equivalence",

author = "Damiano Mazza and Ross, \{Neil J.\}",

year = "2012",

month = apr,

day = "3",

doi = "10.1007/978-3-642-28729-9\_21",

language = "English",

isbn = "9783642287282",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "316--330",

booktitle = "Foundations of Software Science and Computational Structures - 15th Int. Conf., FOSSACS 2012, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2012, Proceedings",

note = "15th International Conference on Foundations of Software Science and Computational Structures, FOSSACS 2012, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2012 ; Conference date: 24-03-2012 Through 01-04-2012",

}

Mazza, D & Ross, NJ 2012, Full abstraction for set-based models of the symmetric interaction combinators. in Foundations of Software Science and Computational Structures - 15th Int. Conf., FOSSACS 2012, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2012, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 7213 LNCS, pp. 316-330, 15th International Conference on Foundations of Software Science and Computational Structures, FOSSACS 2012, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2012, Tallinn, Estonia, 24/03/12. https://doi.org/10.1007/978-3-642-28729-9_21

Full abstraction for set-based models of the symmetric interaction combinators. / Mazza, Damiano; Ross, Neil J.
Foundations of Software Science and Computational Structures - 15th Int. Conf., FOSSACS 2012, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2012, Proceedings. 2012. p. 316-330 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7213 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Full abstraction for set-based models of the symmetric interaction combinators

AU - Mazza, Damiano

AU - Ross, Neil J.

PY - 2012/4/3

Y1 - 2012/4/3

N2 - 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.

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.

KW - Denotational semantics

KW - Interaction nets

KW - Observational equivalence

U2 - 10.1007/978-3-642-28729-9_21

DO - 10.1007/978-3-642-28729-9_21

M3 - Conference contribution

AN - SCOPUS:84859153508

SN - 9783642287282

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 316

EP - 330

BT - Foundations of Software Science and Computational Structures - 15th Int. Conf., FOSSACS 2012, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2012, Proceedings

T2 - 15th International Conference on Foundations of Software Science and Computational Structures, FOSSACS 2012, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2012

Y2 - 24 March 2012 through 1 April 2012

ER -

Mazza D, Ross NJ. Full abstraction for set-based models of the symmetric interaction combinators. In Foundations of Software Science and Computational Structures - 15th Int. Conf., FOSSACS 2012, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2012, Proceedings. 2012. p. 316-330. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-28729-9_21

Full abstraction for set-based models of the symmetric interaction combinators

Abstract

Publication series

Conference

Keywords

Access to Document

Fingerprint

Cite this