A Semantic Framework for Proof Evidence

Zakaria Chihani 1 Dale Miller 1, 2 Fabien Renaud 1
1 PARSIFAL - Proof search and reasoning with logic specifications
LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau], Inria Saclay - Ile de France
Abstract : Theorem provers produce evidence of proof in many different formats, such as proof scripts, natural deductions, resolution refutations, Herbrand expansions, and equational rewritings. In implemented provers, numerous variants of such formats are actually used: consider, for example, such variants of or restrictions to resolution refu-tations as binary resolution, hyper-resolution, ordered-resolution, paramodulation, etc. We propose the foundational proof certificates (FPC) framework for defining the semantics of a broad range of proof evidence. This framework allows both producers of proof certificates and the checkers of those certificates to have a clear formal definition of the semantics of a wide variety of proof evidence. Employing the FPC framework will allow one to separate a proof from its provenance and to allow anyone to construct their own proof checker for a given style of proof evidence. The foundation on which FPC relies is that of proof theory, particularly recent work into focused proof systems: such proof systems provide protocols by which a checker extracts information from the certificate (mediated by the so called clerks and experts) as well as performs various deterministic and non-deterministic computations. While we shall limit ourselves to first-order logic in this paper, we shall not limit ourselves in many other ways. The FPC framework is described for both classical and intuitionistic logics and for proof structures as diverse as resolution refutations, natural deduction, Frege proofs, and equality proofs.
Type de document :
Article dans une revue
Journal of Automated Reasoning, Springer Verlag, 2017, 59 (3), pp.287-330. 〈10.1007/s10817-016-9380-6〉
Liste complète des métadonnées

Littérature citée [85 références]  Voir  Masquer  Télécharger

Contributeur : Dale Miller <>
Soumis le : mercredi 2 novembre 2016 - 15:48:14
Dernière modification le : mercredi 14 novembre 2018 - 16:14:01
Document(s) archivé(s) le : vendredi 3 février 2017 - 14:07:13


Fichiers produits par l'(les) auteur(s)



Zakaria Chihani, Dale Miller, Fabien Renaud. A Semantic Framework for Proof Evidence. Journal of Automated Reasoning, Springer Verlag, 2017, 59 (3), pp.287-330. 〈10.1007/s10817-016-9380-6〉. 〈hal-01390912〉



Consultations de la notice


Téléchargements de fichiers