It is based on the stable model (answer set) semantics of logic programming.
The computational process employed in the design of many answer set solvers is an enhancement of the DPLL algorithm and, in principle, it always terminates (unlike Prolog query evaluation, which may lead to an infinite loop).
In a more general sense, ASP includes all applications of answer sets to knowledge representation and reasoning[1][2] and the use of Prolog-style query evaluation for solving problems arising in these applications.
An early example of answer set programming was the planning method proposed in 1997 by Dimopoulos, Nebel and Köhler.
[5] In 1998 Soininen and Niemelä[6] applied what is now known as answer set programming to the problem of product configuration.
[4] The first of these papers identified the use of answer set solvers for search as a new programming paradigm.
[7] That same year Niemelä also proposed "logic programs with stable model semantics" as a new paradigm.
[8] Lparse is the name of the program that was originally created as a grounding tool (front-end) for the answer set solver smodels.
The language that Lparse accepts is now commonly called AnsProlog,[9] short for Answer Set Programming in Logic.
[10] It is now used in the same way in many other answer set solvers, including assat, clasp, cmodels, gNt, nomore++ and pbmodels.
The definition of a stable model was generalized to programs with choice rules.
[11] Choice rules can be treated also as abbreviations for propositional formulas under the stable model semantics.
The meaning of this rule under the stable model semantics is represented by the propositional formula Cardinality bounds can be used in the body of a rule as well, for instance: Adding this constraint to an Lparse program eliminates the stable models that contain at least 2 of the atoms
A range is a notational shortcut that is mainly used to define numerical domains in a compatible way.
For example, is a shorthand for To find a stable model of the Lparse program stored in file ${filename} we use the command Option 0 instructs smodels to find all stable models of the program.
For instance, if file test contains the rules then the command produces the output An
This can be accomplished using the following Lparse program: Line 1 defines the numbers
However, the search process employed by smodels and other answer set solvers is not based on trial and error.
A clique in a graph is a set of pairwise adjacent vertices.
The following Lparse program can be used to find a Hamiltonian cycle in a given directed graph if it exists; we assume that 0 is one of the vertices.
The choice rule in Line 1 "generates" all subsets of the set of edges.
This program is an example of the more general "generate, define and test" organization: it includes the definition of an auxiliary predicate that helps us eliminate all "bad" potential solutions.
In natural language processing, dependency-based parsing can be formulated as an ASP problem.
[13] The following code parses the Latin sentence "Puella pulchra in villa linguam latinam discit", "the pretty girl is learning Latin in the villa".
The syntax tree is expressed by the arc predicates which represent the dependencies between the words of the sentence.
More recent systems, such as Clasp, use a hybrid approach, using conflict-driven algorithms inspired by SAT, without fully converting into a Boolean-logic form.
These approaches allow for significant improvements of performance, often by an order of magnitude, over earlier backtracking algorithms.
The Potassco project acts as an umbrella for many of the systems below, including clasp, grounding systems (gringo), incremental systems (iclingo), constraint solvers (clingcon), action language to ASP compilers (coala), distributed Message Passing Interface implementations (claspar), and many others.
[15] Query-driven implementations of answer set programming, such as the Galliwasp system[16] and s(CASP)[17] avoid grounding altogether by using a combination of resolution and coinduction.