Skip to Main content Skip to Navigation
New interface
Reports (Research report)

Congruence Closure with Free Variables

Haniel Barbosa 1, 2, 3 Pascal Fontaine 2, 3 Andrew Reynolds 4 
2 VERIDIS - Modeling and Verification of Distributed Algorithms and Systems
MPII - Max-Planck-Institut für Informatik, Inria Nancy - Grand Est, LORIA - FM - Department of Formal Methods
3 MOSEL - Proof-oriented development of computer-based systems
LORIA - FM - Department of Formal Methods
Abstract : Many verification techniques nowadays successfully rely on SMT solvers as back-ends to automatically discharge proof obligations. These solvers generally rely on various instantiation techniques to handle quantifiers. We here show that the major instantiation techniques in SMT solving can be cast in a unifying framework for handling quantified formulas with equality and uninterpreted functions. This framework is based on the problem of E-ground (dis)unification, a variation of the classic rigid E-unification problem. We introduce a sound and complete calculus to solve this problem in practice: Congruence Closure with Free Variables (CCFV). Experimental evaluations of implementations of CCFV in the state-of-the-art solver CVC4 and in the solver veriT exhibit improvements in the former and makes the latter competitive with state-of-the-art solvers in several benchmark libraries stemming from verification efforts.
Document type :
Reports (Research report)
Complete list of metadata
Contributor : Haniel Barbosa Connect in order to contact the contributor
Submitted on : Monday, January 23, 2017 - 7:20:56 PM
Last modification on : Friday, November 18, 2022 - 9:25:32 AM
Long-term archiving on: : Monday, April 24, 2017 - 3:31:34 PM


Files produced by the author(s)


  • HAL Id : hal-01442691, version 2


Haniel Barbosa, Pascal Fontaine, Andrew Reynolds. Congruence Closure with Free Variables. [Research Report] Inria, Loria, Universite de Lorraine, UFRN, University of Iowa. 2017. ⟨hal-01442691v2⟩



Record views


Files downloads