Predicate-calculus-based logics for modeling and solving search problems

• Published in: ACM transactions on computational logic 2006-01, Vol.7 (1), p.38-83
• Main Authors: East, Deborah, Truszczynski, Miroslaw
• Format: Article
• Language: English
• Subjects: Boolean; Calculus; Logic programming; Searches; Semantics; Studies
• ISSN: 1529-3785; 1557-945X
• DOI: 10.1145/1119439.1119441

The answer-set programming (ASP) paradigm is a way of using logic to solve search problems. Given a search problem, to solve it one designs a logic theory so that models of this theory represent problem solutions. To compute a solution to the problem, one computes a model of the theory. Several answer-set programming formalisms have been developed on the basis of logic programming with the semantics of answer sets. In this article we show that predicate logic also gives rise to effective implementations of the ASP paradigm, similar in spirit to logic programming with the answer-set semantics and with a similar scope of applicability. Specifically, we propose two logics based on predicate calculus as formalisms for encoding search problems. We show that the expressive power of these logics is given by the class NPMV. We demonstrate their use in programming and discuss computational approaches to model finding. To address this latter issue, we follow a two-pronged approach. On the one hand, we show that the problem can be reduced to that of computing models of propositional theories and, more generally, of collections of pseudo-Boolean constraints. Consequently, programs (solvers) developed in the areas of propositional and pseudo-Boolean satisfiability can be used to compute models of theories in our logics. On the other hand, we develop native solvers designed specifically to exploit features of our formalisms. We present experimental results demonstrating the computational effectiveness of the overall approach.