Answer Set Programming

Origin. Emerged from logic programming semantics: stable model semantics (Gelfond & Lifschitz, 1988) and well-founded semantics. Answer Set Programming (ASP) as a paradigm crystallized in the 1990s-2000s. Non-monotonic, supports negation as failure, defaults, and constraints. Implemented in efficient solvers: Clingo, DLV, WASP.

Models. Declarative problem solving through stable models. Write rules describing when conclusions hold; the solver finds models (answer sets) satisfying all rules. "Guess and check" problems: generate candidates, filter by constraints. Natural for combinatorial search, planning, diagnosis.

Formalism.

Logic program: Set of rules of the form:

head :- body.

head: atom or disjunction of atoms
body: literals (atoms or their negations)

Rule types:

Fact: a. (always true)
Rule: a :- b, c, not d. (a holds if b, c hold and d doesn't)
Constraint: :- b, c. (b and c can't both hold)
Choice: {a; b; c} :- body. (choose subset)
Disjunction: a | b :- body. (at least one holds)

Negation as failure (NAF): not a means "a is not derivable" — closed-world assumption. Different from classical negation (-a).

Stable model / Answer set: A model M is stable for program P if:

M satisfies all rules
M is minimal: no proper subset satisfies the "reduct" P^M

Reduct P^M: for each rule, if NAF literals are false in M, keep the rule without NAF; otherwise delete the rule.

Example — Graph coloring:

% Generate: each node gets a color
1 { color(X,C) : col(C) } 1 :- node(X).

% Test: adjacent nodes differ
:- edge(X,Y), color(X,C), color(Y,C).

Aggregates:

:- #count{X : selected(X)} > K.

Optimization:

#minimize { W,X : cost(X,W), selected(X) }.

Symbols.

Symbol	Unicode	Name	Meaning
:-	—	If	Rule arrow (reversed)
,	—	And	Conjunction in body
;	—	Or	Disjunction
\|	—	Choice/disj	Disjunctive head
not	—	NAF	Negation as failure
-	—	Strong negation	Classical negation
{ }	—	Choice	Choose subset
#count	—	Aggregate	Cardinality
#sum	—	Aggregate	Sum
#minimize	—	Optimization	Find minimum

Metatheory. Deciding whether a program has an answer set is NP-complete for normal programs, Σ₂ᵖ-complete for disjunctive programs. Finding answer sets is NP-hard (search). Solvers use SAT/CDCL techniques with propagation specific to ASP. Relationships: ASP with constraints = propositional logic; ASP with NAF = autoepistemic logic / default logic fragments.

Applies to. Combinatorial optimization. Planning and scheduling. Configuration. Diagnosis and abduction. Bioinformatics (phylogeny, haplotyping). Knowledge representation. Product configuration. Solving NP-hard problems declaratively.

Limitations. Grounding blowup: programs are grounded (variables replaced by constants) before solving; large domains explode. Function symbols limited (termination issues). Learning ASP idioms takes practice. Not all problems fit the "model finding" paradigm naturally. Performance depends heavily on encoding.