Physical Sciences and Mathematics Commons^™

A new language, called constraint CNF, is proposed. It integrates propositional logic with constraints stemming from constraint programming (CP). A family of algorithms is designed to solve problems expressed in constraint CNF. These algorithms build on techniques from both propositional satisfiability (SAT) and CP. The result is a uniform language and an algorithmic framework, which allow us to gain a deeper understanding of the relation between the solving techniques used in SAT and in CP and apply them together.

Constraint answer set programming is a promising research direction that integrates answer set programming with constraint processing. This research direction often informally relates itself to the field of Satisfiability Modulo Theory. Yet the exact formal link is obscured as the terminology and concepts used in these two research fields differ. The goal of this paper to make the link between these two fields precise.