Entrants' System Descriptions

Darwin 1.4.4

Peter Baumgartner1, Alexander Fuchs2, Cesare Tinelli2
1NICTA, Australia, 2The University of Iowa, USA

Architecture

Darwin [BFT04,BFT06] is an automated theorem prover for first order clausal logic. It is an implementation of the Model Evolution calculus [BT03]. The Model Evolution calculus lifts the propositional DPLL procedure to first-order logic. One of the main motivations for this approach was the possibility of migrating to the first-order level some of those very effective search techniques developed by the SAT community for the DPLL procedure.

The current version of Darwin implements first-order versions of unit propagation inference rules analogously to a restricted form of unit resolution and subsumption by unit clauses. To retain completeness, it includes a first-order version of the (binary) propositional splitting inference rule.

Proof search in Darwin starts with a default interpretation for a given clause set, which is evolved towards a model or until a refutation is found.

Strategies

Darwin traverses the search space by iterative deepening over the term depth of candidate literals. Darwin employs a uniform search strategy for all problem classes.

Implementation

The central data structure is the context. A context represents an interpretation as a set of first-order literals. The context is grown by using instances of literals from the input clauses. The implementation of Darwin is intended to support basic operations on contexts in an efficient way. This involves the handling of large sets of candidate literals for modifying the current context. The candidate literals are computed via simultaneous unification between given clauses and context literals. This process is sped up by storing partial unifiers for each given clause and merging them for different combinations of context literals, instead of redoing the whole unifier computations. For efficient filtering of unneeded candidates against context literals, discrimination tree or substitution tree indexing is employed. The splitting rule generates choice points in the derivation which are backtracked using a form of backjumping similar to the one used in DPLL-based SAT solvers.

Darwin is implemented in OCaml and has been tested under various Linux distributions. It is available from 

    http://goedel.cs.uiowa.edu/Darwin/
Changes to the previous version consist of minor bug fixes.

Expected Competition Performance

We expect its performance to be very strong in the EPR division.

E 1.1pre and EP 1.1pre

Stephan Schulz
Technische Universität München, Germany,

Architecture

E 1.1pre [Sch02,Sch04a] is a purely equational theorem prover. The core proof procedure operates on formulas in clause normal form, using a calculus that combines superposition (with selection of negative literals) and rewriting. No special rules for non-equational literals have been implemented, i.e., resolution is simulated via paramodulation and equality resolution. The basic calculus is extended with rules for AC redundancy elimination, some contextual simplification, and pseudo-splitting with definition caching. The latest versions of E also supports simultaneous paramodulation, either for all inferences or for selected inferences.

E is based on the DISCOUNT-loop variant of the given-clause algorithm, i.e., a strict separation of active and passive facts. Proof search in E is primarily controlled by a literal selection strategy, a clause evaluation heuristic, and a simplification ordering. The prover supports a large number of preprogrammed literal selection strategies, many of which are only experimental. Clause evaluation heuristics can be constructed on the fly by combining various parameterized primitive evaluation functions, or can be selected from a set of predefined heuristics. Supported term orderings are several parameterized instances of Knuth-Bendix Ordering (KBO) and Lexicographic Path Ordering (LPO).

The prover uses a preprocessing step to convert formulas in full first order format to clause normal form. This step may introduce (first-order) definitions to avoid an exponential growth of the formula. Preprocessing also unfolds equational definitions and performs some simplifications on the clause level.

The automatic mode determines literal selection strategy, term ordering, and search heuristic based on simple problem characteristics of the preprocessed clausal problem.

EP 1.1pre is just a combination of E 1.1pre in verbose mode and a proof analysis tool extracting the used inference steps.

Strategies

E has been optimized for performance over the TPTP. The automatic mode of E 1.1pre is partially inherited from the previous version and is based on about 150 test runs over TPTP 3.5.0 and additional tests on large proof problems. It consists of the selection of one of about 40 different strategies for each problem. All test runs have been performed on Linux/Intel machines with a time limit roughly equivalent to 300 seconds on 300MHz Sun SPARC machines, i.e., around 30 seconds on 2Ghz class machines. All individual strategies are refutationally complete.

E distinguishes problem classes based on a number of features, all of which have between 2 and 4 possible values. The most important ones are:

For classes above a threshold size, we assign the absolute best heuristic to the class. For smaller, non-empty classes, we assign the globally best heuristic that solves the same number of problems on this class as the best heuristic on this class does. Empty classes are assigned the globally best heuristic. Typically, most selected heuristics are assigned to more than one class.

For the LTB part of the competition, E will use a relevancy-based pruning approach and attempt to solve the problems with successively more complete specifications until it suceeds or runs out of time.

Implementation

E is implemented in ANSI C, using the GNU C compiler. At the core is a implementation of aggressively shared first-order terms in a term bank data structure. Based on this, E supports the global sharing of rewrite steps. Rewriting is implemented in the form of rewrite links from rewritten to new terms. In effect, E is caching rewrite operations as long as sufficient memory is available. Other important features are the use of perfect discrimination trees with age and size constraints for rewriting and unit-subsumption, feature vector indexing [Sch04b] for forward- and backward subsumption and contextual literal cutting, and a new polynomial implementation of LPO [Loe04].

The program has been successfully installed under SunOS 4.3.x, Solaris 2.x, HP-UX B 10.20, MacOS-X, and various versions of Linux. Sources of the latest released version are available freely from: 

    http://www.eprover.org
EP 1.1pre is a simple Bourne shell script calling E and the postprocessor in a pipeline.

Expected Competition Performance

In the last years, E performed well in most proof categories. We believe that E will again be among the stronger provers in the FOF and CNF categories. We hope that E will at least be a useful complement to dedicated systems in the other categories.

EP 1.1p will be hampered by the fact that it has to analyse the inference step listing, an operation that typically is about as expensive as the proof search itself. Nevertheless, it should be competitive among the FOF and LTB proof class systems.

E-Darwin 1.2

Björn Pelzer
University Koblenz-Landau, Germany

Architecture

E-Darwin is an automated theorem prover for first order clausal logic with equality. It is a modified version of the Darwin prover [BFT04], and it implements the Model Evolution with Equality calculus [BT05]. The general operation of the original Darwin has been extended by inferences for handling equality, specifically a paramodulation and a reflexivity inference. Whereas the original Darwin derived units only, the new inferences in E-Darwin allow the derivation of multi-literal clauses. A more extensive detection and handling of redundancy has been added as well.

Strategies

The uniform search strategy is identical to the one employed in the original Darwin.

Implementation

Darwin's method of storing partial unifiers has been adapted to equations and subterm positions for the paramodulation inference in E-Darwin. A combination of perfect and non-perfect discrimination tree indexes is used to store the context and the clauses.

E-Darwin is implemented in the functional/imperative language OCaml. The system has been tested on Unix and is available under the GNU Public License from the E-Darwin website at: 

    http://www.uni-koblenz.de/~bpelzer/edarwin

Expected Competition Performance

