As substitutions need to apply to an entire proof tree the system only represents each variable once and shares the representation, simultaneously maintaining a stack of substitutions making removal of substitutions under backtracking trivial. It also creates subterms only once and shares them; these are indexed allowing constant-time lookup, and nothing is ever removed from the index, meaning that if a term is constructed again after its initial construction no new memory allocation takes place and the term itself is obtained in constant time. At the same time, fresh copies of variables are recycled under backtracking - these two design choices appear to interact very effectively, as the recycling of the variables seems to make it quite likely that subterms already in the index can be reused.
By default a standard recursive unification algorithm is used, but a polynomial-time version is optional.
If a schedule is used, it is assumed that different approaches to definitional clause conversion may be needed - typically all clauses, conjecture clauses only, or no clauses. As these choices can lead to different matrices, and the conversion itself can be expensive, the system stores and switches between the different matrices rather than converting multiple times.
As the system was developed with two guiding aims - to provide a clear implementation easily modified by others, somewhat in the spirit of MiniSAT [ES04], and to support experiments in machine learning for guiding the proof search - the implementation avoids the use of direct recusion in favour of a pair of stacks and an iterative implementation based on these, as described in [Hol23]. This allows complete and arbitrary control of backtracking restriction and other modifications to the proof search using typically quite simple modifications to the code.
The source and documentation are available at
http://www.cl.cam.ac.uk/~sbh11/connect++.html
CSE 1.7
Feng Cao
JiangXi University of Science and Technology, China
Architecture
CSE 1.7 is a developed prover based on the last version - CSE 1.6.
It is an automated theorem prover for first-order logic without equality, based mainly on a novel
inference mechanism called Contradiction Separation Based Dynamic Multi-Clause Synergized
Automated Deduction (S-CS)
[XL+18].
S-CS is able to handle multiple (two or more) clauses dynamically in a synergized way in one
deduction step, while binary resolution is a special case.
CSE 1.7 also adopts conventional factoring, equality resolution (ER rule), and variable renaming.
Some pre-processing techniques, including pure literal deletion and simplification based on the
distance to the goal clause, and a number of standard redundancy criteria for pruning the search
space: tautology deletion, subsumption (forward and backward), are applied as well.
CSE 1.7 has been improved compared with CSE 1.6, mainly from the following aspects:
Acknowledgement: Development of CSE 1.7 has been partially supported by the General Research Project of Jiangxi Education Department (Grant No. GJJ200818).
CSE_E 1.6
Peiyao Liu
Southwest Jiaotong University, China
Architecture
CSE_E 1.6 is an automated theorem prover for first-order logic by combining CSE 1.6 and E 3.1,
where CSE 1.6 is based on the Contradiction Separation Based Dynamic Multi-Clause Synergized
Automated Deduction (S-CS)
[XL+18]
and E is mainly based on superposition.
The combination mechanism is like this: E and CSE are applied to the given problem sequentially.
If either prover solves the problem, then the proof process completes.
If neither CSE nor E can solve the problem, some inferred clauses with no more than two literals,
especially unit clauses, by CSE will be fed to E as lemmas, along with the original clauses, for
further proof search.
This kind of combination is expected to take advantage of both CSE and E, and produce a better performance. Concretely, CSE is able to generate a good number of unit clauses, based on the fact that unit clauses are helpful for proof search and equality handling. On the other hand, E has a good ability on equality handling.
Acknowledgement: Development of CSE_E 1.6 has been partially supported by the National Natural Science Foundation of China (NSFC) (Grant No. 61976130). Stephan Schulz for his kind permission on using his E prover that makes CSE_E possible.
CSG_E 1.0
Peiyao Liu
Southwest Jiaotong University, China
Architecture
CSG_E 1.0 is an automated theorem prover for first-order logic by combining CSG 1.0 and E 3.1,
where CSG 1.0 is based on the Contradiction Separation Based Dynamic Multi-Clause Synergized
Automated Deduction (S-CS)
[XL+18]
and E is mainly based on superposition.
CSG uses a new deduction calculus based on S-CS rule called gridle construction method.
The main idea of the new method is to select N literals to construct a maximal standard
contradiction (called a gridle), then use the gridle to match the clauses until the gridle is
filled, and finally the literals tha cannot be matched are composed into the new inferred clause.
The combination mechanism is like this: E and CSG are applied to the given problem sequentially.
If either prover solves the problem, then the proof process completes.
If neither CSG nor E can solve the problem, some inferred clauses with no more than two literals,
especially unit clauses, by CSG will be fed to E as lemmas, along with the original clauses, for
further proof search.
This kind of combination is expected to take advantage of both CSE and E, and produce a better
performance.
Concretely, CSE is able to generate a good number of unit clauses, based on the fact that unit
clauses are helpful for proof search and equality handling.
On the other hand, E has a good ability on equality handling.
Acknowledgement: Development of CSG_E 1.0 has been partially supported by the National Natural Science Foundation of China (NSFC) (Grant No. 61976130). Stephan Schulz for his kind permission on using his E prover that makes CSE_E possible.
CSI_E 1.0
Guoyan Zeng
Southwest Jiaotong University, China
Architecture
CSI_E 1.0 is an automated theorem prover for first-order logic, combining CSI 1.0 and E, where
CSI 1.0 is a multi-layer inverse and parallel prover based on the Contradiction Separation Based
Dynamic Multi-Clause Synergized Automated Deduction (S-CS)
[XL+18]
and E is mainly based on superposition.
The combination mechanism is like this: E and CSI are applied to the given problem sequentially.
If either prover solves the problem, then the proof process completes.
If neither CSI nor E can solve the problem, some inferred clauses with no more than two literals,
especially unit clauses, by CSI will be fed to E as lemmas, along with the original clauses, for
further proof search.
This kind of combination is expected to take advantage of both CSI and E, and produce a better
performance.
Concretely, CSI is able to generate a good number of unit clauses, based on the fact that unit
clauses are helpful for proof search and equality handling.
On the other hand, E has a good ability on equality handling.
Acknowledgement: Development of CSE_E 1.6 has been partially supported by the National Natural Science Foundation of China (NSFC) (Grant No. 62106206, 62206227). Stephan Schulz for his kind permission on using his E prover that makes CSE_E possible.
cvc5 1.1.3
Andy Reynolds
University of Iowa, USA
Architecture
cvc5
[BB+22]
is the successor of CVC4
[BC+11].
It is an SMT solver based on the CDCL(T) architecture
[NOT06]
that includes built-in support for many theories, including linear arithmetic, arrays, bit
vectors, datatypes, finite sets and strings.
It incorporates approaches for handling universally quantified formulas.
For problems involving free function and predicate symbols, cvc5 primarily uses heuristic
approaches based on conflict-based instantiation and E-matching for theorems, and finite model
finding approaches for non-theorems.
Like other SMT solvers, cvc5 treats quantified formulas using a two-tiered approach. First, quantified formulas are replaced by fresh Boolean predicates and the ground theory solver(s) are used in conjunction with the underlying SAT solver to determine satisfiability. If the problem is unsatisfiable at the ground level, then the solver answers "unsatisfiable". Otherwise, the quantifier instantiation module is invoked, and will either add instances of quantified formulas to the problem, answer "satisfiable", or return unknown. Finite model finding in cvc5 targets problems containing background theories whose quantification is limited to finite and uninterpreted sorts. In finite model finding mode, cvc5 uses a ground theory of finite cardinality constraints that minimizes the number of ground equivalence classes, as described in [RT+13]. When the problem is satisfiable at the ground level, a candidate model is constructed that contains complete interpretations for all predicate and function symbols. It then adds instances of quantified formulas that are in conflict with the candidate model, as described in [RT+13]. If no instances are added, it reports "satisfiable".
cvc5 has native support for problems in higher-order logic, as described in [BR+19]. It uses a pragmatic approach for HOL, where lambdas are eliminated eagerly via lambda lifting. The approach extends the theory solver for quantifier-free uninterpreted functions (UF) and E-matching. For the former, the theory solver for UF in cvc5 now handles equalities between functions using an extensionality inference. Partial applications of functions are handle using a (lazy) applicative encoding where some function applications are equated to the applicative encoding. For the latter, several of the data structures for E-matching have been modified to incorporate matching in the presence of equalities between functions, function variables, and partial function applications.
https://github.com/cvc5/cvc5
For CASC-29, E implements a two-stage multi-core strategy-scheduling automatic mode. The total CPU time available is broken into several (unequal) time slices. For each time slice, the problem is classified into one of several classes, based on a number of simple features (number of clauses, maximal symbol arity, presence of equality, presence of non-unit and non-Horn clauses, possibly presence of certain axiom patterns...). For each class, a schedule of strategies is greedily constructed from experimental data as follows: The first strategy assigned to a schedule is the the one that solves the most problems from this class in the first time slice. Each subsequent strategy is selected based on the number of solutions on problems not already solved by a preceding strategy. The strategies are then scheduled onto the available cores and run in parallel.
About 140 different strategies have been thoroughly evaluated on all untyped first-order problems from TPTP 7.3.0. We have also explored some parts of the heuristic parameter space with a short time limit of 5 seconds. This allowed us to test about 650 strategies on all TPTP problems, and an extra 7000 strategies on UEQ problems from TPTP 7.2.0. About 100 of these strategies are used in the automatic mode, and about 450 are used in at least one schedule.
https://www.eprover.org
For CASC-J12, E implements a two-stage multi-core strategy-scheduling automatic mode. The total CPU time available is broken into several (unequal) time slices. For each time slice, the problem is classified into one of several classes, based on a number of simple features (number of clauses, maximal symbol arity, presence of equality, presence of non-unit and non-Horn clauses, possibly presence of certain axiom patterns, ...). For each class, a schedule of strategies is greedily constructed from experimental data as follows: The first strategy assigned to a schedule is the the one that solves the most problems from this class in the first time slice. Each subsequent strategy is selected based on the number of solutions on problems not already solved by a preceding strategy. The strategies are then scheduled onto the available cores and run in parallel.
About 140 different strategies have been thoroughly evaluated on all untyped first-order problems from TPTP 7.3.0. We have also explored some parts of the heuristic parameter space with a short time limit of 5 seconds. This allowed us to test about 650 strategies on all TPTP problems, and an extra 7000 strategies on UEQ problems from TPTP 7.2.0. About 100 of these strategies are used in the automatic mode, and about 450 are used in at least one schedule.
https://www.eprover.org
GKC is used as a foundation (GK Core) for building a common-sense reasoner GK. In particular, GK can handle inconsistencies and perform probabilistic and nonmonotonic reasoning [Tam21, Tam22].
The WASM version of the previous GKC 0.6 is used as the prover engine in the educational http://logictools.org system. It can read and output proofs in the TPTP, simplified TPTP and JSON format, the latter compatible with JSON-LD [TS21].
GKC only looks for proofs and does not try to show non-provability. These standard inference rules have been implemented in GKC:
We perform the selection of a given clause by using several queues in order to spread the selection relatively uniformly over these categories of derived clauses and their descendants: axioms, external axioms, assumptions and goals. The queues are organized in two layers. As a first layer we use the common ratio-based algorithm of alternating between selecting n clauses from a weight-ordered queue and one clause from the FIFO queue with the derivation order. As a second layer we use four separate queues based on the derivation history of a clause. Each queue in the second layer contains the two sub-queues of the first layer.
https://github.com/tammet/gkc/
iProver 3.9
Konstantin Korovin
University of Manchester, United Kingdom
Architecture
iProver
[Kor08,
DK20]
is a theorem prover for quantified first-order logic with theories.
iProver interleaves instantiation calculus Inst-Gen
[Kor13,
Kor08,
GK03]
with ordered resolution and superposition calculi
[DK20].
iProver approximates first-order clauses using propositional abstractions
that are solved using MiniSAT
[ES04]
or Z3
[dMB08]
and refined using model-guided instantiations.
iProver also implements a general abstraction-refinement framework for
under-and over-approximations of first-order clauses
[HK18,
HK19].
First-order clauses are exchanged between calculi during the proof search.
Recent features in iProver include:
https://gitlab.com/korovin/iprover
LEO-II 1.7.0
Alexander Steen
University of Greifswald, Germany
Architecture
LEO-II
[BP+08],
the successor of LEO
[BK98],
is a higher-order ATP system based on extensional higher-order resolution.
More precisely, LEO-II employs a refinement of extensional higher-order
RUE resolution
[Ben99].
LEO-II is designed to cooperate with specialist systems for fragments of
higher-order logic.
By default, LEO-II cooperates with the first-order ATP system E
[Sch02].
LEO-II is often too weak to find a refutation amongst the steadily growing
set of clauses on its own.
However, some of the clauses in LEO-II's search space attain a special
status: they are first-order clauses modulo the application of an
appropriate transformation function.
Therefore, LEO-II launches a cooperating first-order ATP system every n
iterations of its (standard) resolution proof search loop (e.g., 10).
If the first-order ATP system finds a refutation, it communicates its success
to LEO-II in the standard SZS format.
Communication between LEO-II and the cooperating first-order ATP system
uses the TPTP language and standards.
Unfortunately the LEO-II system still uses only a very simple sequential collaboration model with first-order ATPs instead of using the more advanced, concurrent and resource-adaptive OANTS architecture [BS+08] as exploited by its predecessor LEO.
The LEO-II system is distributed under a BSD style license, and it is available from
http://www.leoprover.org
Leo-III 1.7.15
Alexander Steen
University of Greifswald, Germany
Architecture
Leo-III
[SB21],
the successor of LEO-II
[BP+08],
is a higher-order ATP system based on extensional higher-order paramodulation
with inference restrictions using a higher-order term ordering.
The calculus contains dedicated extensionality rules and is augmented with
equational simplification routines that have their intellectual roots in
first-order superposition-based theorem proving.
The saturation algorithm is a variant of the given clause loop procedure
inspired by the first-order ATP system E.
Leo-III cooperates with external first-order ATPs that are called asynchronously during proof search; a focus is on cooperation with systems that support typed first-order (TFF) input. For this year's CASC E [Sch02, Sch13] is used as external system. However, cooperation is in general not limited to first-order systems. Further TPTP/TSTP-compliant external systems (such as higher-order ATPs or counter model generators) may be included using simple command-line arguments. If the saturation procedure loop (or one of the external provers) finds a proof, the system stops, generates the proof certificate and returns the result.
https://tptp.org/NonClassicalLogic/
The term data structure of Leo-III uses a polymorphically typed spine term representation augmented with explicit substitutions and De Bruijn-indices. Furthermore, terms are perfectly shared during proof search, permitting constant-time equality checks between alpha-equivalent terms.
Leo-III's saturation procedure may at any point invoke external reasoning tools. To that end, Leo-III includes an encoding module which translates (polymorphic) higher-order clauses to polymorphic and monomorphic typed first-order clauses, whichever is supported by the external system. While LEO-II relied on cooperation with untyped first-order provers, Leo-III exploits the native type support in first-order provers (TFF logic) for removing clutter during translation and, in turn, higher effectivity of external cooperation.
Leo-III is available on GitHub:
https://github.com/leoprover/Leo-III
Prover9 1109a
Bob Veroff on behalf of William McCune
University of New Mexico, USA
Architecture
Prover9, Version 2009-11A, is a resolution/paramodulation prover for first-order logic with
equality.
Its overall architecture is very similar to that of Otter-3.3
[McC03].
It uses the "given clause algorithm", in which not-yet-given clauses are available for rewriting
and for other inference operations (sometimes called the "Otter loop").
Prover9 has available positive ordered (and nonordered) resolution and paramodulation, negative ordered (and nonordered) resolution, factoring, positive and negative hyperresolution, UR-resolution, and demodulation (term rewriting). Terms can be ordered with LPO, RPO, or KBO. Selection of the "given clause" is by an age-weight ratio.
Proofs can be given at two levels of detail: (1) standard, in which each line of the proof is a stored clause with detailed justification, and (2) expanded, with a separate line for each operation. When FOF problems are input, proof of transformation to clauses is not given.
Completeness is not guaranteed, so termination does not indicate satisfiability.
Given a problem, Prover9 adjusts its inference rules and strategy according to syntactic properties of the input clauses such as the presence of equality and non-Horn clauses. Prover9 also does some preprocessing, for example, to eliminate predicates.
For CASC Prover9 uses KBO to order terms for demodulation and for the inference rules, with a simple rule for determining symbol precedence.
For the FOF problems, a preprocessing step attempts to reduce the problem to independent subproblems by a miniscope transformation; if the problem reduction succeeds, each subproblem is clausified and given to the ordinary search procedure; if the problem reduction fails, the original problem is clausified and given to the search procedure.
http://www.cs.unm.edu/~mccune/prover9/
Twee 2.4.2
Nick Smallbone
Chalmers University of Technology, Sweden
Architecture
Twee 2.4.2
[Sma21]
is a theorem prover for unit equality problems based on unfailing completion
[BDP89].
It implements a DISCOUNT loop, where the active set contains rewrite rules (and unorientable
equations) and the passive set contains critical pairs.
The basic calculus is not goal-directed, but Twee implements a transformation which improves goal
direction for many problems.
Twee features ground joinability testing [MN90] and a connectedness test [BD88], which together eliminate many redundant inferences in the presence of unorientable equations. The ground joinability test performs case splits on the order of variables, in the style of [MN90], and discharges individual cases by rewriting modulo a variable ordering.
Each critical pair is scored using a weighted sum of the weight of both of its terms. Terms are treated as DAGs when computing weights, i.e., duplicate subterms are counted only once per term.
For CASC, to take advantage of multiple cores, several versions of Twee run in parallel using different parameters (e.g., with the goal-directed transformation on or off).
The passive set is represented compactly (12 bytes per critical pair) by storing only the information needed to reconstruct the critical pair, not the critical pair itself. Because of this, Twee can run for an hour or more without exhausting memory.
Twee uses an LCF-style kernel: all rules in the active set come with a certified proof object which traces back to the input axioms. When a conjecture is proved, the proof object is transformed into a human-readable proof. Proof construction does not harm efficiency because the proof kernel is invoked only when a new rule is accepted. In particular, reasoning about the passive set does not invoke the kernel.
Twee can be downloaded as open source from:
https://nick8325.github.io/twee
Twee 2.5.0
Nick Smallbone
Chalmers University of Technology, Sweden
Architecture
Twee 2.4.2
[Sma21]
is a theorem prover for unit equality problems based on unfailing completion
[BDP89].
It implements a DISCOUNT loop, where the active set contains rewrite rules (and unorientable
equations) and the passive set contains critical pairs.
The basic calculus is not goal-directed, but Twee implements a transformation which improves goal
direction for many problems.
Twee features ground joinability testing [MN90] and a connectedness test [BD88], which together eliminate many redundant inferences in the presence of unorientable equations. The ground joinability test performs case splits on the order of variables, in the style of [MN90], and discharges individual cases by rewriting modulo a variable ordering. New this year is a mode which rewrites backwards from the goal instead of enumerating critical pairs, but it is still rather rough.
Each critical pair is scored using a weighted sum of the weight of both of its terms. Terms are treated as DAGs when computing weights, i.e., duplicate subterms are counted only once per term.
For CASC, to take advantage of multiple cores, several versions of Twee run in parallel using different parameters (e.g., with the goal-directed transformation on or off).
The passive set is represented compactly (12 bytes per critical pair) by storing only the information needed to reconstruct the critical pair, not the critical pair itself. Because of this, Twee can run for an hour or more without exhausting memory.
Twee uses an LCF-style kernel: all rules in the active set come with a certified proof object which traces back to the input axioms. When a conjecture is proved, the proof object is transformed into a human-readable proof. Proof construction does not harm efficiency because the proof kernel is invoked only when a new rule is accepted. In particular, reasoning about the passive set does not invoke the kernel.
Twee can be downloaded as open source from:
https://nick8325.github.io/twee
There have been a number of changes and improvements since Vampire 4.7, although it is still the
same beast.
Most significant from a competition point of view are long-awaited refreshed strategy schedules.
As a result, several features present in previous competitions will now come into full force,
including new rules for the evaluation and simplification of theory literals.
A large number of completely new features and improvements also landed this year: highlights
include a significant refactoring of the substitution tree implementation, the arrival of
encompassment demodulation to Vampire, and support for parametric datatypes.
Vampire's higher-order support has also been re-implemented from the ground up.
The new implementation is still at an early stage and its theoretical underpinnings are being
developed.
There is currently no documentation of either.
Vampire 4.8
Michael Rawson
TU Wien, Austria
Architecture
Vampire
[KV13]
is an automatic theorem prover for first-order logic with extensions to theory-reasoning and higher-order logic.
Vampire implements the calculi of ordered binary resolution, and superposition for handling equality.
It also implements the Inst-gen calculus and a MACE-style finite model builder
[RSV16].
Splitting in resolution-based proof search is controlled by the AVATAR architecture which uses a SAT or SMT solver to make splitting decisions
[Vor14,
RB+16].
A number of standard redundancy criteria and simplification techniques are used for pruning the
search space: subsumption, tautology deletion, subsumption resolution and rewriting by ordered
unit equalities.
The reduction ordering is the Knuth-Bendix Ordering.
Substitution tree and code tree indexes are used to implement all major operations on sets of
terms, literals and clauses.
Internally, Vampire works only with clausal normal form.
Problems in the full first-order logic syntax are clausified during preprocessing
[RSV16].
Vampire implements many useful preprocessing transformations including the SinE axiom selection
algorithm.
When a theorem is proved, the system produces a verifiable proof, which validates both the
clausification phase and the refutation of the CNF.
There have been a number of improvements since Vampire 4.8, although it is still the same beast.
For the first time this year, Vampire's schedules were constructed mostly using the Snake strategy
selection tool, although a return of the traditional Spider is still possible in future.
Improvements from the past year include:
Vampire 4.9
Michael Rawson
TU Wien, Austria
Vampire's higher-order support remains very similar to last year, although a re-implementation
intended for mainline Vampire is already underway.
Architecture
Vampire
[KV13]
is an automatic theorem prover for first-order logic with extensions to theory-reasoning and
higher-order logic.
Vampire implements the calculi of ordered binary resolution, and superposition for handling
equality.
It also implements a MACE-style finite model builder for finding finite counter-examples
[RSV16].
Splitting in resolution-based proof search is controlled by the AVATAR architecture which uses a
SAT or SMT solver to make splitting decisions
[Vor14,
RB+16].
A number of standard redundancy criteria and simplification techniques are used for pruning the
search space: subsumption, tautology deletion, subsumption resolution and rewriting by ordered
unit equalities.
The reduction ordering is the Knuth-Bendix Ordering.
Substitution tree and code tree indexes are used to implement all major operations on sets of
terms, literals and clauses.
Internally, Vampire works only with clausal normal form.
Problems in the full first-order logic syntax are clausified during preprocessing
[RSV16].
Vampire implements many useful preprocessing transformations including the SInE axiom selection
algorithm.
When a theorem is proved, the system produces a verifiable proof, which validates both the
clausification phase and the refutation of the CNF.
Zipperposition 2.1.9999
Jasmin Blanchette
Ludwig-Maximilians-Universität München, Germany
Architecture
Zipperposition is a superposition-based theorem prover for typed first-order
logic with equality and for higher-order logic.
It is a pragmatic implementation of a complete calculus for full higher-order
logic
[BB+21].
It features a number of extensions that include polymorphic types, user-defined
rewriting on terms and formulas ("deduction modulo theories"), a lightweight
variant of AVATAR for case splitting
[EBT21],
and Boolean reasoning
[VN20].
The core architecture of the prover is based on saturation with an extensible
set of rules for inferences and simplifications.
Zipperposition uses a full higher-order unification algorithm that enables
efficient integration of procedures for decidable fragments of higher-order
unification
[VBN20].
The initial calculus and main loop were imitations of an earlier version of E
[Sch02].
With the implementation of higher-order superposition, the main loop had to be
adapted to deal with possibly infinite sets of unifiers
[VB+21].
Zipperposition's code can be found at
https://github.com/sneeuwballen/zipperpositionand is entirely free software (BSD-licensed).
Zipperposition can also output graphic proofs using graphviz. Some tools to perform type inference and clausification for typed formulas are also provided, as well as a separate library for dealing with terms and formulas [Cru15].