Lamarche, Francois and Strassburger, Lutz - From Proof Nets to the Free *-Autonomous Category

lmcs:2239 - Logical Methods in Computer Science, October 5, 2006, Volume 2, Issue 4
From Proof Nets to the Free *-Autonomous Category

Authors: Lamarche, Francois and Strassburger, Lutz

In the first part of this paper we present a theory of proof nets for full multiplicative linear logic, including the two units. It naturally extends the well-known theory of unit-free multiplicative proof nets. A linking is no longer a set of axiom links but a tree in which the axiom links are subtrees. These trees will be identified according to an equivalence relation based on a simple form of graph rewriting. We show the standard results of sequentialization and strong normalization of cut elimination. In the second part of the paper we show that the identifications enforced on proofs are such that the class of two-conclusion proof nets defines the free *-autonomous category.


Source : oai:arXiv.org:cs/0605054
DOI : 10.2168/LMCS-2(4:3)2006
Volume: Volume 2, Issue 4
Published on: October 5, 2006
Submitted on: November 4, 2005
Keywords: Computer Science - Logic in Computer Science,F.4.1


Share

Consultation statistics

This page has been seen 38 times.
This article's PDF has been downloaded 12 times.