E-Darwin development forked from the original Darwin at version 1.3 and is still very much work in progress, serving as a testbed for modifications to the model evolution calculus. The performance on problems without equality remains on the level of the by now outdated Darwin 1.3.

E-KRHyper 1.1.3

Björn Pelzer
University Koblenz-Landau, Germany

Architecture

E-KRHyper [PW07] is a theorem proving and model generation system for first-order logic with equality. It is an implementation of the E-hyper tableau calculus [BFP07], which integrates a superposition-based handling of equality [BG98] into the hyper tableau calculus [BFN96]. The system is an extension of the KRHyper theorem prover [Wer03], which implements the original hyper tableau calculus.

An E-hyper tableau is a tree whose nodes are labeled with clauses and which is built up by the application of the inference rules of the E-hyper tableau calculus. The calculus rules are designed such that most of the reasoning is performed using positive unit clauses. A branch can be extended with new clauses that have been derived from the clauses of that branch.

A positive disjunction can be used to split a branch, creating a new branch for each disjunct. No variables may be shared between branches, and if a case-split creates branches with shared variables, then these are immediately substituted by ground terms. The grounding substitution is arbitrary as long as the terms in its range are irreducible: the branch being split may not contain a positive equational unit which can simplify a substituting term, i.e. rewrite it with one that is smaller according to a reduction ordering. When multiple irreducible substitutions are possible, each of them must be applied in consecutive splittings in order to preserve completeness.

Redundancy rules allow the detection and removal of clauses that are redundant with respect to a branch.

The hyper extension inference from the original hyper tableau calculus is equivalent to a series of E-hyper tableau calculus inference applications. Therefore the implementation of the hyper extension in KRHyper by a variant of semi-naive evaluation [Ull89] is retained in E-KRHyper, where it serves as a shortcut inference for the resolution of non-equational literals.

Strategies

E-KRHyper uses a uniform search strategy for all problems. The E-hyper tableau is generated depth-first, with E-KRHyper always working on a single branch. Refutational completeness and a fair search control are ensured by an iterative deepening strategy with a limit on the maximum term weight of generated clauses.

Implementation

E-KRHyper is implemented in the functional/imperative language OCaml. The system accepts input in the TPTP format and in the TPTP-supported Protein-format. The calculus implemented by E-KRHyper works on clauses, so first order formula input is converted into CNF by an algorithm which follows the transformation steps as used in the clausification of Otter [McC03a]. E-KRHyper operates on an E-hyper tableau which is represented by linked node records. Several layered discrimination-tree based indexes (both perfect and non-perfect) provide access to the clauses in the tableau and support backtracking.

The system runs on Unix and MS-Windows platforms and is available under the GNU Public License from the E-KRHyper website at: 

    http://www.uni-koblenz.de/~bpelzer/ekrhyper

Expected Competition Performance

Since last year only minor changes have been done which could affect the performance within CASC, so the results are expected to be at or below the level of Otter.

Equinox 4.1

Koen Claessen
Chalmers University of Technology, Sweden

Architecture

Equinox is an experimental theorem prover for pure first-order logic with equality. It finds ground proofs of the input theory, by solving successive ground instantiations of the theory using an incremental SAT-solver. Equinox is based on a "stack" of increasingly powerful logics, starting at propositional logic all the way up the first-order logic with equality. The implementation consists of a corresponding stack of theorem provers.

This is the first version of Equinox that is complete.

Strategies

There is only one strategy in Equinox:
  1. Give all ground clauses in the problem to a SAT solver.
  2. Run the SAT-solver.
  3. If a contradiction is found, we have a proof and we terminate.
  4. If a model is found, we use the model to indicate which new ground instantiations should be added to the SAT-solver.
  5. Goto 2.

Implementation

The main part of Equinox is implemented in Haskell using the GHC compiler. Equinox also has a built-in incremental SAT solver (MiniSat) which is written in C++. The two parts are linked together on the object level using Haskell's Foreign Function Interface.

Expected Competition Performance

Equinox should perform better than previous years. There should be problems that it can solve that few other provers can handle.

Infinox 1.0

Ann Lillieström, Koen Claessen
Chalmers University of Technology, Sweden

Architecture

Infinox is a tool that (for some problems) can show the absence of finite models. It works by showing the existence of functions or relations with certain properties that imply infinity, such as:
  1. for an injective function f : D → D that is not surjective, D must be infinite
  2. for a surjective function f : D → D that is not injective, D must be infinite
  3. for a relation r : D × D that is anti-symmetric, transitive, and serial, D must be infinite (or empty)
All methods in Infinox are based on one of these three principles.

Strategies

Infinox runs a number of fixed methods in sequence, and terminates if one of them succeeds.

Implementation

Infinox is implemented in Haskell using the GHC compiler, and it uses Stephan Schulz' E-prover as a back-end.

Expected Competition Performance

Infinox participates in only the demonstration division.

iProver 0.5

Konstantin Korovin
The University of Manchester, United Kingdom

Architecture

iProver is an automated theorem prover which is based on an instantiation calculus Inst-Gen [GK03, Kor08a], complete for first-order logic. One of the distinctive features of iProver is a modular combination of first-order reasoning with ground reasoning. In particular, iProver currently integrates MiniSat for reasoning with ground abstractions of first-order clauses. In addition to instantiation, iProver implements ordered resolution calculus and a combination of instantiation and ordered resolution, see [Kor08b] for the implementation details. The saturation process is implemented as a modification of a given clause algorithm. We use non-perfect discrimination trees for the unification indexes, priority queues for passive clauses and a compressed vector index for subsumption and subsumption resolution (both forward and backward). The following redundancy eliminations are implemented: blocking non-proper instantiations; dismatching constraints [GK04,Kor08b]; global subsumption [Kor08b]; resolution-based simplifications and propositional-based simplifications. Equality is dealt with (internally) by adding the necessary axioms of equality. iProver has a satisfiablity mode which includes a finite model finder, based on an adaptation of ideas from DarwinFM and Paradox to the iProver setting.

Strategies

iProver v0.5 has around 40 options to control the proof search including options for literal selections, passive clause selections, frequency of calling the SAT solver, simplifications and options for combination of instantiation with resolution. At CASC iProver will execute a fixed schedule of selected options.

For the LTB division a small script partitions the time available to the given problem set and runs iProver with the allocated time limit, and time is repartitioned after each solved problem.

Implementation

iProver is implemented in OCaml and for the ground reasoning uses MiniSat. iProver accepts FOF and CNF formats. In the case of FOF format, either Vampire or E prover is used for clausification.

iProver is available at: 

    http://www.cs.man.ac.uk/~korovink/iprover/

Expected Competition Performance

iProver 0.5 is the CASC-J4 EPR division winner.

iProver 0.7 and iProver-SInE 0.7

Konstantin Korovin
The University of Manchester, United Kingdom

Architecture

