Baelde, David ;
Doumane, Amina ;
Saurin, Alexis
Infinitary Proof Theory: the Multiplicative Additive Case
Abstract
Infinitary and regular proofs are commonly used in fixed point logics. Being natural intermediate devices between semantics and traditional finitary proof systems, they are commonly found in completeness arguments, automated deduction, verification, etc. However, their proof theory is surprisingly underdeveloped. In particular, very little is known about the computational behavior of such proofs through cut elimination. Taking such aspects into account has unlocked rich developments at the intersection of proof theory and programming language theory. One would hope that extending this to infinitary calculi would lead, e.g., to a better understanding of recursion and corecursion in programming languages. Structural proof theory is notably based on two fundamental properties of a proof system: cut elimination and focalization. The first one is only known to hold for restricted (purely additive) infinitary calculi, thanks to the work of Santocanale and Fortier; the second one has never been studied in infinitary systems. In this paper, we consider the infinitary proof system muMALLi for multiplicative and additive linear logic extended with least and greatest fixed points, and prove these two key results. We thus establish muMALLi as a satisfying computational proof system in itself, rather than just an intermediate device in the study of finitary proof systems.
BibTeX  Entry
@InProceedings{baelde_et_al:LIPIcs:2016:6582,
author = {David Baelde and Amina Doumane and Alexis Saurin},
title = {{Infinitary Proof Theory: the Multiplicative Additive Case}},
booktitle = {25th EACSL Annual Conference on Computer Science Logic (CSL 2016)},
pages = {42:142:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770224},
ISSN = {18688969},
year = {2016},
volume = {62},
editor = {JeanMarc Talbot and Laurent Regnier},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6582},
URN = {urn:nbn:de:0030drops65825},
doi = {10.4230/LIPIcs.CSL.2016.42},
annote = {Keywords: Infinitary proofs, linear logic}
}
2016
Keywords: 

Infinitary proofs, linear logic 
Seminar: 

25th EACSL Annual Conference on Computer Science Logic (CSL 2016)

Issue date: 

2016 
Date of publication: 

2016 