Constructive Logics. Part II: Linear Logic and Proof Nets
Jean H. Gallier · ScholarlyCommons (University of Pennsylvania) · 1991
. The purpose of this paper is to give an exposition of material dealing with constructive logics, typed -calculi, and linear logic. The first part of this paper gives an exposition of background material (with a few exceptions). This second part is devoted to linear logic and proof nets. Particular attention is given to the algebraic semantics (in Girard's terminology, phase semantics) of linear logic. We show how phase spaces arise as an instance of a Galois connection. We also give a direct proof of the correctness of the Danos-Regnier criterion for proof nets. This proof is based on a purely graph-theoretic decomposition lemma. As a corollary, we give an O(n 2 )-time algorithm for testing whether a proof net is correct. Although the existence of such an algorithm has been announced by Girard, our algorithm appears to be original. This research was partially supported by ONR Grant NOOO14-88-K-0593. Contents 1 Core Linear Logic and Propositional Linear Logic 3 2 Representing I...