Answer Set Programming: An Introduction to the Special Issue

What distinguishes ASP from other declarative paradigms, like satisfiability (SAT) or constraint solving (CSP), is its underlying modeling language and the semantics involved. Problems are specified using logic programminglike rules, with some convenient extensions facilitating compact and readable problem descriptions. Sets of such rules, or answer set programs, come with an intuitive, well-defined and, by now, well-accepted semantics. This semantics has its roots in research in knowledge representation, in particular nonmonotonic reasoning, and avoids the pitfalls of earlier attempts such as the procedural semantics of Prolog based on negation as finite failure. This semantics was originally called the stable-model semantics and was defined for normal logic programs only, that is, programs consisting of rules with a single atom in the head and any finite number of atoms, possibly preceded by default negation, not, in the body. Stable models were later generalized to broader classes of programs, where the semantics can no longer be defined in terms of sets of atoms, which is a natural representation of classical models. Instead, it was defined by means of some sets of literals. For this reason the term answer set was adopted as more adequate (although answer sets also have a straightforward interpretation as models, albeit three-valued ones). Over the last decade or so, ASP has evolved into a vibrant and active research area that produced not only theoretical insights, but also highly effective and useful software tools and interesting and promising applications.