Skip to Main content Skip to Navigation
Conference papers

Uniform Derivation of Satisfiability Procedures

Michaël Rusinowitch 1
1 PROTHEO - Constraints, automatic deduction and software properties proofs
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : joint work with A.Armando - S. Ranise - In verification with proof assistants (such as PVS, HOL, and Nqthm), decision procedures are typically used for eliminating trivial subgoals represented for instance as sequents modulo a background theory. These theories axiomatize standard data-types such bit-vectors and have proved to be quite useful for, e.g., hardware verification. Elimination of trivial sequents often reduces to the problem of proving the unsatisfiability of conjunctions of literals modulo a background theory , which is the problem we shall consider here. We show how a superposition-based inference system for first-order equational logic can be used almost directly as a satisfiability procedure for various theories including lists, arrays, extensional arrays and combinations of them. We also give a similar decision procedure for homomorphism.
Document type :
Conference papers
Complete list of metadatas
Contributor : Publications Loria <>
Submitted on : Tuesday, September 26, 2006 - 2:48:11 PM
Last modification on : Wednesday, January 8, 2020 - 2:17:17 PM


  • HAL Id : inria-00100611, version 1



Michaël Rusinowitch. Uniform Derivation of Satisfiability Procedures. Résolution de contraintes du 1er ordre dans des structures variées, A. Colmerauer, 2001, Marseille, France, 2 p. ⟨inria-00100611⟩



Record views