The Fine Structure of Formal Proof Systems and their Computational Interpretations
This is a joint project between Austria and France represented by the following institutions:
- University of Innsbruck
- Vienna University of Technology
- Université Paris Diderot
- INRIA Saclay — Ile-de-France
The project is carried out by a consortium of four partners, two Austrian and two French, all being internationally recognised for their work on structural proof theory, but each coming from a different tradition. One tradition originates in mathematics and is mainly concerned with first-order logic, and studies Hilbert’s epsilon calculus, Herbrand’s theorem, and Gödel’s Dialectica interpretation. A second tradition, originating in computer science, is mainly concerned with propositional systems, and studies Curry-Howard correspondence, algebraic semantics, linear logic, proof nets, and deep inference. A common ground is the role played by analytic proofs and the notion of cut-elimination.
The FISP project is part of a long-term, ambitious project whose objective is to apply the powerful and promising techniques from structural proof theory to central problems in computer science for which they have not been used before, especially the understanding of the computational content of proofs, the extraction of programs from proofs and the logical control of refined computational operations. So far, the work done in the area of computational interpretations of logical systems is mainly based on the seminal work of Gentzen, who in the mid-thirties introduced the sequent calculus and natural deduction, along with the cut-elimination procedure. But that approach reveals its limits when it comes to computational interpretations of classical logic or the modelling of parallel computing. The aim of our project, based on the complementary skills of the teams, is to overcome these limits. For instance, deep inference provides new properties, namely full symmetry and atomicity, which were not available until recently and opened new possibilities at the computing level, in the era of parallel and distributed computing.
Duration: 3 years
Start of Project: January 1, 2016
Meetings
- Kick-Off Meeting, November 15 – 17, 2016, Innsbruck, Austria
- 2nd FISP Meeting , August 22—27 in Funchal, Madeira
- 3rd and Final FISP Meeting, December~7 to~8, 2018, Vienna, Austria
Members
The project is coordinated by
- Georg Moser (coordinator Austria)
- Matthias Baaz
- Michel Parigot (coordinator France)
- Lutz Straßburger
The node Innsbruck consists of
- Georg Moser
- Kenji Miyamoto