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

Authors

  • Tomi Janhunen Helsinki Institute for Information Technology and Aalto University
  • Shahab Tasharrofi Helsinki Institute for Information Technology and Aalto University
  • Eugenia Ternovska Simon Fraser University

DOI:

https://doi.org/10.1609/aaai.v30i1.10111

Keywords:

Knowledge Representation and Reasoning, Logic Programming, Special-purpose Propagators, SAT Solvers

Abstract

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.

Downloads

Published

2016-02-21

How to Cite

Janhunen, T., Tasharrofi, S., & Ternovska, E. (2016). SAT-to-SAT: Declarative Extension of SAT Solvers with New Propagators. Proceedings of the AAAI Conference on Artificial Intelligence, 30(1). https://doi.org/10.1609/aaai.v30i1.10111

Issue

Section

Technical Papers: Knowledge Representation and Reasoning