Answer Set Programming - a Declarative Knowledge Representation Paradigm

Ilkka Niemelä and Mirek Truszczynski
Section: Logic and Computation
Level: Introductory


A fundamental motivation behind the study of nonmonotonic logics has been an expectation that nonmonotonic reasoning will result in computationally feasible general purpose knowledge representation tools. The emergence in recent years of several automated reasoning systems based on nonmonotonic logics validates this view.

In this course we discuss a computational paradigm of answer set programming that is rooted in default logic and logic programming with negation. The crucial idea of answer set programming is to encode application problems so that their solutions be fully described by different answer sets (extensions, stable models, etc., depending on the nonmonotonic formalism used) of the corresponding program.

We will discuss theoretical foundations of answer set programming such as the stable model semantics and the well-founded semantics of logic programs, as well as algorithms to compute stable models. We will discuss implemented systems and their performance, and demonstrate their use. We will focus on issues of modeling application problems as answer set programs and consider, in particular, planning, reasoning about action, product configuration, constraint satisfaction, satisfiability, standard AI puzzles and combinatorial optimization.

Course Outline


Basic knowledge of propositional and first-order logic.



Prof. Ilkka Niemelä
Helsinki University of Technology
Dept. of Computer Science and Engineering
Laboratory for Theoretical Computer Science
P.O.Box 5400, FIN-02015 HUT, Finland
Phone +358-9-451 3290
Fax +358-9-451 3369

Prof. Mirek Truszczynski
University of Kentucky
Dept. of Computer Science
Lexington, KY 40506-0046
Phone +1-859-257-3961
Fax +1-859-323-1971