CADE-28: THE 28TH INTERNATIONAL CONFERENCE ON AUTOMATED DEDUCTION
PXTP-7 ON SUNDAY, JULY 11TH

View: session overviewtalk overviewside by side with other conferences

09:00-10:00 Session 3: PxTP Workshop: Certifying Transformations
Location: ZoomRoom 2
09:00
A Framework for Proof-Carrying Logical Transformations

ABSTRACT. In various provers and deductive verification tools, logical transformations are used extensively in order to reduce a proof task into a number of simpler tasks. Logical transformations are often part of the trusted base of such tools. In this paper, we develop a framework to improve confidence in their results. We follow a modular and skeptical approach: transformations are instrumented independently of each other and produce certificates that are checked by a third-party tool. Logical transformations are considered in a higher-order logic, with type polymorphism and built-in theories such as equality and integer arithmetic. We develop a language of proof certificates for them and use it to implement the full chain of certificate generation and certificate verification.

09:30
General Automation in Coq through Modular Transformations

ABSTRACT. Whereas proof assistants based on Higher-Order Logic benefit of automation from external solvers, those based on Type Theory resist automation and thus require more expertise. Indeed, the latter is a more expressive logic which is further from first-order logic, the logic of most automatic theorem provers. In this article, we develop a methodology to transform a subset of Coq goals into first-order statements that can be automatically discharged by automatic provers. The general idea is to write modular, pairwise independent transformations and combine them. Each of these eliminates a specific aspect of Coq logic towards first-order logic. As a proof of concept, we apply this methodology to a set of simple but crucial transformations which extend the local context with proven first-order assertions that make Coq definitions and algebraic types explicit. They allow users of Coq to solve non-trivial goals automatically. This methodology paves the way towards the definition and combination of more complex transformations, making Coq more accessible.

10:00-10:30Break
10:30-11:30 Session 4D: PxTP Workshop: Invited Talk
Location: ZoomRoom 2
10:30
Reasoning in Many Logics with Vampire: Everything's CNF in the End
11:30-12:30 Session 5: PxTP Workshop: Use Cases
Location: ZoomRoom 2
11:30
Integrating an Automated Prover for Projective Geometry as a New Tactic in the Coq Proof Assistant (extended abstract)

ABSTRACT. Recently, we developed an automated theorem prover for projective incidence geometry. This prover, based on a combinatorial approach using matroids, proceeds by saturation using the matroid rules. It is designed as an independent tool, implemented in C, which takes a geometric configuration as input and produces as output some Coq proof scripts: the statement of the expected theorem, a proof script proving the theorem and possibly some auxiliary lemmas. In this document, we show how to embed such an external tool as a plugin in Coq so that it can be used as a simple tactic.

12:00-12:30Break
12:30-13:10 Session 6D: PxTP Workshop: Generating and Using Proofs
Location: ZoomRoom 2
12:30
Certifying CNF Encodings of Pseudo-Boolean Constraints (extended abstract)

ABSTRACT. The dramatic improvements in Boolean satisfiability (SAT) solving since the turn of the millennium have made it possible to leverage state-of-the-art conflict-driven clause learning (CDCL) solvers for many combinatorial problems in academia and industry, and the use of proof logging has played a crucial role in increasing the confidence that the results these solvers produce are correct. However, the conjunctive normal form (CNF) format used for SAT proof logging means that it is hard to extend the method to other, stronger, solving paradigms for combinatorial problems. We show how to instead leverage the cutting planes proof system to provide proof logging for pseudo-Boolean solvers that translate pseudo-Boolean problems (a.k.a 0-1 integer linear programs) to CNF and run CDCL. We are hopeful that this is just a first step towards providing a unified proof logging approach that will also extend to maximum satisfiability (MaxSAT) solving and pseudo-Boolean optimization in general.

12:50
Alethe: Towards a Generic SMT Proof Format (Extended Abstract)

ABSTRACT. The first iteration of the proof format used by the SMT solver veriT was presented ten years ago at the first PxTP workshop. Since then the format has matured. veriT proofs are used within multiple applications, and other solvers generate proofs in the same format. Now we would like to gather feedback from the community to guide future developments. Towards this, we review the history of the format, present our pragmatic approach to develop the format, and also discuss problems that may arise when other solvers use the format.

14:00-14:30Break