What Is Answer Set Programming?

Answer set programming is a declarative programming paradigm in which a problem is described as a set of logical rules and solutions are read off as the stable models, or answer sets, of that description. It belongs to the logic programming family, alongside Prolog and Datalog, but differs from Prolog in a decisive way: the order of rules and of subgoals carries no procedural meaning, and computation is a model-generation task rather than a query-driven proof search. A programmer states what counts as a solution; a solver enumerates the assignments that satisfy that statement.

The paradigm emerged in the late 1990s from work on the semantics of negation in logic programs, and its formal basis is the stable model semantics introduced by Michal Gelfond and Vladimir Lifschitz in 1988. It is aimed at combinatorial search problems in the complexity class NP and, with disjunctive rules, at problems one level higher in the polynomial hierarchy, which makes planning, configuration, diagnosis, and constraint problems its natural territory.

Stable Model Semantics

The semantics defines which sets of atoms count as answer sets of a program containing negation as failure. Given a candidate set of atoms, the program is reduced by deleting every rule whose negated literals conflict with the candidate and by stripping the remaining negated literals; the candidate is a stable model when it is exactly the minimal model of that reduct. The definition makes each answer set self-supporting, ruling out conclusions that only justify themselves in a circular way, and it gives a clean account of default reasoning, where a conclusion holds unless something contradicts it. A program may have one answer set, many, or none, and this multiplicity is the point: each answer set corresponds to one solution of the encoded problem. Lifschitz's course notes on answer set programming work through the reduct construction and its consequences in detail.

Language Constructs and the Ground-and-Solve Pipeline

Practical programs are written over a first-order language with variables, function symbols, and arithmetic, then processed in two stages. A grounder instantiates the variables to produce a finite propositional program, and a solver searches that program for stable models using conflict-driven clause learning techniques adapted from Boolean satisfiability solving. Beyond plain rules, the modeling language supplies integrity constraints that eliminate unwanted candidates, choice rules that generate alternatives, cardinality and weight constraints that express counting and resource limits, aggregates such as sums and minima, and optimization statements that rank answer sets by cost. The usual idiom is generate and test: choice rules propose candidate solutions, constraints discard those that violate the specification, and optimization directives select the best of what remains.

Solvers and Hybrid Extensions

The reference implementation is clingo from the Potsdam Answer Set Solving Collection, which combines the grounder gringo with the solver clasp in a single system and supports incremental grounding and solving for problems whose horizon grows step by step. Alternative systems include DLV, which introduced disjunctive logic programming to practice, and smodels, an early solver that established cardinality constraints. Because pure grounding is impractical for large numeric domains, current work extends the paradigm with theory reasoning, attaching constraint, difference logic, or linear arithmetic propagators to the search, and a tutorial on hybrid answer set solving describes how such theory atoms are integrated. Related extensions cover probabilistic reasoning, temporal and dynamic logics for action domains, and interfaces that embed a solver inside a conventional programming language.

Applications

Answer set programming has applications in fields including:

• Automated planning, scheduling, and timetabling
• Product configuration and industrial decision support
• Bioinformatics, including metabolic network analysis and phylogeny reconstruction
• Robotics task planning and commonsense reasoning about actions
• Diagnosis and repair for systems with incomplete information
• Knowledge representation, semantic web reasoning, and database query answering