A System of Interaction and Structure V: The Exponentials and Splitting - Inria - Institut national de recherche en sciences et technologies du numérique Access content directly
Preprints, Working Papers, ... Year : 2009

A System of Interaction and Structure V: The Exponentials and Splitting

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.
Fichier principal
Vignette du fichier
NEL-splitting.pdf (311.33 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

inria-00441254 , version 1 (15-12-2009)
inria-00441254 , version 2 (28-01-2015)

Identifiers

  • HAL Id : inria-00441254 , version 1

Cite

Alessio Guglielmi, Lutz Strassburger. A System of Interaction and Structure V: The Exponentials and Splitting. 2009. ⟨inria-00441254v1⟩
373 View
289 Download

Share

Gmail Facebook X LinkedIn More