Theorem Proving for Hierarchic First-Order Theories

Leo Bachmair, Harald Ganzinger, and Uwe Waldmann

In Giorgio Levi and Hélène Kirchner, editors, Algebraic and Logic Programming, Third International Conference, LNCS 632, pages 420-434, Volterra, Italy, September 2-4, 1992. Springer-Verlag.

Revised version: Refutational theorem proving for hierarchic first-order theories, in AAECC, 5(3/4):193-212, 1994.

Abstract: We extend previous results on theorem proving for first-order clauses with equality to hierarchic first-order theories. Semantically such theories are confined to conservative extensions of the base models. It is shown that superposition together with variable abstraction and constraint refutation is refutationally complete for sufficiently complete theories. For the proof we introduce a concept of approximation between theorem proving systems, which makes it possible to reduce the problem to the known case of (flat) first-order theories. These results allow the modular combination of a superposition-based theorem prover with an arbitrary refutational prover for the primitive base theory, whose axiomatic repesentation in some logic may remain hidden. Furthermore they can be used to eliminate existentially quantified predicate symbols from certain second-order formulae.


Previous | Up | Next
Uwe Waldmann <uwe@mpi-inf.mpg.de>, 1997-10-02.
Imprint | Data Protection