Answer-set Programming --- Solving Search Problems with Logic
Mirek Truszczynski
University of Kentucky
Answer-set programming is a way of using logic to solve search problems.
A general approach is as follows. Given a search problem, one first
designs a theory in some logic so that models of this theory represent
solutions to the problem. Next, one computes computes a model of the
corresponding theory and, finally, one reads back the solution encoded
by the model.
Several answer-set programming formalisms have been developed on the
basis of logic programming with the semantics of stable models. The
logic of predicate calculus also gives rise to effective implementations
of the ASP paradigm, similar in the spirit to logic programming with
stable model semantics and with a similar scope of applicability.
In the talk we will present and contrast the two approaches, emphasizing
their fundamental aspects: high-level modeling, rooted in nonmonotonic
reasoning and declarative programming, and low-level search, related to
satisfiability. We will discuss basic results concerning the complexity
and expressive power. We will discuss some of the current research
directions and open problems.
Deepak Ramachandran
Last modified: Mon Mar 27 11:38:17 CST 2006