de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch
 
Hilfe Wegweiser Datenschutzhinweis Impressum Kontakt
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Forschungspapier

NRCL - A Model Building Approach to the Bernays-Schönfinkel Fragment

MPG-Autoren
http://pubman.mpdl.mpg.de/cone/persons/resource/persons79168

Alagi,  Gábor
Automation of Logic, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons45719

Weidenbach,  Christoph
Automation of Logic, MPI for Informatics, Max Planck Society;

Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
Volltexte (frei zugänglich)

arXiv:1502.05501.pdf
(Preprint), 385KB

Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

Alagi, G., & Weidenbach, C. (2015). NRCL - A Model Building Approach to the Bernays-Schönfinkel Fragment. Retrieved from http://arxiv.org/abs/1502.05501.


Zitierlink: http://hdl.handle.net/11858/00-001M-0000-0025-B02B-F
Zusammenfassung
We combine key ideas from first-order superposition and propositional CDCL to create the new calculus NRCL deciding the Bernays-Sch\"onfinkel fragment. It inherits the abstract redundancy criterion and the monotone model operator from superposition. CDCL adds to NRCL the dynamic, conflict-driven search for an atom ordering inducing a model. As a result, in NRCL a false clause can be effectively found modulo the current model assumption. 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 via propagation blocks the previous conflict state for the rest of the search. Since learned clauses are never redundant, only finitely many can be generated by NRCL on the Bernays-Sch\"onfinkel fragment, which provides a nice argument for termination.