Passer à la navigation principale Passer à la recherche Passer au contenu principal

A system of interaction and structure V: The exponentials and splitting

  • University of Bath, Department of Computer Science

Résultats de recherche: Contribution à un journalArticleRevue par des pairs

Résumé

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. NEL is presented in deep inference, because no Gentzen formalism can express it in such a way that the cut rule is admissible. Other recent work shows that system NEL is Turing-complete, and is able to express process algebra sequential composition directly and model causal quantum evolution faithfully. In this paper, we show cut elimination for NEL, based on a technique that we call splitting. The splitting theorem shows how and to what extent we can recover a sequent-like structure in NEL proofs. When combined with a decomposition theorem, proved in the previous paper of this series, splitting yields a cut-elimination procedure for NEL.

langue originaleAnglais
Pages (de - à)563-584
Nombre de pages22
journalMathematical Structures in Computer Science
Volume21
Numéro de publication3
Les DOIs
étatPublié - 1 janv. 2011

Empreinte digitale

Examiner les sujets de recherche de « A system of interaction and structure V: The exponentials and splitting ». Ensemble, ils forment une empreinte digitale unique.

Contient cette citation