Proof theory is the study of formal proofs as mathematical objects in their own right. The subject has enjoyed continued attention among computer scientists in particular due to its significance for formalization, metalogic, and automation. In recent decades there has been a surge of interest on the representations of formal proofs themselves. The outcomes of these investigations have been remarkable, in particular extending the scope of structural proof theory to novel and richer settings:

• Richer line structures (e.g. hypersequents, nested sequents, labelled sequents) have resulted in a uniform treatment of standard modal logics, streamlining their metatheory and providing new tools for metalogical problems.
• Richer proof structures (e.g., cyclic proofs, annotated systems, infinitely branching proofs) have significantly advanced our understanding of fixed points and (co)induction. Indeed, we are now seeing many of these previously disjoint techniques being combined to push the boundaries of proof theoretic approaches to computational logic.
• Graphical proof representations (e.g., proof nets, atomic flows, combinatorial proofs) originating from “linear” logics, now not only comprise a well-behaved computational model for resource-sensitive reasoning, but also provide an impressively uniform treatment for logics across the board.

In fact, we are now seeing many of these previously disjoint techniques being combined to push the boundaries of proof theoretic approaches to computational logic, which has produced deep and fruitful cross-fertilizations between programming languages and proof theory. Arguably, the most well-known is the Curry-Howard correspondence (“propositions-as-types”) where (functional) programs correspond to formal proofs and their execution to normalization. A complementary tradition, proof-search-as-computation (“propositions-as-processes”), instead interprets (logic) programs to formulas and their execution to proof search.

The point of this Dagstuhl Seminar is twofold. First and foremost, we want to bring together theorists and practitioners exploiting proof representations to identify new directions of application and, simultaneously, distill new theoretical directions from problems “in the wild”. At the same time, this seminar will expose the interface between the proof-normalization and proof-search traditions by probing proof representations from both directions.

Creative Commons BY 4.0

Carlos Areces, Anupam Das, Elaine Pimentel, and Lutz Straßburger