Congruence Closure with Free Variables

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.
Type de document :
Communication dans un congrès
Tools and Algorithms for Construction and Analysis of Systems (TACAS), 2017, Uppsala, Sweden. 205, pp.220 - 230, 2017, 〈10.1007/10721959_17〉
Liste complète des métadonnées

Littérature citée [27 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01590918
Contributeur : Pascal Fontaine <>
Soumis le : mercredi 20 septembre 2017 - 14:23:28
Dernière modification le : jeudi 21 septembre 2017 - 01:08:55

Fichier

Barbosa1.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Haniel Barbosa, Pascal Fontaine, Andrew Reynolds. Congruence Closure with Free Variables. Tools and Algorithms for Construction and Analysis of Systems (TACAS), 2017, Uppsala, Sweden. 205, pp.220 - 230, 2017, 〈10.1007/10721959_17〉. 〈hal-01590918〉

Partager

Métriques

Consultations de la notice

63

Téléchargements de fichiers

5