iProver is an automated theorem prover based on an instantiation calculus Inst-Gen [GK03,Kor08a] which is complete for first-order logic. One of the distinctive features of iProver is a modular combination of first-order reasoning with ground reasoning. In particular, iProver currently integrates MiniSat [ES04] for reasoning with ground abstractions of first-order clauses. In addition to instantiation, iProver implements ordered resolution calculus and a combination of instantiation and ordered resolution, see [Kor08b] for the implementation details. The saturation process is implemented as a modification of a given clause algorithm. We use non-perfect discrimination trees for the unification indexes, priority queues for passive clauses and a compressed vector index for subsumption and subsumption resolution (both forward and backward). The following redundancy eliminations are implemented: blocking non-proper instantiations; dismatching constraints [GK04,Kor08b]; global subsumption [Kor08b]; resolution-based simplifications and propositional-based simplifications. We implemented a compressed feature vector index for efficient forward/backward subsumption and subsumption resolution. Equality is dealt with (internally) by adding the necessary axioms of equality.

For the LTB division, iProver-SInE runs iProver as the underlying inference engine of SInE 0.4, i.e., axiom selection is done by SInE, and proof attempts are done by iProver.

Strategies

iProver has around 40 options to control the proof search including options for literal selections, passive clause selections, frequency of calling the SAT solver, simplifications and options for combination of instantiation with resolution. At CASC iProver will execute a small number of fixed schedules of selected options depending on general syntactic properties such as Horn/non-Horn, equational/non-equational and maximal term depth.

Implementation

iProver is implemented in OCaml and for the ground reasoning uses MiniSat. iProver accepts FOF and CNF formats, in the case of FOF format, E prover is used for clausification. iProver is available at: 
    http://www.cs.man.ac.uk/~korovink/iprover/

Expected Competition Performance

We expect strong performance in the EPR division and reasonably good performance in FOF, CNF, FNT, SAT and LTB divisions.

iProver-Eq 0.5

Konstantin Korovin, Christoph Sticksel
The University of Manchester, United Kingdom

Architecture

iProver-Eq extends the iProver system [Kor08a] with built-in equational reasoning, along the lines of [GK04]. As in the iProver system, first-order reasoning is combined with ground satisfiability checking where the latter is delegated to an off-the-shelf ground solver. The main differences with iProver are that the ground reasoning is done modulo the theory of equality and the first-order reasoning is done by a variant of ordered paramodulation calculus.

The first-order reasoning in iProver-Eq consists of three components, each based on a given clause algorithm: selection of clauses for instantiation, unit paramodulation on selected literals and resolution for simplifications. For non-equational input, the system behaves almost identically to the iProver system, employing the same calculus and simplifications. When equational literals are selected in clauses, a separate calculus based on ordered paramodulation and demodulation is used to find conflicts between selected literals. Literals participating in a conflict give rise to instantiations of the clauses they are selected in and these instances are in turn passed to the ground solver. The ground solver is required to reason modulo equality and we have integrated the CVC3 solver [BT07] for this task.

Strategies

The most influential options on the proof search in iProver-Eq control literal selection and passive clause selection in the individual given clause algorithms as well as the global distribution of time between the three parts and the ground solver. At CASC, iProver-Eq will execute a fixed schedule of selected options as well as simple heuristics for the initial distribution between the equational and non-equational reasoning.

Implementation

iProver-Eq is implemented in OCaml. For the ground reasoning iProver-Eq uses CVC3 in the equational case and MiniSat in the non-equational case. iProver-Eq accepts FOF and CNF formats. In the case of FOF format, the E prover is used for clausification.

Expected Competition Performance

iProver-Eq is still work in progress and has not yet been evaluated. We hope iProver-Eq will perform reasonably well in FOF and CNF divisions, in particular improving iProver's performance on equational problems.

Isabelle/HOL 2009

Jasmin Blanchette1, Lawrence C. Paulson2, Tobias Nipkow1, Makarius Wenzel1, Stefan Berghofer1
1Technische Universität München, Germany, 2University of Cambridge, United Kingdom

Architecture

Isabelle/HOL 2009 [NPW02] is the higher-order logic incarnation of the generic proof assistant Isabelle2009. While designed for interactive proof development, Isabelle/HOL also provides several automatic proof tactics, notably an equational reasoner [Nip89], a classical reasoner [PN94], a tableau prover [Pau99], and a first-order resolution-based prover [Hur03].

Although Isabelle is designed for interactive proof development, it is a little known fact that it is possible to run Isabelle from the command line, passing in a theory file with a formula to solve. Isabelle theory files can include Standard ML code to be executed when the file is processed. The TPTP2X Isabelle format module outputs a THF problem in Isabelle/HOL syntax, augmented with ML code that (1) runs the nine tactics in sequence, each with a CPU time limit, until one succeeds or all fail, and (2) reports the result and proof (if found) using the SZS standards. A Perl script is used to insert the CPU time limit (equally divided over the nine tactics) into TPTP2X's Isabelle format output, and then run the command line isabelle-process on the resulting theory file.

Strategies

The Isabelle/HOL wrapper submitted to the competition simply tries the following tactics sequentially:
simp
Performs equational reasoning using rewrite rules.
blast
Searches for a proof using a fast untyped tableau prover and then attempts to reconstruct the proof using Isabelle tactics.
auto
Combines simplification and classical reasoning under one roof.
metis
Combines ordered resolution and ordered paramodulation. The proof is then reconstructed using Isabelle tactics.
fast
Searches for a proof using sequent-style reasoning, performing a depth-first search. Unlike blast and metis, they construct proofs directly in Isabelle. That makes them slower but enables them to work in the presence of the more unusual features of HOL, such as type classes and function unknowns.
fastsimp
Combines fast and simp.
best
Similar to fast, except that it performs a best-first search.
force
Similar to auto, but more exhaustive.
meson
Implements Loveland's MESON procedure [Lov78]. Constructs proofs directly in Isabelle.

Implementation

Isabelle is a generic theorem prover written in Standard ML. Its meta-logic, Isabelle/Pure, provides an intuitionistic fragment of higher-order logic. The HOL object logic extends pure with a more elaborate version of higher-order logic, complete with the familiar connectives and quantifiers. Other object logics are available, notably FOL (first-order logic) and ZF (Zermelo–Fraenkel set theory).

The implementation of Isabelle relies on a small LCF-style kernel, meaning that inferences are implemented as operations on an abstract theorem datatypes. Assuming the kernel is correct, all values of type theorem are correct by construction.

Most of the code for Isabelle was written by the Isabelle teams at the University of Cambridge and the Technische Universität München. A notable exception is the metis proof method, which was taken from the HOL4 theorem prover (also implemented in ML).

Isabelle/HOL is available for all major platforms under a BSD-style license from 

    http://www.cl.cam.ac.uk/research/hvg/Isabelle

Expected Competition Performance

Early results with Isabelle/HOL 2008 suggest that Isabelle will finish third in the THF category, immediately after TPS. However, in the meantime, two unsound proof modes have been disabled in TPS. This could be enough to provide us with a second place.

leanCoP 2.1 and leanCoP-SInE 2.1

Jens Otten
University of Potsdam, Germany

Architecture

leanCoP [OB03,Ott08a] is an automated theorem prover for classical first-order logic. It is a very compact implementation of the connection (tableau) calculus [Bib87,LS01].

