Relating Natural Deduction and Sequent Calculus for Intuitionistic Non-Commutative Linear Logic
✍ Scribed by Jeff Polakow; Frank Pfenning
- Publisher
- Elsevier Science
- Year
- 1999
- Tongue
- English
- Weight
- 851 KB
- Volume
- 20
- Category
- Article
- ISSN
- 1571-0661
No coin nor oath required. For personal study only.
✦ Synopsis
We present a sequent calculus for intuitionistic non-commutative linear logic (INCLL), show that it satisfies cut elimination, and investigate its relationship to a natural deduction system for the logic. We show how normal natural deductions correspond to cut-free derivations, and arbitrary natural deductions to sequent derivations with cut. This gives us a syntactic proof of normalization for a rich system of non-commutative natural deduction and its associated (\lambda)-calculus. INCLL conservatively extends linear logic with means to express sequencing, which has applications in functional programming, logical frameworks, logic programming, and natural language parsing.