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:

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

Members

The project is coordinated by

The node Innsbruck consists of

FWF “International Cooperation Project” project number project number

I 2671-N35

Contact

georg moser at uibk dot ac dot at

Publications