Visible to the public Linear Logic Propositions as Session TypesConflict Detection Enabled

TitleLinear Logic Propositions as Session Types
Publication TypeMiscellaneous
Year of Publication2014
AuthorsLuis Caires, Frank Pfenning, Bernardo Toninho

Throughout the years, several typing disciplines for the p-calculus have been proposed. Arguably, the most widespread of these typing disciplines consists of session types. Session types describe the input/output behavior of processes and traditionally provide strong guarantees about this behavior (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 p-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.

Citation Keynode-30088

Other available formats:

Caires_Linear_Logic_Props_FP.pdfPDF document543.24 KBDownloadPreview