Galois, Inc., USA

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.

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.

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, an interpretation of known
functions and relations is manually constructed to make many of their
standard properties valid in the finite model. For example, the domain
of the model is the set *{0,...,7}*, and the higher order logic
arithmetic functions are interpreted in the model modulo *8*.
Unknown functions and relations are interpreted randomly, but with a
bias towards making supporting theorems valid in the model. The finite
model strategy carries over to TPTP problems, by manually interpreting
a collection of functions and relations that appear in TPTP axiom
files in such a way as to make the axioms valid in the model.

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

There have been only minor changes to Metis 2.2 since CASC 22, so it is expected to perform at approximately the same level in CASC J5 and end up in the lower half of the table. However, it is possible that Metis 2.2 might get a boost from its finite model clause weighting, since this year the CASC competition rules have changed so that function and relation names are no longer obfuscated.

- Hur03
- Hurd J. (September 2003),
**First-Order Proof Tactics in Higher-Order Logic Theorem Provers**, Archer M., Di Vito B., Muñoz C.,*Design and Application of Strategies/Tactics in Higher Order Logics (STRATA 2003)*(Rome, Italy), pp.56-68, NASA Technical Report CP-2003-212448, NASA.