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
Department of Mathematics and Statistics
Dalhousie University

Résultats de recherche: Le chapitre dans un livre, un rapport, une anthologie ou une collection › Contribution à une conférence › Revue par des pairs

Résumé

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.

langue originale	Anglais
titre	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
Nombre de pages	15
Les DOIs	https://doi.org/10.1007/978-3-642-28729-9_21
état	Publié - 3 avr. 2012
Modification externe	Oui
Evénement	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, Estonie Durée: 24 mars 2012 → 1 avr. 2012

Série de publications

Nom	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	7213 LNCS
ISSN (imprimé)	0302-9743
ISSN (Electronique)	1611-3349

Une conférence

Une conférence	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
Pays/Territoire	Estonie
La ville	Tallinn
période	24/03/12 → 1/04/12

Accès au document

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

Contient cette citation

Mazza, D., & Ross, N. J. (2012). Full abstraction for set-based models of the symmetric interaction combinators. Dans 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 (p. 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. p. 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. Dans 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, p. 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, Estonie, 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).

Résultats de recherche: Le chapitre dans un livre, un rapport, une anthologie ou une collection › Contribution à une conférence › Revue par des pairs

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

Résumé

Série de publications

Une conférence

Accès au document

Empreinte digitale

Contient cette citation