Answer set programming

From Wikipedia, the free encyclopedia

Answer set programming is a form of declarative programming that is similar in syntax to traditional logic programming and close in semantics to non-monotonic logic. The main difference between traditional logic programming and answer set programming is how negation as failure is interpreted. In traditional logic programming, negation-as-failure indicates the failure of a derivation; in answer set programming, it indicates the consistency of a literal.

1 Syntax
2 Semantics
3 Comparison, Complexity, and Implementations
4 See also
5 References
6 External links

[edit] Syntax

An answer set program is composed of a set of rules, each rules being composed of an $h e a d$ and a $b o d y$ :

$head \leftarrow body$

Both the head and the body of a rule are sets of literals, each literal being a possibly negated atom. Contrarily to traditional logic programs, atoms are propositional rather than first-order, and they can be negated using two forms of negation: classical negation (denoted by $\neg$ ) and negation-as-failure (denoted by $n o t$ ). A literal is either an atom or a negated (using classical negation) atom. The following is an example program:

$a \leftarrow b, not~c$
$a, not~\neg c \leftarrow not~d, \neg e$
$\neg c \leftarrow not~\neg e, a$

According to the first rule, $a$ is true whenever $b$ is true and $c$ can be assumed false without producing an inconsistency.

[edit] Semantics

The semantic of a program is based on its answer sets, each answer set being a set of literals. For programs not containing negation-as-failure, the semantic of a program is based on the concepts of closure and minimality:

A program is closed under a set L of literals if the set contains at least a literal in the head of a rule whenever it contains all literals in L in its body.
A set of literals is an answer set of a program if it is minimal (under set containment) among the ones the program is closed for.

If the program contains some literals that are negated using negation-as-failure, the semantics requires the additional concept of reduct:

The reduct of a program under a set of literals is the program obtained by performing the following changes to each rule:
1. remove all literals of the head that are negated using negation-as-failure and are in the set;
2. remove all literals of the tail that are negated using negation-as-failure and are not in the set;
3. remove the whole rule if it still contains negated (using negation-as-failure) atoms after the application of the two rules above.

A set of literals is an answer set of a program if it is an answer set of the reduct of the program under the set itself. In other words, an answer set can be computed by running the following nondeterministic algorithm:

 choose a set of literals L;
 compute the reduct PL of program P under L;
 if L is a minimal set of literals PL is closed for
   output L

The choice of the initial set of literals L is non-deterministic. The algorithm decides whether L is an answer set by first computing the reduct of the program under L, and then checking whether L is an answer set of this negation-as-failure-free program.

An answer set program can have zero, one, or many answer sets. A program entails a literal if all its answer sets contain that literal.

[edit] Comparison, Complexity, and Implementations

In contrast to Prolog, the semantics of answer set programs do not depend on a specific order of evaluation of the rules and of the atoms within each rule.

The complexity of checking the existence of an answer set for a program and the complexity of checking whether a program entails a literal range from P to the second level of the polynomial hierarchy depending on a set of conditions (e.g., stratification, disjunction in the head) a program may or may not satisfy.

Four systems implementing answer set programming are smodels, dlv, assat and cmodels.

[edit] See also

[edit] References

T. Eiter, N. Leone, C. Mateis, G. Pfeifer, F. Scarcello (1998). The KR System dlv: Progress Report, Comparisons and Benchmarks. In Proceedings of the Sixth International Conference on Principles of Knowledge Representation and Reasoning (KR'98): 406-417
V. Lifschitz (2002). Answer set programming and plan generation. Artificial Intelligence. 138(1-2): 39-54. DOI:10.1016/S0004-3702(02)00186-8
I. Niemela, P. Simons, T. Syrjanen (2000). Smodels: A System for Answer Set Programming. CoRR cs.AI/0003033