From Syntactic Proofs to Combinatorial Proofs

Matteo Acclavio (1, 2, 3) , Lutz Strassburger (1, 2, 3)

1 Inria Saclay - Ile de France
2 PARSIFAL - Proof search and reasoning with logic specifications
3 LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau]

In this paper we investigate Hughes’ combinatorial proofs as a notion of proof identity for classical logic. We show for various syntactic formalisms including sequent calculus, analytic tableaux, and resolution, how they can be translated into combinatorial proofs, and which notion of identity they enforce. This allows the comparison of proofs that are given in different formalisms.

Domaines: Logique en informatique [cs.LO]

Matteo Acclavio, Lutz Strassburger. From Syntactic Proofs to Combinatorial Proofs. International Joint Conference on Automated Reasoning, IJCAR 2018, Springer, pp.481-497, 2018, 978-3-319-94204-9. ⟨hal-01942275⟩