For the LTB division, leanCoP-SInE runs leanCoP as the underlying inference engine of SInE 0.4, i.e., axiom selection is done by SInE, and proof attempts are done by leanCoP.

Strategies

The reduction rule of the connection calculus is applied before the extension rule. Open branches are selected in a depth-first way. Iterative deepening on the proof depth is used to achieve completeness. leanCoP 2.1 includes all the additional strategies and search techniques of leanCoP 2.0, i.e., regularity, lemmata, restricted backtracking [Ott08b], and a fixed strategy scheduling.

Implementation

leanCoP is implemented in Prolog. The source code of the core prover is only a few lines long and fits on half a page. Prolog's built-in indexing mechanism is used to quickly find connections. While the core prover and the definitional clausal form transformation from leanCoP 2.0 have not changed, the following extensions and improvements have been integrated into leanCoP 2.1: The source code of leanCoP 2.1, which is available under the GNU general public license, together with more information can be found on the leanCoP web site at: 
    http://www.leancop.de

Expected Competition Performance

We expect the performance of leanCoP 2.1 to be similar to that of leanCoP 2.0. On problems with many axioms, like those in the LTB division of CASC, the combined leanCoP-SInE prover should perform significantly better than leanCoP alone.

LEO-II 1.0

Christoph Benzmüller1,2, Frank Theiss1
1International University of Germany, Germany, 2Articulate Software, USA

Architecture

The higher-order theorem prover LEO-II is the successor of LEO [BK98], which was developed as part of the Saarbruecken OMEGA system [SBA06]. The development of the independent LEO-II prover started in 2006 at Cambridge University, UK, in a joint project with Larry Paulson that was funded by the EPSRC. Previous versions of LEO-II have been described in the literature [BP+07,BP+08].

The calculus currently employed by LEO-II is best characterized as a strategic refinement of extensional higher-order RUE resolution [Ben99]. Novel aspects in LEO-II version 1.0 over previous versions include splitting of the conjecture in several subproblems (if appropriate), improved clause normalization and improved strategies for the basic fragment of simple type theory [BS09] (all but one of the examples that were characterized as challenging for higher-order provers in [BS09] are now provable in less than 0.15 seconds in LEO-II). LEO-II offers also an interactive mode and, most importantly, it is capable of generating proof objects in TSTP format.

Strategies

LEO-II is designed to cooperate with specialist systems for fragments of higher-order logic. The idea is to combine the strengths of the different systems: LEO-II predominantly addresses higher-order aspects in its reasoning process, with the aim of quickly removing higher-order clauses from the search space, and turning them into first-order clauses that can be refuted with a first-order ATP system. Currently, LEO-II is capable of cooperating with the first-order ATP systems E, SPASS, and Vampire. By default LEO-II cooperates with E.

Implementation

LEO-II is implemented in Objective Caml version 3.10 and its problem representation language is the new TPTP THF language [BRS08].

The improved performance of LEO-II in comparison to its predecessor LEO (implemented in LISP) is due to several novel features including the exploitation of term sharing and term indexing techniques [TB06], support for primitive equality reasoning (extensional higher-order RUE resolution), and improved heuristics at the calculus level.

Unfortunately the LEO-II system currently 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 online at: 

    http://leoprover.org

Expected Competition Performance

LEO-II's competition performance is hard to predict for different reasons: this is the first higher-order CASC competition ever held, the THF TPTP library [SB+09] grew very fast over the last year (faster than the first-order TPTP at any point) and many novel problems have recently entered the THF TPTP, LEO-II version 1.0 has substantially changed compared to the previous versions, and the performance of the competitor systems is hard to predict since they appear to be improving fast. An exciting and very motivating situation!

Matita 1.0

The HELM Team and contributors
University of Bologna, Italy

Architecture

Matita (0.5.7) is an interactive theorem prover including a fully automatic module (prover) for problems falling in the first order unit equality case. An overall description of the system and its architecture can be found in [AC+07], but there is no paper devoted to the automatic prover built in the system.

Strategies

The prover is based on standard superposition calculus for unit equality clauses.

Implementation

Matita is written in Objective Caml, a functional language similar to ML developed at INRIA. The automatic prover participating to the CASC is a module of 4000 lines, designed with simplicity and ease of integration in mind. It uses the functor abstraction mechanism of the OCaml language to achieve a good degree of reusability (i.e., comparison over terms is an abstract notion, that can be instantiated with a reduction aware relation for higher order logics like the Calculus of Inductive Constructions on which Matita is based, or a simpler alpha equivalence relation for the TPTP first order language). Matita is based on the Curry-Howard Isomorphism, i.e., proofs are lambda-terms of the CIC calculus. The automatic prover is thus able to produce a trace suitable for proof term reconstruction [AT07].

The ATP system registered to the CASC competition will be part of the upcoming 1.0 release of the Matita interactive theorem prover, and is thus not part of any officially released versions, but can be downloaded using the SVN repository at: 

    http://matita.cs.unibo.it

Expected Competition Performance

Since the system never participated to the CASC, there is no real expectation, but we hope not to finish last ;-).

Metis 2.2

Joe Hurd
Galois, Inc., USA

Architecture

Metis 2.2 [Hur03] is a proof tactic used in the HOL4 interactive theorem prover. It works by converting a higher order logic goal to a set of clauses in first order logic, with the property that a refutation of the clause set can be translated to a higher order logic proof of the original goal.

Experiments with various first order calculi [Hur03] have shown a given clause algorithm and ordered resolution to best suit this application, and that is what Metis 2.2 implements. Since equality often appears in interactive theorem prover goals, Metis 2.2 also implements the ordered paramodulation calculus.

Strategies

Metis 2.2 uses a fixed strategy for every input problem. Negative literals are always chosen over positive literals, and terms are ordered using the Knuth-Bendix ordering with uniform symbol weight and precedence favouring reduced arity.

Implementation

Metis 2.2 is written in Standard ML, for ease of integration with HOL4. It uses indexes for resolution, paramodulation, (forward) subsumption and demodulation. It keeps the Active clause set reduced with respect to all the unit equalities so far derived.

In addition to standard age and size measures, Metis 2.2 uses finite models to weight clauses in the Passive set. When integrated with higher order logic, a finite model is manually constructed to interpret standard functions and relations in such a way as to make many standard axioms true and negated goals false. Non-standard functions and relations are interpreted randomly, but with a bias towards making negated goals false. Since it is part of the CASC competition rules that standard functions and relations are obfuscated, Metis 2.2 will back off to the biased random interpretation of all functions and relations (except equality), using a finite model with 4 elements.

Metis 2.2 reads problems in TPTP format and outputs detailed proofs in TSTP format, where each refutation step is one of 6 simple inference rules. Metis 2.2 implements a complete calculus, so when the set of clauses is saturated it can soundly declare the input problem to be unprovable (and outputs the saturation set).

Metis 2.2 is free software, released under the GPL. It can be downloaded from 

    http://www.gilith.com/software/metis

Expected Competition Performance

