Computer Science – Logic in Computer Science
Scientific paper
2002-11-25
Computer Science
Logic in Computer Science
34 pages, 4 tables; extended version of papers that appeared in Proceedings of AAAI-2000 and Proceedings of KI-2001
Scientific paper
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 theory in the logic so that models of this theory represent problem solutions. To compute a solution to a problem one needs to compute a model of the corresponding theory. Several answer-set programming formalisms have been developed on the basis of logic programming with the semantics of stable models. In this paper we show that also the logic of predicate calculus gives rise to effective implementations of the ASP paradigm, similar in spirit to logic programming with stable model 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 NP-search. We demonstrate how to use them in programming and develop computational tools for model finding. In the case of one of the logics our techniques reduce the problem to that of propositional satisfiability and allow one to use off-the-shelf satisfiability solvers. The language of the other logic has more complex syntax and provides explicit means to model some high-level constraints. For theories in this logic, we designed our own solver that takes advantage of the expanded syntax. We present experimental results demonstrating computational effectiveness of the overall approach.
East Deborah
Truszczynski Miroslaw
No associations
LandOfFree
Propositional satisfiability in declarative programming does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Propositional satisfiability in declarative programming, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Propositional satisfiability in declarative programming will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-253703