Vampire (theorem prover)

From Wikipedia, the free encyclopedia
  (Redirected from Vampire theorem prover)
Jump to: navigation, search
Vampire (theorem prover)
Developer(s) Andrei Voronkov
Alexandre Riazanov[1][2]
Kryštof Hoder[3]
Type Automated theorem proving
Website www.vprover.org

Vampire is an automatic theorem prover for first-order classical logic developed in the School of Computer Science at the University of Manchester by Andrei Voronkov together with Kryštof Hoder and previously with Alexandre Riazanov. So far it has won the "world cup for theorem provers" (the CADE ATP System Competition) in the most prestigious CNF (MIX) division eleven times (1999, 2001–2010).[1][4]

Background[edit]

Vampire's kernel implements the calculi of ordered binary resolution and superposition for handling equality. The splitting rule and negative equality splitting can be simulated by the introduction of new predicate definitions and dynamic folding of such definitions. A DPLL-style algorithm splitting is also supported. A number of standard redundancy criteria and simplification techniques are used for pruning the search space: tautology deletion, subsumption resolution, rewriting by ordered unit equalities, basicness restrictions and irreducibility of substitution terms. The reduction ordering used is the standard Knuth-Bendix ordering.

A number of efficient indexing techniques are used to implement all major operations on sets of terms and clauses. Run-time algorithm specialisation is used to accelerate forward matching.

Although the kernel of the system works only with clausal normal forms, the preprocessor component 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. When a theorem is proven, the system produces a verifiable proof, which validates both the clausification phase and the refutation of the conjunctive normal form.

Along with proving theorems, Vampire has other related functionalities such as generating interpolants.

Executables can be obtained from the system website [5] A somewhat outdated version is available under the GNU Lesser General Public License as part of Sigma KEE.[6]

References[edit]

  1. ^ a b Riazanov, A.; Voronkov, A. (2002). "The design and implementation of VAMPIRE". AI Communications 15 (2-3/2002): 91–110. ISSN 0921-7126.  edit
  2. ^ http://riazanov.webs.com/Riazanov_PhD_thesis.pdf (PhD thesis of Dr. Alexandre Riazanov on the implementation of Vampire)
  3. ^ Urban, J.; Hoder, K.; Voronkov, A. (2010). "Mathematical Software – ICMS 2010". Lecture Notes in Computer Science 6327. p. 155. doi:10.1007/978-3-642-15582-6_30. ISBN 978-3-642-15581-9.  |chapter= ignored (help) edit
  4. ^ Voronkov, A. (1995). "The anatomy of vampire". Journal of Automated Reasoning 15 (2): 237–265. doi:10.1007/BF00881918.  edit
  5. ^ http://www.vprover.org
  6. ^ http://sigmakee.cvs.sourceforge.net/viewvc/sigmakee/Vampire