Certified grounding with CertiFOX

Peiran Wu (KU Leuven)

Tue Nov 17, 14:00-15:00 (starts in 13 hours)

Abstract: The ground-and-solve strategy, where high-level theories are first translated into equivalent or equisatisfiable quantifier-free formulas, is an important method in declarative problem solving. While proof formats like DRAT and VeriPB exist for certifying results of SAT and pseudo-Boolean solvers, a trust gap remains for the grounding step of the strategy. Without certificates for grounding, one cannot be sure that the ground formulas produced by the grounder and passed to the solver – let alone the solutions – actually correspond to the original problem specification.

In this talk, I will present CertiFOX, a novel certifying grounding framework for first-order logic model expansion (FOX) over finite domains. Central to the framework is a proof system we are developing for grounding derivations. Our tool suite includes GroundFOX, a proof-logging grounder, and CheckFOX, a proof-log checker. Also in active development is LeanFOX, a formally verified checker implemented independently in Lean. LeanFOX provides stronger guarantees for the soundness of the proof system and the correctness of verified proof logs. I will demonstrate how the grounder and checkers work and share some discoveries we made while implementing LeanFOX.

Mathematics

Audience: researchers in the topic


ANTLR seminar

Series comments: This is the Algebra, Number Theory, Logic and Representation theory seminar.

Organizer: Marie Roth
Curator: Lorna Gregory*
*contact for this listing

Export talk to