The major change between Metis 2.1, which was entered into CASC-J4, and Metis 2.2 is the representation of normalization steps in TSTP proof format. There were only minor changes to the core proof engine, so Metis 2.2 is expected to perform at approximately the same level and end up in the lower half of the table.

OSHL-S 0.6

Hao Xu, David Plaisted
University of North Carolina at Chapel Hill, USA

Architecture

OSHL-S is a theorem prover based on the architecture and strategy introduced in [PZ00] with a few improvements. Type inference is employed to reduce the number of instances that are generated before a contradicting instance is found.

Strategies

OSHL-S employs a uniform strategy for all problems, which is similar to OSHL: it starts with a all negative or all positive model. In each iteration, it finds contradicting instances of the model using inferred types, and then modifies the model to make the instance satisfiable, if possible.

Implementation

OSHL-S is implemented in Java using Java SE 6 SDK and the Netbeans IDE. The implementation of OSHL-S combines a few strategies for improving the performance of the system, including relaxed ordering, context-free types, relevance ranking, and batched generation. The website for the prover and tools is: 
    http://www.cs.unc.edu/~xuh/oshls

Expected Competition Performance

The performance should be improved over that of OSHL-S 0.1.

Otter 3.3

William McCune
Argonne National Laboratory, USA

Architecture

Otter 3.3 [McC03a] is an ATP system for statements in first-order (unsorted) logic with equality. Otter is based on resolution and paramodulation applied to clauses. An Otter search uses the "given clause algorithm", and typically involves a large database of clauses; subsumption and demodulation play an important role.

Strategies

Otter's original automatic mode, which reflects no tuning to the TPTP problems, will be used.

Implementation

Otter is written in C. Otter uses shared data structures for clauses and terms, and it uses indexing for resolution, paramodulation, forward and backward subsumption, forward and backward demodulation, and unit conflict. Otter is available from: 
    http://www-unix.mcs.anl.gov/AR/otter/

Expected Competition Performance

Otter has been entered into CASC as a stable benchmark against which progress can be judged (there have been only minor changes to Otter since 1996 [MW97], nothing that really affects its performace in CASC). This is not an ordinary entry, and we do not hope for Otter to do well in the competition.

Acknowledgments: Ross Overbeek, Larry Wos, Bob Veroff, and Rusty Lusk contributed to the development of Otter.

Paradox 3.0

Koen Claessen, Niklas Sörensson
Chalmers University of Technology, Sweden

Architecture

Paradox [CS03] is a finite-domain model generator. It is based on a MACE-style [McC03b] flattening and instantiating of the first-order clauses into propositional clauses, and then the use of a SAT solver to solve the resulting problem.

Paradox incorporates the following features: Polynomial-time clause splitting heuristics, the use of incremental SAT, static symmetry reduction techniques, and the use of sort inference.

Strategies

There is only one strategy in Paradox:
  1. Analyze the problem, finding an upper bound N on the domain size of models, where N is possibly infinite. A finite such upper bound can be found, for example, for EPR problems.
  2. Flatten the problem, and split clauses and simplify as much as possible.
  3. Instantiate the problem for domain sizes 1 up to N, applying the SAT solver incrementally for each size. Report "SATISFIABLE" when a model is found.
  4. When no model of sizes smaller or equal to N is found, report "CONTRADICTION".
In this way, Paradox can be used both as a model finder and as an EPR solver.

Implementation

The main part of Paradox is implemented in Haskell using the GHC compiler. Paradox also has a built-in incremental SAT solver which is written in C++. The two parts are linked together on the object level using Haskell's Foreign Function Interface.

Expected Competition Performance

Paradox 3.0 is the CASC-J4 FNT division winner.

SInE 0.4

Kryštof Hoder
The University of Manchester, United Kingdom

Architecture

SiNE 0.4 is an axiom selection system for first order theories. It uses a syntactic approach based on symbols' presence in axioms and the conjecture. (When we say symbols, we mean function and predicate symbols taken together.) A relation D (as in "Defines") is created between symbols and axioms, which represents the fact that for a symbol there are some axioms that "give it its meaning". After the relation has been constructed, the axiom selection starts. At the beginning only the conjecture is selected, in each iteration the selection is extended by all axioms that are D-related to any symbol used in already selected formulae. The iteration continues until no more axioms are selected. The selected axioms and the conjecture are then handed to an underlying inference engine.

Strategies

In order to construct the D-relation, we compute for each symbol the number of axioms in which it appears, which we call the generality index of the symbol. Then each axiom is put into the D-relation of the least general symbol it contains. (If there are more symbols with lowest generality index, axiom the is put in the relation of all of them.) This strategy selects about 2% of axioms on problems CSR(075-109)+1. In order to get different sets of axioms for multiple proof attempts on each problem, we have introduced a benevolence parameter. Given benevolence b ≥ 1, formula F, which has the least general symbol with generality index g0, is put into the D-relations of all its symbols with generality index g ≤ b × g0. Another way to modify the axiom set is to add axioms that were used in proofs of previously proved problems (which used the same axiom set).

Implementation

The axiom selection is implemented in Python. Problems are accessed one by one as present in the batch file. First each problem's time limit is calculated. This calculation is "optimistic" in a way that it assumes that the success rate of problems to come will be the same as of the already encountered ones. (It gives a problem more than it's fair share of time, assuming that many of the problems won't use their whole time limit.) Each problem is attempted in five phases, each of them specifies different selection parameters (i.e., benevolence and whether the axioms from previous proofs are included). For each phase a D-relation is constructed (or reused if it was constructed for the same axiom set previously). Then axioms are selected and passed to an underlying prover. This version contains EP as an underlying prover, as it was used last year by the competition-winning version.

SInE is available from: 

    http://www.cs.man.ac.uk/~hoderk/sine/sine.tgz

Expected Competition Performance

SInE 0.3 was the CASC-J4 LTB division winner. SInE 0.4 is a minimally updated version for the new LTB rules.

TPS 3.20080227G1d

Peter B. Andrews1, Chad E. Brown2
1Carnegie Mellon University, USA, 2Saarland University, Germany

Architecture

TPS is a higher-order theorem proving system that has been developed over several decades under the supervision of Peter B. Andrews with substantial work by Eve Longini Cohen, Dale A. Miller, Frank Pfenning, Sunil Issar, Carl Klapper, Dan Nesmith, Hongwei Xi, Matthew Bishop, Chad E. Brown, and Mark Kaminski. TPS can be used to prove theorems of Church's type theory automatically, interactively, or semi-automatically [AB+96,AB06].

When searching for a proof, TPS first searches for an expansion proof [Mil87] or an extensional expansion proof [Bro07] of the theorem. Part of this process involves searching for acceptable matings [And81]. Using higher-order unification, a pair of occurrences of subformulas (which are usually literals) is mated appropriately on each vertical path through an expanded form of the theorem to be proved. The expansion proof thus obtained is then translated [Pfe87] without further search into a proof of the theorem in natural deduction style. The translation process provides an effective soundness check, but it is not actually used during the competition.

Strategies

Strategies used by TPS in the search process include:

Implementation

