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

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

Researchers

Research units

  • Simon Fraser University

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.

Details

Original languageEnglish
Title of host publicationProceedings of the Thirtieth AAAI Conference on Artificial Intelligence (AAAI-16)
Publication statusPublished - 2016
MoE publication typeA4 Article in a conference publication
EventAAAI Conference on Artificial Intelligence - Phoenix, United States
Duration: 12 Feb 201617 Feb 2016
Conference number: 30

Publication series

Name
ISSN (Print)2374-3468

Conference

ConferenceAAAI Conference on Artificial Intelligence
Abbreviated titleAAAI
CountryUnited States
CityPhoenix
Period12/02/201617/02/2016

ID: 5545956