Answer set programming (ASP) is a form of declarative programming oriented towards difficult (primarily NP-hard) search problems. It is based on the stable model (answer set) semantics of logic programming. In ASP, search problems are reduced to computing stable models, and answer set solvers—programs for generating stable models—are used to perform search. 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 and the use of Prolog-style query evaluation for solving problems arising in these applications.
{p,q,r}.
says: choose arbitrarily which of the atoms (p∨¬p)∧(q∨¬q)∧(r∨¬r).
The language of Lparse allows us also to write "constrained" choice rules, such as
(p∨¬p)∧(q∨¬q)∧(r∨¬r)
- p,q,r. The meaning of this rule can be represented by the propositional formula
- p(a). p(b). p(c).
q(b). q(c).
The program
(start..end)
where start and end are constant-valued arithmetic expressions. A range is a notational shortcut that is mainly used to define numerical domains in a compatible way. For example, the fact
p(X):q(X)
If the extension of q is {q(a1), q(a2), ..., q(aN)}, the above condition is semantically equivalent to writing {p(a1), p(a2), ..., p(aN)} in the place of the condition. For example,
% lparse${filename}|smodels
Option 0 instructs smodels to find all stable models of the program. For instance, if file test contains the rules
n-
coloring of a
graph color(x)≠color(y) for every pair of adjacent vertices
c(1..n).
1 {color(X,I) : c(I)} 1 :- v(X).
:- color(X,I), color(Y,I), e(X,Y), c(I).
Line 1 defines the numbers x. The constraint in Line 3 prohibits assigning the same color to vertices G, such as
color(…,…) in the output of smodels will represent an ≥n in a given directed graph, or determines that it does not exist:
{in(X,Y)} :- e(X,Y).
:- 2 {in(X,Y) : e(X,Y)}, v(X).
:- 2 {in(X,Y) : e(X,Y)}, v(Y).
r(X) :- in(0,X), v(X).
r(Y) :- r(X), in(X,Y), e(X,Y).
:- not r(X), v(X).
The choice rule in Line 1 "generates" all subsets of the set of edges. The three constraints "weed out" the subsets that are not Hamiltonian cycles. The last of them uses the auxiliary predicate Yes
|
|
|
Clasp Answer Set Solver |
Linux, macOS, Windows |
MIT License |
No |
Cmodels |
Linux, Solaris |
GPL |
diff-SAT |
Linux, macOS, Windows (Java virtual machine) |
MIT License |
DLV |
Linux, macOS, Windows |
free for academic and non-commercial educational use, and for non-profit organizations |
No |
DLV-Complex |
Linux, macOS, Windows |
GPL |
|
Yes |
Requires grounding |
|
|
|
Platypus |
Linux, Solaris, Windows |
GPL |
|
|
|
|
|
distributed, multi-threaded nomore++, smodels |
| style=\"background-color: var(--background-color-neutral,#eaecf0);color: var(--color-base,#202122);font-weight: bold; vertical-align: middle; text-align: left; \" class=\"table-rh\"</span>"},{"html":""}]]}'>Pbmodels |
Linux |
? |
|
|
|
|
|
pseudo-boolean solver based |
| style=\"background-color: var(--background-color-neutral,#eaecf0);color: var(--color-base,#202122);font-weight: bold; vertical-align: middle; text-align: left; \" class=\"table-rh\"</span>"},{"html":""}]]}'>Smodels |
Linux, macOS, Windows |
GPL |
No |
Smodels-cc Archived 2015-11-15 at the Wayback Machine |
Linux |
? |
- ↑ Baral, Chitta (2003). Knowledge Representation, Reasoning and Declarative Problem Solving. Cambridge University Press. ISBN 978-0-521-81802-5.
- ↑ Soininen, T.; Niemelä, I. (1998), Formalizing configuration knowledge using rules with choices (Postscript), Laboratory of Information Processing Science, Helsinki University of Technology
- ↑
Crick, Tom (2009). Superoptimisation: Provably Optimal Code Generation using Answer Set Programming (PDF) (Ph.D.). University of Bath. Docket 20352. Archived from the original (PDF) on 2016-03-04. Retrieved 2011-05-27.
- ↑ "ASP-Core-2 Input Language Specification" (PDF). Retrieved 14 May 2018.
- ↑ Arias, J.; Carro, M.; Salazar, E.; Marple, K.; Gupta, G. (2018). "Constraint Answer Set Programming without Grounding". Theory and Practice of Logic Programming. 18 (3–4): 337–354. arXiv:1804.11162. doi:10.1017/S1471068418000285. S2CID 13754645.
- 1 2
|