Linear logic propositions as session types. (10th November 2014)

• Record Type: Journal Article
• Authors: CAIRES, LUÍS; PFENNING, FRANK; TONINHO, BERNARDO
• Is Part Of: Mathematical structures in computer science. Volume 26:Number 3(2016)
• Page Start: 367
• Page End: 423
• Publication Date: 2014-11-10
• Subjects: Computer science -- Mathematics -- Periodicals; 004.015105
• DOI: 10.1017/S0960129514000218
• Languages: English
• ISSNs: 0960-1295

Abstract

Abstract : Throughout the years, several typing disciplines for the π-calculus have been proposed. Arguably, the most widespread of these typing disciplines consists of session types. Session types describe the input/output behaviour of processes and traditionally provide strong guarantees about this behaviour (i.e. deadlock-freedom and fidelity). While these systems exploit a fundamental notion of linearity, the precise connection between linear logic and session types has not been well understood. This paper proposes a type system for the π-calculus that corresponds to a standard sequent calculus presentation of intuitionistic linear logic, interpreting linear propositions as session types and thus providing a purely logical account of all key features and properties of session types. We show the deep correspondence between linear logic and session types by exhibiting a tight operational correspondence between cut-elimination steps and process reductions. We also discuss an alternative presentation of linear session types based on classical linear logic, and compare our development with other more traditional session type systems.