SAT-to-SAT: Declarative Extension of SAT Solvers with New Propagators

Tomi Janhunen, Shahab Tasharrofi, Eugenia Ternovska

Research output: Chapter in Book/Report/Conference proceedingConference article in proceedingsScientificpeer-review


Special-purpose propagators speed up solving logic programs by inferring facts that are hard to deduce otherwise. However, implementing special-purpose propagators is a non-trivial task and requires expert knowledge of solvers. This paper proposes a novel approach in logic programming that allows (1) logical specification of both the problem itself and its propagators and (2) automatic incorporation of such propagators into the solving process. We call our proposed language P[R] and our solver SAT-to-SAT because it facilitates communication between several SAT solvers. Using our proposal, non-specialists can specify new reasoning methods (propagators) in a declarative fashion and obtain a solver that benefits from both state-of-the-art techniques implemented in SAT solvers as well as problem-specific reasoning methods that depend on the problem's structure. We implement our proposal and show that it outperforms the existing approach that only allows modeling a problem but does not allow modeling the reasoning methods for that problem.
Original languageEnglish
Title of host publicationProceedings of the Thirtieth AAAI Conference on Artificial Intelligence (AAAI-16)
PublisherAAAI Press
Publication statusPublished - 2016
MoE publication typeA4 Conference publication
EventAAAI Conference on Artificial Intelligence - Phoenix, United States
Duration: 12 Feb 201617 Feb 2016
Conference number: 30

Publication series

ISSN (Print)2374-3468


ConferenceAAAI Conference on Artificial Intelligence
Abbreviated titleAAAI
Country/TerritoryUnited States


Dive into the research topics of 'SAT-to-SAT: Declarative Extension of SAT Solvers with New Propagators'. Together they form a unique fingerprint.

Cite this