| Answer Set Programming |
Article Index for Answer |
Website Links For Answer |
Information AboutAnswer Set Programming |
| CATEGORIES ABOUT ANSWER SET PROGRAMMING | |
| logic programming | |
|
SYNTAX An answer set program is composed of a set of rules, each rules being composed of an head and a tail: 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 ) and negation-as-failure (denoted by ). A literal is either an atom or a negated (using classical negation) atom. The following is an example program: According to the first rule, is true whenever is true and 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 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. Three systems implementing answer set programming are smodels, dlv, and cmodels. SEE ALSO REFERENCES
EXTERNAL LINKS |
|
|