Hostname: page-component-7b7567c8c-2n9c9 Total loading time: 0 Render date: 2026-11-17T15:08:52.423Z Has data issue: false hasContentIssue false

Games and full completeness for multiplicative linear logic

Published online by Cambridge University Press:  12 March 2014

Samson Abramsky
Affiliation:
Department of Computing, Imperial College of Science, Technology and Medicine, London, SW7 2BZ, England, E-mail: sa@doc.ic.ac.uk
Radha Jagadeesan
Affiliation:
Department of Mathematical Sciences, Loyola University, Chicago, E-mail: radha@feldberg.math.luc.edu

Abstract

We present a game semantics for Linear Logic, in which formulas denote games and proofs denote winning strategies. We show that our semantics yields a categorical model of Linear Logic and prove full completeness for Multiplicative Linear Logic with the MIX rule: every winning strategy is the denotation of a unique cut-free proof net. A key role is played by the notion of history-free strategy; strong connections are made between history-free strategies and the Geometry of Interaction. Our semantics incorporates a natural notion of polarity, leading to a refined treatment of the additives. We make comparisons with related work by Joyal, Blass, et al.

Information

Type
Research Article
Copyright
Copyright © Association for Symbolic Logic 1994

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable