Answer Set Programming: From Model Computation to Problem Solving

The term answer set programming (ASP) was coined by Vladimir Lifschitz to refer to a new declarative programming paradigm that has its roots in sta-ble model (answer set) semantics of logic programs and implementations of this semantics developed in the late 90's. When working with the implementa-tions it became evident that they are instantiations of a dierent programming paradigm [5, 8, 15, 18, 19] than that of standard logic programming. This new ASP paradigm can be characterized as follows. In ASP programs are theories of some formal system with a semantics that assigns to a theory a collection of sets (models) referred to as answer sets of the program. In order to solve a problem using ASP a program is devised such that the solutions of the problem can be retrieved from the answer sets of the program. An ASP solver is a system that takes as input a program and computes answer sets for it. While ASP has its roots in logic programming, it could be based on other formal systems such as propositional or rst-order logic, too. In fact, the basic idea of ASP is similar to, e.g., SAT-based planning or constraint satisfactio