Answer set programming

Answer Set Programming is a form of declarative programming that similar in syntax to logic programming and close in semantics to non-monotonic logic. Differently from 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 $not$). A literal is either an atom or a negated (using classical negation) atom. A rule is an expression of the form:

$head\leftarrow body$

where both $head$ and $body$ are sets of literals and negated (using negation-as-failure) literals. A program is a set of rules. The following is an example program:

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

The semantics of a programs is based on its answer sets, which are sets of literals. For programs not containing negation-as-failure, the semantics is defined as follows. A program is closed under a set of literals if the set contains at least a literal in the head of a rule whenever it contains all literals 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 is based on the reduct of a program under a set of literals, which is the set obtained by removing from the head of the rules the atoms that are negated using negation-as-failure and are in the set, removing from the tail of the rules the atoms that are negated using negation-as-failure and are not in the set, and removing all rules that still contain negated (using negation-as-failure) atoms according to this rule. A set of literals is an answer set of a program if it is an answer set of the reduct of the program under this set of literals.

Contrarily to Prolog, the semantics of answer set programs do not depend on an order of the literals and negated literals in a rule and on an order of the rules in a program.

Two system implementing answer set programming are smodels and dlv.

References

• T. Eiter, N. Leone, C. Mateis, G. Pfeifer, F. Scarcello: 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. Answer set programming and plan generation. Artificial Intelligence. 138(1-2): 39-54 (2002)

• I. Niemela, P, Simons, T, Syrjanen. [Smodels: A System for Answer Set Programming]

CoRR cs.AI/0003033

External Link

[Working group on Answer Set Programming]