{NRCL} - a model building approach to the {Bernays-Schönfinkel} fragment

Gábor Alagi 1, 2 Christoph Weidenbach 2, 1
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
Abstract : We combine constrained literals for model representation with key concepts from first-order superposition and propositional conflict-driven clause learning (CDCL) to create the new calculus Non-Redundant Clause Learning (NRCL) deciding the Bernays-Schönfinkel fragment. We use first-order literals constrained by disequalities between tuples of terms for compact model representation. From superposition, NRCL inherits the abstract redundancy criterion and the monotone model operator. CDCL adds the dynamic, conflict-driven search for a model. As a result, NRCL finds a false clause modulo the current model candidate effectively. It guides the derivation of a first-order ordered resolvent that is never redundant. Similar to 1UIP-learning in CDCL, the learned resolvent induces backtracking and, by blocking the previous conflict state via propagation, it enforces progress towards finding a model or a refutation. The non-redundancy result also implies that only finitely many clauses can be generated by NRCL on the Bernays-Schönfinkel fragment, which proves termination.
Document type :
Conference papers
Liste complète des métadonnées

Contributor : Stephan Merz <>
Submitted on : Wednesday, December 23, 2015 - 11:48:35 AM
Last modification on : Tuesday, February 19, 2019 - 3:40:03 PM




Gábor Alagi, Christoph Weidenbach. {NRCL} - a model building approach to the {Bernays-Schönfinkel} fragment. Frontiers of Combining Systems, 10th International Symposium (FroCos 2015), 2015, Wroclaw, Poland. pp.69-84, ⟨10.1007/978-3-319-24246-0_5⟩. ⟨hal-01247991⟩



Record views