TL;DR
This paper introduces SC-TPTP, a new format for representing proofs in sequent-based calculi, designed to bridge the gap between automated theorem provers (ATPs) and interactive theorem provers (ITPs). By extending the widely-used TPTP format with detailed sequent-style inference steps, SC-TPTP aims to facilitate the transfer of proofs between diverse tools, making them more verifiable and interoperable.
What Problem Does This Paper Address?
The core challenge this paper tackles is the difficulty of transferring proofs between different automated and interactive theorem proving systems. While many systems might share similar logical foundations, their internal proof representations and the granularity of their inference steps can vary significantly. This heterogeneity makes it hard for one system to understand or utilize proofs generated by another. For instance, an ATP might use advanced, high-level steps like Skolemization or congruence closure, which are difficult to translate into the more basic, step-by-step proofs typically accepted by proof assistants. This leads to a combinatorial explosion of custom import/export mechanisms needed for each pair of systems. The authors propose a common, detailed proof format as a solution to this interoperability problem.
Methods
The paper introduces SC-TPTP, a new proof derivation format that acts as a "super specification" of the existing TPTP format. The key innovation is the detailed representation of sequent-calculus style proofs. SC-TPTP defines a set of inference rules, categorized into three levels:
- Level 1: These are basic, low-level inference rules (structural, introduction rules for logical connectives, negation, quantifiers, and equality) that are designed to be easily verifiable and directly translatable into many proof systems. They are based on both one-sided and two-sided sequent calculus, and are also suitable for tableaux-based proofs.
- Level 2: These are more advanced, tool-specific proof steps (like congruence closure) that are more difficult to verify directly but come with procedures to be transformed into Level 1 steps.
- Level 3 (implied): The paper mentions that Level 2 steps are expected to expand over time, suggesting a potential for further levels of abstraction.
The format uses the TPTP FOFX grammar to represent formulas and sequents, and annotations within the derivation steps specify the rule used, its parameters (like indices, terms, or variables), and the premises it refers to. The authors also developed a library of utilities in Scala to parse, print, verify, and transform SC-TPTP proofs, including exporting them to Coq.
Datasets
Not discussed in the paper. The paper focuses on a proof format and its utility, rather than on training or evaluating models on specific datasets.
Key Insights and Ideas
- Bridging the ATP-ITP Divide: The primary insight is that a standardized, detailed proof format like SC-TPTP can act as a crucial intermediary for proof exchange between ATPs and ITPs, significantly reducing the complexity of integration.
- Leveraging Existing Standards: By building upon the TPTP format, SC-TPTP benefits from existing parsers and tools, making adoption easier. The FOFX grammar is extended to support sequents.
- Hierarchical Proof Representation: The multi-level approach (Level 1 for basic, verifiable steps; Level 2 for advanced, transformable steps) is key. This allows tools to leverage high-level proofs from ATPs while still being able to reconstruct them into low-level, verifiable steps for ITPs.
- Sequent Calculus as a Common Ground: The choice of sequent calculus provides a natural and well-understood framework that aligns well with many theorem provers and proof assistants, especially those using tableaux methods.
- The "Proof Holes" Concept for Coq: The paper highlights how translating sequent calculus rules into Coq, which is intuitionistic, requires careful handling of hypotheses and conclusions, sometimes leading to proofs with "holes" that need to be filled later.
Key Results
- SC-TPTP Format Defined: The paper formally defines the SC-TPTP format, including its syntax and semantics for Level 1 inference rules.
- SC-TPTP Utilities Library: A publicly available library in Scala is developed to parse, print, verify, and transform SC-TPTP proofs. This includes a tool to export SC-TPTP proofs to Coq.
- Integration with Goéland and Lisa: The SC-TPTP format has been implemented in the Goéland ATP (for export) and the Lisa proof assistant (for import), demonstrating its practical utility for proof transfer.
- Elimination of Congruence Steps: An algorithm is implemented to unfold Level 2 congruence steps into simpler substitution steps using e-graphs, making advanced proofs more amenable to verification.
- Example Proofs: The paper provides concrete examples of SC-TPTP derivations for logical formulas and the drinker paradox, as well as their translation into Coq.
Limitations and Future Work
- Limited Level 2 Rules: Currently, only a few Level 2 rules (simultaneous substitution, congruence closure) are implemented. The authors anticipate expanding this set.
- Community Adoption: The success of SC-TPTP hinges on its adoption by the broader theorem proving community.
- Expansion to Other Logics and Calculi: Future work includes supporting typed first-order logic, connection calculus, and potentially resolution-based proofs.
- Theory Reasoning: Integrating theory-specific rules as high-level proof steps is a planned extension.
- Deskolemization: Implementing deskolemization as a proof step is also considered.
- Export to Other Proof Assistants: The authors plan to extend their export capabilities to other proof assistants like Lambdapi, Isabelle, and Lean.
- TPTP Syntax Limitations: The authors identify limitations in the current TPTP syntax (e.g., for n-ary conjunctions/disjunctions, identifiers) and plan to propose refinements.
Summary updated