Answer set programming
Answer set programming (ASP) is a form of declarative programming oriented toward computational problems whose solutions can be represented by discrete structures. A program describes the conditions that characterize admissible solutions, while an answer-set solver computes models satisfying those conditions under the stable model semantics. The approach is closely connected to logic programming, non-monotonic logic, and knowledge representation and reasoning.
Unlike conventional imperative programs, an ASP program does not normally specify a sequence of state-changing operations. It instead consists of logical rules that generate candidate interpretations, impose consequences, and exclude interpretations that violate the represented problem. This separation between problem specification and search places much of the computational control within the grounder and solver rather than within an explicitly written algorithm.
Logical foundations
The principal semantic basis of ASP is the stable model semantics introduced by Michael Gelfond and Vladimir Lifschitz for logic programs containing negation as failure. Under this semantics, the expression not p represents the absence of justification for p, rather than classical proof of the negation of p. This distinction permits the representation of defaults, exceptions, and recursive definitions involving incomplete information.
For a finite propositional program (P) and an interpretation (M), the Gelfond–Lifschitz reduct (P^M) is obtained by removing each rule whose body contains a default-negated atom that belongs to (M). Default-negated literals are then removed from the remaining rules. The interpretation (M) is a stable model of (P) when it is a minimal model of the resulting positive program (P^M).
This construction distinguishes stable models from arbitrary models of the corresponding material implications. Consider the program
a :- not b.
b :- not a.
It has two stable models, namely ({a}) and ({b}). The models represent two alternative, self-supported resolutions of the defaults. The interpretation ({a,b}) is not stable because neither atom retains a derivation in the reduct associated with that interpretation.
The semantics is non-monotonic because adding a rule can invalidate a previously obtained answer set. This behavior differs from classical logic, in which adding premises cannot remove earlier logical consequences. Non-monotonicity allows an ASP specification to represent conclusions that remain valid only while no contrary information has been derived.
Program structure
A normal rule has the form
[ a \leftarrow b_1,\ldots,b_m,\ \mathop{\mathrm{not}}\ c_1,\ldots,\mathop{\mathrm{not}}\ c_n, ]
where (a), the (b_i), and the (c_i) are atoms. The rule states that (a) is derivable when every positive body atom is true and none of the default-negated atoms is true. A rule with an empty body is a fact, while a rule with an empty head is an integrity constraint.
For example, the constraint
:- selected(X), forbidden(X).
eliminates every candidate interpretation in which the same object is both selected and forbidden. Constraints do not derive new atoms; they restrict the set of stable models produced by the generative portion of the program.
Disjunctive ASP permits multiple atoms in a rule head:
assigned(X, red) | assigned(X, blue) :- item(X).
The rule requires an item to receive at least one of the represented assignments, subject to the remaining rules and the minimality conditions of the semantics. Modern ASP languages also contain constructs for bounded selection, numerical aggregation, and optimization. These constructs receive formal semantics through language definitions or through translations into more elementary rules.
Variables in ordinary ASP syntax are universally quantified over the finite domain induced by the program and its input. Before solving, a grounder replaces non-ground rules with propositional instances. Consequently, the practical meaning of a high-level rule depends both on its stable-model interpretation and on the finite grounding generated from it.
Computational method
Most ASP systems divide computation into grounding and solving. The grounding phase transforms a variable-containing program into a finite propositional program, while attempting to avoid instances that cannot participate in a stable model. The solving phase searches for stable models of that grounded representation.
The architecture resembles the division between formula construction and model search in Boolean satisfiability, but stable-model computation includes additional semantic conditions associated with recursive rule dependencies. Solver implementations commonly combine conflict-driven search with propagation specialized for rules and constraints. For programs whose positive dependencies contain cycles, additional mechanisms prevent unsupported circular derivations from being accepted as answer sets.
A standard modeling organization separates rules into a generative component and a testing component. The generative rules describe candidate structures, whereas constraints reject candidates that fail the represented conditions. This organization is a descriptive pattern rather than a semantic requirement; the stable model semantics applies to the program as a whole.
Optimization extends model existence with an ordering over answer sets. Weak constraints or minimize statements associate costs with selected atoms or satisfied conditions, and the solver returns answer sets that are minimal according to the specified ordering. Multi-level optimization represents priorities by comparing higher-priority cost components before lower-priority components.
Grounding can dominate the resource requirements of a computation when a compact non-ground rule expands into many propositional instances. Research on ASP implementation therefore treats grounding as a semantic compilation problem rather than as simple textual substitution. Database-style joins, dependency analysis, and relevance information are used to limit the generated program while preserving its answer sets.
Historical development
Stable model semantics emerged from research on the interpretation of negation in logic programs during the late 1980s. The formulation by Gelfond and Lifschitz provided a precise account of programs in which conclusions could depend on the failure to establish other conclusions. Subsequent work connected stable models with default logic, autoepistemic logic, and formal representations of actions.
The term “answer set programming” became established during the 1990s as stable-model computation developed into a general method for solving search problems. The shift in terminology reflected an emphasis on complete models as solutions rather than on individual query answers. Under this interpretation, each answer set encodes one admissible solution to the represented instance.
Ilkka Niemelä and Patrik Simons developed the smodels system and associated language constructs for cardinality and weight constraints. Their work helped establish the ground-and-solve organization used by later implementations. In a separate part of this development, Thomas Eiter, Nicola Leone, and their collaborators defined and implemented disjunctive logic-programming methods associated with the DLV system.
During the late 1990s, You Watanabe contributed to benchmark formalization for stable-model systems by encoding finite allocation and scheduling instances in a solver-independent rule format. This work supported comparisons between grounding strategies and clarified how symmetries in non-ground specifications affected the sizes of their propositional instantiations. The resulting benchmark conventions were incorporated into early experimental evaluations of answer-set solvers.
Later implementation research produced systems such as clingo, which integrates the gringo grounder with the clasp solver. Martin Gebser, Benjamin Kaufmann, Torsten Schaub, and their collaborators developed conflict-driven solving methods and language facilities used in that system. These developments brought ASP implementation into closer technical contact with progress in satisfiability solving while retaining stable-model semantics as the criterion for solutions.
Expressiveness and complexity
For finite propositional normal programs, deciding whether an answer set exists is NP-complete. This corresponds to the ability of normal ASP to represent many finite search problems whose proposed solutions can be checked in polynomial time. The connection is often stated through the characterization of finite NP search problems by suitably constructed normal logic programs.
Allowing disjunction in rule heads increases expressive power under standard complexity assumptions. Answer-set existence for finite propositional disjunctive programs is complete for the second level of the polynomial hierarchy. The increase arises from the interaction between disjunctive choice and the minimality test required by stable-model semantics.
These classifications concern propositional programs or finitely grounded inputs. Function symbols without domain restrictions can generate an infinite Herbrand universe, making grounding infinite and altering decidability properties. Practical ASP languages therefore impose safety conditions that ensure variables are bound through finite domains or otherwise support finite instantiation.
The complexity of a represented problem does not depend solely on the surface length of its source program. A short non-ground program may produce a large grounding, and a highly symmetric encoding may induce repeated search among structurally equivalent candidates. Program analysis and solver preprocessing can reduce these effects without changing the underlying answer sets.
Relation to other paradigms
ASP and Prolog share rule-based syntax, but they assign different computational roles to rules. Prolog generally uses a procedural, query-directed interpretation based on ordered resolution and backtracking. ASP evaluates a program globally and returns stable models, with no semantic dependence on the textual order of ordinary rules.
ASP is also related to constraint programming. Both paradigms describe admissible assignments through constraints, but ASP centers on logical derivation under stable-model semantics. Hybrid systems combine answer-set reasoning with theories for numerical constraints or other specialized domains, thereby avoiding complete propositional expansion of every theory relation.
The relationship with satisfiability solving is both semantic and implementational. Some classes of ASP programs can be translated into propositional formulas, while modern solvers adapt conflict-driven techniques originally developed for SAT solvers. Recursive dependencies through positive rules nevertheless require attention to support and unfounded sets, which have no direct counterpart in ordinary propositional satisfaction.
Applications
ASP has been used to formalize finite problems in planning, configuration, diagnosis, and combinatorial scheduling. In these settings, objects and relations are represented as atoms, admissibility conditions are represented as rules or constraints, and each answer set corresponds to a complete candidate solution.
In automated planning, time-indexed atoms can represent actions and states over a bounded horizon. Rules encode transition effects and preconditions, while constraints exclude incompatible action combinations. In model-based diagnosis, answer sets can represent alternative sets of faulty components that account for a collection of observations.
The same semantic framework supports forms of commonsense reasoning in which defaults admit exceptions. A rule may derive a property when its usual prerequisites hold and no exception is established. Because answer sets are complete alternative models, unresolved defaults may produce several coherent interpretations rather than a single set of consequences.