GAPT (General Architecture for Proof Theory) [GAPT] is a framework containing many data structures, algorithms, parsers and other components common in proof theory and automated deduction. As such it implements various proof calculi, including LK proofs and resolution proofs.
The main idea of the GAPT proof checker is to attempt to import a given TSTP derivation as an acyclic directed graph of LK proofs which can then combined into a compact representation of an LK proof of a sequent whose antecedent contains input axioms and the negation of the input conjecture and whose succeedent contains $false. As a pre-pass GAPT performs other auxiliary checks like checking that the axiom file directives are correct. To check semantic entailment of plain inferences GAPT uses its internal superposition prover Escargot.
GAPT returns VerifiedBad if any of the checks fail, or any internal proof invariant is violated. If checking takes longer than the given time limit, GAPT returns Timeout. If an unexpected situation occurs (e.g. input syntax error, or unexpected exception thrown), GAPT returns Unknown. Otherwise, GAPT returns VerifiedGood.
The checker not only outputs the SZS status, but in case of VerifiedBad it also gives a more detailed message as to what went wrong. For example, if Escargot can establish that a plain inference is incorrect, the checker outputs the step name of the incorrect inference.
The approach of importing the TSTP derivation as an LK proof allows, in principle, to compute a more elaborated version of the TSTP derivation that requires no external ATP tools to check anymore.
GAPT is implemented in Scala. It uses parboiled2 as a parsing library to parse the TPTP format. The internal superposition prover Escargot is used for checking plain inferences, so GAPT does not depend on an external ATP tool for proof checking.
The proof checking proceeds in the following way: First the input file is parsed in the TPTP format. Then the file is checked for unique formula names and for acyclicity of the derivation. Next, auxiliary checks are performed to ensure all steps have valid statuses and the file directives in axioms and conjectures are correct. Now, each step is assigned a first-order sequent where the step's parents' formulas are in the antecedent and the step's formula is in the succeedent. For plain inference steps an attempt is made to find an LK proof for this sequent by using the internal superposition prover Escargot. For skolemization inference steps an LK proof for the sequent is constructed using a special skolemization LK rule. For negated conjecture steps an attempt is made to find an LK proof for both the if and only if direction of negation(conjecture) iff negated_conjecture. To make sure that skolem symbols are used appropriately across all inferences, e.g., the same skolem symbol is not used for different skolemized formulas, an additional check is performed across the whole derivation. Finally, for each step, LK cuts between the step's proofs and the step's parents' proofs are applied which results in LK proofs whose antecedents contain axioms and the negation of the conjecture from the input file and whose succeedent contains the formula of the given step. This results in a compact representation of the LK proof of the input refutation, i.e., an LK proof of the sequent whose antecedent consists of input axioms and the negation of the conjecture and whose succeedent consists of $false. This representation avoids unfolding the whole LK proof into a tree and instead saves space by remaining a directed acyclic graph.
GAPT is available at:
https://www.logic.at/gapt/
We expect GAPT to be sound, but as this is the first version of the GAPT derivation checker we don't expect fast results. It might struggle to verify long derivations or difficult plain inferences, since Escargot works very well on small examples, but is likely not able to compete with state-of-the art resolution provers in this area. However, GAPT should be able to handle most reasonably granular input derivations correctly and we expect to receive few negative points.