TPS has been developed as a research tool for developing, investigating, and refining a variety of methods of searching for expansion proofs, and variations of these methods. Its behavior is controlled by hundreds of flags. A set of flags, with values for them, is called a mode. 52 modes have been found which collectively suffice for automatically proving virtually all the theorems which TPS has proved automatically thus far. When searching for a proof in automatic mode, TPS tries each of these modes in turn for a specified amount of time.

TPS is implemented in Common Lisp, and is available from: 

    http://gtps.math.cmu.edu/tps.html

Expected Competition Performance

TPS is quite versatile when searching for proofs of higher-order theorems, but it is effectively slow when it must try many modes. Therefore, the performance of TPS is likely to depend very heavily on the way the competition is set up. If the emphasis is on speed, with short time limits, TPS may not do very well. On the other hand, if the emphasis is on the variety of theorems that can be proved, with very liberal time limits, TPS may do very well.

Vampire 10.0

Andrei Voronkov
University of Manchester, United Kingdom

No system description supplied.

Expected Competition Performance

Vampire 10.0 is the CASC-J4 FOF and CNF division winner.

Vampire 11.0

Kryštof Hoder, Andrei Voronkov
The University of Manchester, United Kingdom

Architecture

Vampire 11.0 is an automatic theorem prover for first-order classical logic. It consists of a shell and a kernel. The kernel implements the calculi of ordered binary resolution and superposition for handling equality. The splitting rule in kernel adds propositional parts to clauses, which are manipulated using binary decision diagrams (BDDs). 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 indexing is used to implement all major operations on sets of terms and literals. Although the kernel of the system works only with clausal normal forms, the shell accepts a problem in the full first-order logic syntax, clausifies it and performs a number of useful transformations before passing the result to the kernel. Also the axiom selection algorithm of last year's LTB divison winner SInE can be enabled as part of the preprocessing.

When a theorem is proved, the system produces a verifiable proof, which validates both the clausification phase and the refutation of the CNF.

Strategies

The Vampire 11.0 kernel provides a fairly large number of features for strategy selection. The most important ones are: The Vampire 11.0 core is a completely new Vampire, and it shares virtually no code with the previous versions. The automatic mode of Vampire 11.0, however, uses both the Vampire 11.0 core and Vampire 10.0 to solve problems, based on input problem classification that takes into account simple syntactic properties, such as being Horn or non-Horn, presence of equality, etc.

Implementation

Vampire 11.0 is implemented in C++. The supported compilers are gcc 4.1.x, gcc 4.3.x.

Expected Competition Performance

We expect Vampire 11.0 to perform comparably to the Vampire 10.0.

Waldmeister 806

Thomas Hillenbrand1, Bernd Löchner2
1Max-Planck-Institut für Informatik Saarbrücken, Germany, 2Technische Universität Kaiserslautern, Germany

No system description supplied.

Expected Competition Performance

Waldmeister 806 is the CASC-J4 UEQ division winner.

Waldmeister C09a

Thomas Hillenbrand
Max-Planck-Institut für Informatik, Germany

Architecture

Waldmeister C09a [Hil03] is a system for unit equational deduction. Its theoretical basis is unfailing completion in the sense of [BDP89] with refinements towards ordered completion (cf. [AHL03]). The system saturates the input axiomatization, distinguishing active facts, which induce a rewrite relation, and passive facts, which are the one-step conclusions of the active ones up to redundancy. The saturation process is parameterized by a reduction ordering and a heuristic assessment of passive facts [HJL99].

Waldmeister C09a is a minor upgrade of Waldmeister 806, the best feature of which is TPTP format output.

Implementation

The prover is coded in ANSI-C. It runs on Solaris, Linux, and newly also on MacOS X. In addition, it is now available for Windows users via the Cygwin platform. The central data strucures are: perfect discrimination trees for the active facts; group-wise compressions for the passive ones; and sets of rewrite successors for the conjectures. Visit the Waldmeister web pages at: 
    http://www.waldmeister.org

Strategies

The approach taken to control the proof search is to choose the search parameters according to the algebraic structure given in the problem specification [HJL99]. This is based on the observation that proof tasks sharing major parts of their axiomatization often behave similar. Hence, for a number of domains, the influence of different reduction orderings and heuristic assessments has been analyzed experimentally; and in most cases it has been possible to distinguish a strategy uniformly superior on the whole domain. In essence, every such strategy consists of an instantiation of the first parameter to a Knuth-Bendix ordering or to a lexicographic path ordering, and an instantiation of the second parameter to one of the weighting functions addweight, gtweight, or mixweight, which, if called on an equation s = t, return |s| + |t|, |max>(s,t)|, or |max>(s,t)| · (|s| + |t| + 1) + |s| + |t|, respectively, where |s| denotes the number of symbols in s.

Expected Competition Performance

Waldmeister C09a will output much nicer proofs than Waldmeister 806.

References

