Answer set programming |
Answer set programming is a form of declarative programming that is similar in syntax to 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.
=Syntax=
An answer set program is composed of a set of rules, each rules being composed of an head and a tail:
head leftarrow body
Both the head and the tail 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 eg) and negation-as-failure (denoted by not). 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~ eg c leftarrow not~d, eg e
eg c leftarrow not~ eg e, a
According to the first rule, a is true whenever b is true and c can be assumed false without producing an inconsistency.
=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:
If the program contains some literals that are negated using negation-as-failure, the semantics requires the additional concept of reduct:
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 non-deterministic 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.
=Comparison, Complexity, and Implementations=
Contrarily 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_(complexity) 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.
Three systems implementing answer set programming are smodels and dlv, and cmodels.
=See Also=
=References=
=External Links=
|
|