A Calculus for Interaction Nets Based on the Linear Chemical Abstract Machine

Ian Mackie; Shinya Sato

doi:10.1016/j.entcs.2008.10.027

A Calculus for Interaction Nets Based on the Linear Chemical Abstract Machine

Ian Mackie
, Shinya Sato

École Polytechnique

Faculty of Econoinformatics
Himeji Dokkyo University

Research output: Contribution to journal › Conference article › peer-review

6 Citations (Scopus)

Abstract

Interaction nets are graph rewriting systems which are a generalisation of proof nets for classical linear logic. The linear chemical abstract machine (CHAM) is a term rewriting system which corresponds to classical linear logic, via the Curry-Howard isomorphism. We can obtain a textual calculus for interaction nets which is surprisingly similar to linear CHAM based on the multiplicative fragment of classical linear logic. In this paper we introduce a framework based on the linear CHAM to model interaction net reduction. We obtain a textual calculus for interaction nets that is closer to the graphical representation than previous attempts.

Original language	English
Pages (from-to)	59-70
Number of pages	12
Journal	Electronic Notes in Theoretical Computer Science
Volume	192
Issue number	3
DOIs	https://doi.org/10.1016/j.entcs.2008.10.027
Publication status	Published - 10 Nov 2008
Event	3rd International Workshop on Developments in Computational Models, DCM 2007 as a satellite event of ICALP 2007 - Wroclaw, Poland Duration: 15 Jul 2007 → 15 Jul 2007

Keywords

CHAM
Interaction net
chemical abstract machine
linear logic

Access to Document

10.1016/j.entcs.2008.10.027

Cite this

@article{d92c4faba158402785b4f412d76d6404,

title = "A Calculus for Interaction Nets Based on the Linear Chemical Abstract Machine",

abstract = "Interaction nets are graph rewriting systems which are a generalisation of proof nets for classical linear logic. The linear chemical abstract machine (CHAM) is a term rewriting system which corresponds to classical linear logic, via the Curry-Howard isomorphism. We can obtain a textual calculus for interaction nets which is surprisingly similar to linear CHAM based on the multiplicative fragment of classical linear logic. In this paper we introduce a framework based on the linear CHAM to model interaction net reduction. We obtain a textual calculus for interaction nets that is closer to the graphical representation than previous attempts.",

keywords = "CHAM, Interaction net, chemical abstract machine, linear logic",

author = "Ian Mackie and Shinya Sato",

year = "2008",

month = nov,

day = "10",

doi = "10.1016/j.entcs.2008.10.027",

language = "English",

volume = "192",

pages = "59--70",

journal = "Electronic Notes in Theoretical Computer Science",

issn = "1571-0661",

publisher = "Elsevier B.V.",

number = "3",

note = "3rd International Workshop on Developments in Computational Models, DCM 2007 as a satellite event of ICALP 2007 ; Conference date: 15-07-2007 Through 15-07-2007",

}

TY - JOUR

T1 - A Calculus for Interaction Nets Based on the Linear Chemical Abstract Machine

AU - Mackie, Ian

AU - Sato, Shinya

PY - 2008/11/10

Y1 - 2008/11/10

N2 - Interaction nets are graph rewriting systems which are a generalisation of proof nets for classical linear logic. The linear chemical abstract machine (CHAM) is a term rewriting system which corresponds to classical linear logic, via the Curry-Howard isomorphism. We can obtain a textual calculus for interaction nets which is surprisingly similar to linear CHAM based on the multiplicative fragment of classical linear logic. In this paper we introduce a framework based on the linear CHAM to model interaction net reduction. We obtain a textual calculus for interaction nets that is closer to the graphical representation than previous attempts.

AB - Interaction nets are graph rewriting systems which are a generalisation of proof nets for classical linear logic. The linear chemical abstract machine (CHAM) is a term rewriting system which corresponds to classical linear logic, via the Curry-Howard isomorphism. We can obtain a textual calculus for interaction nets which is surprisingly similar to linear CHAM based on the multiplicative fragment of classical linear logic. In this paper we introduce a framework based on the linear CHAM to model interaction net reduction. We obtain a textual calculus for interaction nets that is closer to the graphical representation than previous attempts.

KW - CHAM

KW - Interaction net

KW - chemical abstract machine

KW - linear logic

UR - https://www.scopus.com/pages/publications/55249125202

U2 - 10.1016/j.entcs.2008.10.027

DO - 10.1016/j.entcs.2008.10.027

M3 - Conference article

AN - SCOPUS:55249125202

SN - 1571-0661

VL - 192

SP - 59

EP - 70

JO - Electronic Notes in Theoretical Computer Science

JF - Electronic Notes in Theoretical Computer Science

IS - 3

T2 - 3rd International Workshop on Developments in Computational Models, DCM 2007 as a satellite event of ICALP 2007

Y2 - 15 July 2007 through 15 July 2007

ER -

A Calculus for Interaction Nets Based on the Linear Chemical Abstract Machine

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this