AB+96
Andrews P. B., Bishop M., Issar S., Nesmith. D., Pfenning F., Xi H. (1996), TPS: A Theorem-Proving System for Classical Type Theory, Journal of Automated Reasoning 16(3), pp.321-353.
AB06
Andrews P. B., Brown C. E. (2006), TPS: A Hybrid Automatic-Interactive System for Developing Proofs, Journal of Applied Logic 4(4), pp.367-395.
And81
Andrews P. B. (1981), Theorem Proving via General Matings, Journal of the ACM 28(2), pp.193-214.
And89
On Connections and Higher-Order Logic, Journal of Automated Reasoning 5(3), pp.257-291.
AS+07
Asperti A., Coen C., Tassi E., Zacchiroli S. (2007), User Interaction with the Matita Proof Assistant, Journal of Automated Reasoning 39(2), pp.109-139.
AT07
Asperti A., Tassi E. (2007), Higher order Proof Reconstruction from Paramodulation-Based Refutations: The Unit Equality Case, Kauers M., Kerber M., Miner R., Windsteiger W., Proceedings of the 6th International Conference on Mathematical Knowledge Management (Hagenberg, Austria), pp.146-160, Lecture Notes in Computer Science 4573.
AHL03
Avenhaus J., Hillenbrand T., Löchner B. (2003), On Using Ground Joinable Equations in Equational Theorem Proving, Journal of Symbolic Computation 36(1-2), pp.217-233, Elsevier Science.
BDP89
Bachmair L., Dershowitz N., Plaisted D.A. (1989), Completion Without Failure, Ait-Kaci H., Nivat M., Resolution of Equations in Algebraic Structures, pp.1-30, Academic Press.
BG98
Bachmair L., Ganzinger H. (1998), Equational Reasoning in Saturation-Based Theorem Proving, Bibel W., Schmitt P.H., Automated Deduction, A Basis for Applications, pp.352-397, Applied Logic Series 10, Kluwer Academic Publishers.
BT07
Barrett C., Tinelli C. (2007), CVC3, Damm W., Hermanns H., Proceedings of the 19th International Conference on Computer Aided Verification (Berlin, Germany), pp.298-302, Lecture Notes in Computer Science 4590, Springer-Verlag.
BFN96
Baumgartner P., Furbach U., Niemelä I. (1996), Hyper Tableaux, Alferes J., Pereira L., Orlowska E., Proceedings of JELIA'96: European Workshop on Logic in Artificial Intelligence (Evora, Portugal), pp.1-17, Lecture Notes in Artificial Intelligence 1126, Springer-Verlag.
BT03
Baumgartner P., Tinelli C. (2003), The Model Evolution Calculus, Baader F., Proceedings of the 19th International Conference on Automated Deduction (Miami, USA), pp.350-364, Lecture Notes in Artificial Intelligence 2741, Springer-Verlag.
BFT04
Baumgartner P., Fuchs A., Tinelli C. (2004), Darwin - A Theorem Prover for the Model Evolution Calculus, Sutcliffe G., Schulz S., Tammet T., Proceedings of the Workshop on Empirically Successful First Order Reasoning, 2nd International Joint Conference on Automated Reasoning (Cork, Ireland).
BT05
Baumgartner P., Tinelli C. (2005), The Model Evolution Calculus with Equality, Nieuwenhuis R., Proceedings of the 20th International Conference on Automated Deduction (Tallinn, Estonia), pp.392-408, Lecture Notes in Artificial Intelligence 3632, Springer-Verlag.
BFT06
Baumgartner P., Fuchs A., Tinelli C. (2006), Implementing the Model Evolution Calculus, International Journal on Artificial Intelligence Tools 15(1), pp.21-52.
BFP07
Baumgartner P., Furbach U., Pelzer B. (2007), Hyper Tableaux with Equality, Pfenning F., Proceedings of the 21st International Conference on Automated Deduction (Bremen, Germany), pp.492-507, Lecture Notes in Artificial Intelligence 4603, Springer-Verlag.
BK98
Benzmüller C., Kohlhase M. (1998), LEO - A Higher-Order Theorem Prover, Kirchner C., Kirchner H., Proceedings of the 15th International Conference on Automated Deduction (Lindau, Germany), pp.139-143, Lecture Notes in Artificial Intelligence 1421, Springer-Verlag.
Ben99
Benzmüller C. (1999), Extensional Higher-order Paramodulation and RUE-Resolution, Ganzinger H., Proceedings of the 16th International Conference on Automated Deduction (Trento, Italy), pp.399-413, Lecture Notes in Artificial Intelligence 1632, Springer-Verlag.
BP+07
Benzmüller C., Paulson L., Theiss F., Fietzke A. (2007), Progress Report on LEO-II - An Automatic Theorem Prover for Higher-Order Logic, Schneider K., Brandt J., Proceedings of the 20th International Conference on Theorem Proving in Higher Order Logics (Kaiserslautern, Germany), pp.33-48.
BP+08
Benzmüller C., Paulson L., Theiss F., Fietzke A. (2008), LEO-II - A Cooperative Automatic Theorem Prover for Higher-Order Logic, Baumgartner P., Armando A., Gilles D., Proceedings of the 4th International Joint Conference on Automated Reasoning (Sydney, Australia), pp.162-170, Lecture Notes in Artificial Intelligence 5195, Springer-Verlag.
BRS08
Benzmüller C., Rabe F., Sutcliffe G. (2008), THF0 - The Core TPTP Language for Classical Higher-Order Logic, Baumgartner P., Armando A., Gilles D., Proceedings of the 4th International Joint Conference on Automated Reasoning (Sydney, Australia), pp.491-506, Lecture Notes in Artificial Intelligence 5195, Springer-Verlag.
BS+08
Benzmüller C., Sorge V., Jamnik M., Kerber M. (2008), Combined Reasoning by Automated Cooperation, Journal of Applied Logic 6(3), pp.318-342.
Bib87
Bibel W. (1987), Automated Theorem Proving, Vieweg and Sohn.
BA98
Bishop M., Andrews P.B. (1998), Selectively Instantiating Definitions, Kirchner C., Kirchner H., Proceedings of the 15th International Conference on Automated Deduction (Lindau, Germany), pp.365-380, Lecture Notes in Artificial Intelligence 1421, Springer-Verlag.
Bis99
Bishop M. (1999), A Breadth-First Strategy for Mating Search, Ganzinger H., Proceedings of the 16th International Conference on Automated Deduction (Trento, Italy), pp.359-373, Lecture Notes in Artificial Intelligence 1632, Springer-Verlag.
BK+08
Bongio J., Katrak C., Lin H., Lynch C., McGregor R. (2008), Encoding First Order Proofs in SMT, Krstic S., Oliveras A., Proceedings of the 5th International Workshop on Satisfiability Modulo Theories (Berlin, Germany), pp.71-84, Electronic Notes in Theoretical Computer Science 198(2).
BDD07
Bonichon R., Delahaye D., Doligez D. (2007), Zenon : An Extensible Automated Theorem Prover Producing Checkable Proofs, Dershowitz N., Voronkov A., Proceedings of the 14th International Conference on Logic for Programming, Artificial Intelligence, and Reasoning (Yerevan, Armenia), pp.151-165, Lecture Notes in Artificial Intelligence 4790. -->
Bro02
Brown C.E. (2002), Solving for Set Variables in Higher-Order Theorem Proving, Voronkov A., Proceedings of the 18th International Conference on Automated Deduction (Copenhagen, Denmark), pp.408-422, Lecture Notes in Artificial Intelligence 2392, Springer-Verlag.
Bro07
Brown C. E. (2007), Automated Reasoning in Higher-Order Logic: Set Comprehension and Extensionality in Church's Type Theory, Studies in Logic: Logic and Cognitive Systems 10, College Publications.
BS09
Brown C. E., Smolka G. (2009), Terminating Tableaux for the Basic Fragment of Simple Type Theory, Giese M., Waaler A., Proceedings of the 18th International Conference on Automated Reasoning with Analytic Tableaux and Related Methods (Oslo, Norway), pp.138-151, Lecture Notes in Artificial Intelligence 5697, Springer-Verlag.
CS03
Claessen K., Sorensson N. (2003), New Techniques that Improve MACE-style Finite Model Finding, Baumgartner P., Fermueller C., Proceedings of the CADE-19 Workshop: Model Computation - Principles, Algorithms, Applications (Miami, USA).
ES04
E{\'e}n N., Sörensson N. (2004), An Extensible SAT-solver, Giunchiglia E., Tacchella A., Proceedings of the 6th International Conference on Theory and Applications of Satisfiability Testing (Santa Margherita Ligure, Italy), pp.502-518, Lecture Notes in Computer Science 2919, Springer-Verlag.
GK03
Ganzinger H., Korovin K. (2003), New Directions in Instantiation-Based Theorem Proving, Kolaitis P., Proceedings of the 18th IEEE Symposium on Logic in Computer Science (Ottawa, Canada), pp.55-64.

GK04
Ganzinger H., Korovin K. (2004), Integrating Equational Reasoning into Instantiation-Based Theorem Proving, Marcinkowski J., Tarlecki A., Proceedings of the 18th International Workshop on Computer Science Logic, 13th Annual Conference of the EACSL (Karpacz, Poland), pp.71-84, Lecture Notes in Computer Science 3210.
HJL99
Hillenbrand T., Jaeger A., Löchner B. (1999), Waldmeister - Improvements in Performance and Ease of Use, Ganzinger H., Proceedings of the 16th International Conference on Automated Deduction (Trento, Italy), pp.232-236, Lecture Notes in Artificial Intelligence 1632, Springer-Verlag.
Hil03
Hillenbrand T. (2003), Citius altius fortius: Lessons Learned from the Theorem Prover Waldmeister, Dahn I., Vigneron L., Proceedings of the 4th International Workshop on First-Order Theorem Proving (Valencia, Spain), Electronic Notes in Theoretical Computer Science 86(1), Elsevier Science.
Hur03
Hurd J. (2003), First-Order Proof Tactics in Higher-Order Logic Theorem Provers, Archer M., Di Vito B., Munoz C., Proceedings of the 1st International Workshop on Design and Application of Strategies/Tactics in Higher Order Logics (Rome, Italy), pp.56-68, NASA Technical Reports NASA/CP-2003-212448.
Iss90
Issar S. (1990), Path-Focused Duplication: A Search Procedure for General Matings, Dietterich T. Swartout W., Proceedings of the 8th National Conference on Artificial Intelligence (Boston, USA), pp.221-226, American Association for Artificial Intelligence / MIT Press.
Kor08a
Korovin K. (2008), An Invitation to Instantiation-Based Reasoning: From Theory to Practice, Podelski A., Voronkov A., Wilhelm R., Volume in Memoriam of Harald Ganzinger, Springer-Verlag.
Kor08b
Korovin K. (2008), iProver - An Instantiation-Based Theorem Prover for First-order Logic (System Description), Baumgartner P., Armando A., Gilles D., Proceedings of the 4th International Joint Conference on Automated Reasoning (Sydney, Australia), Lecture Notes in Artificial Intelligence.
LS01
Letz R., Stenz G. (2001), Model Elimination and Connection Tableau Procedures, Robinson A., Voronkov A., Handbook of Automated Reasoning, pp.2015-2114, Elsevier Science.
Loe04
Loechner B. (2004), What to Know When Implementing LPO, Sutcliffe G., Schulz S., Tammet T., Proceedings of the Workshop on Empirically Successful First Order Reasoning, 2nd International Joint Conference on Automated Reasoning (Cork, Ireland).
Lov78 Loveland D.W. (1978), Automated Theorem Proving : A Logical Basis, Elsevier Science.
MW97
McCune W.W., Wos L. (1997), Otter: The CADE-13 Competition Incarnations, Journal of Automated Reasoning 18(2), pp.211-220.
McC03a
McCune W.W. (2003), Otter 3.3 Reference Manual, ANL/MSC-TM-263, Argonne National Laboratory, Argonne, USA.
McC03b
McCune W.W. (2003), Mace4 Reference Manual and Guide, ANL/MSC-TM-264, Argonne National Laboratory, Argonne, USA.
Mil87
Miller D. (1987), A Compact Representation of Proofs, Studia Logica 46(4), pp.347-370.
NPW02
Nipkow T., Paulson L., Wenzel M. (2002), Isabelle/HOL: A Proof Assistant for Higher-Order Logic, Lecture Notes in Computer Science 2283, Springer-Verlag.
Nip89
Nipkow T. (1989), Equational Reasoning in Isabelle, Science of Computer Programming 12(2), pp.123-149.
OB03
Otten J., Bibel W. (2003), leanCoP: Lean Connection-Based Theorem Proving, Journal of Symbolic Computation 36(1-2), pp.139-161.
Ott08a
Otten J. (2008), leanCoP 2.0 and {\sf ileancop 1.2}: High Performance Lean Theorem Proving in Classical and Intuitionistic Logic, Baumgartner P., Armando A., Gilles D., Proceedings of the 4th International Joint Conference on Automated Reasoning (Sydney, Australia), pp.Accepted, Lecture Notes in Artificial Intelligence.
Ott08b
Restricting Backtracking in Connection Calculi, Technical Report, Institut für Informatik, University of Potsdam, Potsdam, Germany.
PN94
Paulson L.C., Nipkow T. (1994), Isabelle: A Generic Theorem Prover, Lecture Notes in Computer Science 828, Springer-Verlag.
Pau99
Paulson L. (1999), A Generic Tableau Prover and its Integration with Isabelle, Artificial Intelligence 5(3), pp.73-87.
PW07
Pelzer B., Wernhard C. (2007), System Description: E-KRHyper, Pfenning F., Proceedings of the 21st International Conference on Automated Deduction (Bremen, Germany), pp.508-513, Lecture Notes in Artificial Intelligence 4603, Springer-Verlag.
Pfe87
Pfenning F. (1987), Proof Transformations in Higher-Order Logic, PhD thesis, Carnegie-Mellon University (Pittsburg, USA).
PZ00
Plaisted D.A., Zhu Y. (2000), Ordered Semantic Hyper-linking, Journal of Automated Reasoning 25(3), pp.167-217.
Sch02
Schulz S. (2002), E: A Brainiac Theorem Prover, AI Communications 15(2-3), pp.111-126.
Sch04a
Schulz S. (2004), System Abstract: E 0.81, Rusinowitch M., Basin D., Proceedings of the 2nd International Joint Conference on Automated Reasoning (Cork, Ireland), pp.223-228, Lecture Notes in Artificial Intelligence 3097.
Sch04b
Schulz S. (2004), Simple and Efficient Clause Subsumption with Feature Vector Indexing, Sutcliffe G., Schulz S., Tammet T., Proceedings of the Workshop on Empirically Successful First Order Reasoning, 2nd International Joint Conference on Automated Reasoning (Cork, Ireland).
SBA06
Siekmann J., Benzmüller C., Autexier S. (2006), Computer Supported Mathematics with OMEGA, Journal of Applied Logic 4(4), pp.533-559.
SGS07
Streeter M., Golovin D., Smith S.F. (2007), Combining Multiple Heuristics Online, Holte R.C., Howe A., Proceedings of the 22nd Conference on Artificial Intelligence (Vancouver, Canada), pp.1197-1203, AAAI Press.
SB+09
Sutcliffe G., Benzmüller C., Brown C. E., Theiss F. (2009), Progress in the Development of Automated Theorem Proving for Higher-order Logic, Schmidt R., Proceedings of the 22nd International Conference on Automated Deduction (Montreal Canada), pp.116-130, Lecture Notes in Artificial Intelligence 5663, Springer-Verlag.
TB06
Theiss F., Benzmüller C. (2006), Proceedings of the 6th International Workshop on the Implementation of Logics, Benzmüller C., Fischer B., Sutcliffe G., pp.7-23, CEUR Workshop Proceedings 212.
Ull89
Ullman J. (1989), Principles of Database and Knowledge-Base Bystems, Computer Science Press, Inc..
Wer03
Wernhard C. (2003), System Description: KRHyper, Fachberichte Informatik 14-2003, Universität Koblenz-Landau, Koblenz, Germany.