E Prover

E Prover
Name	E Prover
Developer	Sergei Jakubík; Radboud University; University of Innsbruck
Released	1993 (approx.)
Operating system	Unix-like; Windows
License	GPL

E Prover is an automated theorem prover for first-order logic with equality. It is a high-performance implementation used in automated reasoning, formal verification, and mathematical proof search, integrating saturation-based methods with extensive heuristic control. E Prover is widely used in competitions, research, and industrial verification projects.

Overview

E Prover implements saturation-based proving strategies derived from resolution and superposition, drawing on techniques developed in the research communities around Alan Robinson, Brookhaven National Laboratory, Herbrand, Gordon Plotkin, John McCarthy, Alonzo Church, Kurt Gödel, and Alfred Tarski. It is often compared with provers such as Vampire (theorem prover), SPASS, Prover9, Z3 Theorem Prover, CVC4, CVC5, Lean (proof assistant), Coq, Isabelle (proof assistant), HOL Light, and ACL2. E Prover participates in the CADE ATP System Competition and contributes to projects like TPTP (Thousands of Problems for Theorem Provers), SMT-LIB, Mizar, Metamath, and Flyspeck. Its development has ties to institutions like Radboud University Nijmegen, University of Innsbruck, Technical University of Munich, University of Manchester, and University of New South Wales.

History and Development

Development traces to work in automated reasoning groups influenced by researchers at SRI International, M.I.T., Princeton University, Stanford University, University of Cambridge, and University of Edinburgh. Key contributors include Sergei Jakubík, with collaborations involving researchers affiliated with NWO, European Research Council, DFG (German Research Foundation), and projects funded by the European Union. E Prover evolved through iterative improvements influenced by results from conferences such as CADE (Conference on Automated Deduction), IJCAR (International Joint Conference on Automated Reasoning), CADE-27, FLoC (Federated Logic Conference), and workshops at CAV (Computer Aided Verification). Historical influences include saturation theorem provers from the 1970s and algorithmic ideas from resolution pioneers and equality handling from Knuth–Bendix completion approaches.

Architecture and Features

E Prover's core architecture centers on a saturation loop implementing variant strategies of the given-clause algorithm, incorporating literal selection, term indexing, and efficient data structures. It uses clause simplification, subsumption, demodulation, and ordering techniques informed by Knuth, Bendix, Herbrand, and proof normalization studies. Feature highlights include support for ordered paramodulation, subsumption-based simplifiers, extensive heuristic scheduling, proof reconstruction output, and integration hooks for tactics from systems like Isabelle (proof assistant) and Coq. The implementation emphasizes performance, using optimized memory management and indexing structures inspired by work at SRI International and IBM Research.

Input Languages and Formats

E Prover accepts input in formats compatible with the TPTP (Thousands of Problems for Theorem Provers) library, using FOF (first-order form), CNF (conjunctive normal form), and TFF (typed first-order form). It interfaces with benchmarks and problem sets originating from Mizar Mathematical Library, HOL Light, Metamath, and Isabelle (proof assistant) exports, and participates in translations to and from the SMT-LIB standard via frontends. The tool can parse problems prepared by systems such as Otter, Prover9, and formats used in CADE competitions.

Inference Techniques and Algorithms

E Prover implements superposition-based inference, resolution, equality reasoning via paramodulation, and clause-selection heuristics inspired by the given-clause algorithm of Alan Robinson. It employs term indexing strategies like discrimination trees and fingerprint indexing, influenced by indexing research from Uppsala University and University of Oxford groups. Additional algorithmic techniques include literal selection functions, age-weight combinations, simplification ordering such as KBO and LPO, and proof-object generation enabling reconstruction in assistants like Isabelle (proof assistant). Heuristics and strategy scheduling have been refined using machine learning and strategy configuration approaches demonstrated in MaLARea, ENIGMA, and competitions like CASC.

Performance and Benchmarks

E Prover's performance is regularly evaluated on benchmark suites such as TPTP (Thousands of Problems for Theorem Provers), competition tracks in CADE ATP System Competition, and problem collections from Mizar, Flyspeck, and SMT-LIB. Results are compared against systems such as Vampire (theorem prover), SPASS, Prover9, Z3 Theorem Prover, CVC4, and E theorem prover competitors. Published evaluations appear in proceedings of CADE, IJCAR, SAT Conference, and CAV, demonstrating strengths on first-order problems with equality and in applications requiring produced proofs suitable for reconstruction in systems like Isabelle (proof assistant) and Coq.

Integrations and Applications

E Prover is integrated into proof environments and verification toolchains for formalizations from Mizar Mathematical Library, Isabelle (proof assistant), Coq, HOL Light, and projects such as Flyspeck. It is used in software verification projects at organizations like Google, Microsoft Research, Amazon Web Services, and research groups at Radboud University Nijmegen and University of Innsbruck. Applications include automated proof search in formal mathematics, model checking workflows at ETH Zurich and MPI-SWS, and as a backend for systems participating in CASC and CADE evaluations. Advanced users combine E Prover with learning-guided strategies from projects like ENIGMA and pipeline tools such as Sledgehammer.

Category:Automated theorem provers