A System of Interaction and Structure V: The Exponentials and SplittingReport as inadecuate

A System of Interaction and Structure V: The Exponentials and Splitting - Download this document for free, or read online. Document in PDF available to download.

1 CALLIGRAMME - Linear logic, proof networks and categorial grammars INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications 2 PARSIFAL - Proof search and reasoning with logic specifications LIX - Laboratoire d-informatique de l-École polytechnique Palaiseau, Inria Saclay - Ile de France, Polytechnique - X, CNRS - Centre National de la Recherche Scientifique : UMR7161

Abstract : System NEL is the mixed commutative-non-commutative linear logic BV augmented with linear logic-s exponentials, or, equivalently, it is MELL augmented with the non-commutative self-dual connective seq. System NEL is Turing-complete, it is able to directly express process algebra sequential composition and it faithfully models causal quantum evolution. In this paper, we show cut elimination for NEL, based on a property that we call splitting. NEL is presented in the calculus of structures, which is a deep-inference formalism, because no Gentzen formalism can express it analytically. The splitting theorem shows how and to what extent we can recover a sequent-like structure in NEL proofs. Together with the decomposition theorem, proved in the previous paper of the series, this immediately leads to a cut-elimination theorem for NEL.

Author: Alessio Guglielmi - Lutz Straßburger -

Source: https://hal.archives-ouvertes.fr/


Related documents