mrs-proover 0.2.0

Olivier Roland
Independent, France

Overview

mrs-proover 0.2.0 is introduced in this section. mrs-proover is a proof checker for TSTP first-order refutation proofs, built as a companion to the mrs automated theorem prover [Sut06]. It follows the semantic verification paradigm pioneered by GDV: structural properties of the proof DAG are checked first (uniqueness of formula names, acyclicity, a single $false root), followed by leaf verification against the linked problem file, followed by per-step verification of each inference.

A small set of inference patterns that are expected to recur in every proof — the negated-conjecture step, and Skolemization steps — are verified internally using dedicated structural checks rather than external provers, since these steps have precisely specified shapes (see the ProoVer Rules and Format page). Axiom and conjecture leaves are checked for alpha-equivalence against the named formula in the linked problem file, either internally or, when internal matching fails, by delegating to an external ATP. All other inference steps with status thm or cth are discharged as proof obligations to an ATP ladder.

mrs-proover reports Unknown (rather than guessing) whenever neither a positive nor a negative verdict can be established within the allotted resources for a given step; because the ProoVer scoring penalizes a false VerifiedGood on a bad proof ten times more heavily than a missed detection, the overall verdict policy is deliberately conservative: any single step found unsound anywhere in the proof yields VerifiedBad for the whole proof; otherwise any step left undecided yields Unknown; only if every step is positively confirmed does the proof yield VerifiedGood.

Implementation

mrs-proover is implemented in Rust (edition 2024), reusing the mrs TPTP/TSTP parser, clausifier, and unification/formula-lowering crates from the same workspace. The proof is loaded and its dependency structure is represented as a directed acyclic graph over annotated formulae; formulae are lowered from the TPTP AST into the shared mrs-core term/formula representation for alpha-equivalence and structural comparisons.

For inference steps that cannot be settled by the internal structural checks, mrs-proover discharges the corresponding proof obligation (parent formulae as axioms, inferred formula as conjecture) to an ATP ladder that runs, per step, the in-process mrs prover first, then races any available external backends — E [Sch02] and Vampire [KV13] — in parallel; the first definite Sound/Unsound verdict from any ladder member wins and the remaining subprocesses for that step are cancelled. Steps can be verified concurrently across multiple CPU cores (default 8, matching the competition hardware).

mrs-proover has been cross-checked, using only its internal mrs backend (no external ATPs), against the 7 official ProoVer example proofs, against the leoprover/noergler PyRes correctness corpus (170 valid proofs, 170 corresponding falsified/mutated proofs), and against the ATP-Research-Project test corpus of correct and deliberately "evil" proofs. Across all of these, running the in-process backend alone never produced a false VerifiedGood on an evil proof and never produced a false VerifiedBad on a valid proof; adding the external E/ Vampire backends only improves detection rate (fewer proofs left at Unknown), never soundness.

mrs-proover is open source (MIT OR Apache-2.0) and available from:

    https://github.com/newca12/mrs

as the mrs-proover crate in the same repository as the mrs ATP system.

Expected Competition Performance

mrs-proover is expected to correctly identify almost all well-formed valid proofs as VerifiedGood and almost all deliberately incorrect ("evil") proofs as VerifiedBad, given the internal structural checks tailored to the exact Skolemization and negated-conjecture formats specified by the ProoVer rules, backed by external ATP calls for the remaining steps. Given the highly asymmetric scoring (a single false VerifiedGood on an evil proof costs as much as ten correct verifications), mrs-proover is tuned to prefer reporting Unknown over guessing whenever a step cannot be positively confirmed or refuted within the time budget, so a non-trivial fraction of harder or unusually-shaped valid proofs may be conservatively scored 0 rather than +1.

References

Sut06: Sutcliffe G. (2006), Semantic Derivation Verification, International Journal on Artificial Intelligence Tools 15(6), pp.1053-1070, World Scientific.
Sch02: Schulz S. (2002), E: A Brainiac Theorem Prover, AI Communications 15(2-3), pp.111-126, IOS Press.
KV13: Kovács L., Voronkov A. (2013), First-Order Theorem Proving and Vampire, Sharygina N., Veith H., Computer Aided Verification (CAV 2013) (Saint Petersburg, Russia), pp.1-35, LNCS 8044, Springer.