Alexis Saurin (IRIF), Linear logic with fixed points and infinitary proofs, from straight threads to bouncing threads

Schedule

Abstract

Infinitary and circular 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 under-developed. In particular, 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. In this talk, we consider the infinitary proof system μMALL∞ for multiplicative and additive linear logic extended with least and greatest fixed points, and prove these two key results. We thus establish μMALL∞ as a satisfying computational proof system in itself, rather than just an intermediate device in the study of finitary proof systems. In the last part of the talk, we will discuss some ongoing work on relaxing the validity condition for infinitary proofs and therefore accepting more proofs. This is motivated by the fact that usual validity conditions only consider straight threads -- progressing from conclusion to premise. While natural in the cut-free setting, it is quite restrictive in presence of cut. This is joint work with Baelde, Doumane and Jaber.