Content deleted Content added
m Open access bot: url-access=subscription updated in citation with #oabot. |
Link suggestions feature: 3 links added. |
||
Line 153:
If we think of the stable model semantics as a description of the behavior of [[Prolog]] in the presence of negation then programs without a unique stable model can be judged unsatisfactory: they do not provide an unambiguous specification for Prolog-style query answering. For instance, the two programs above are not reasonable as Prolog programs—SLDNF resolution does not terminate on them.
But the use of stable models in [[answer set programming]] provides a different perspective on such programs. In that [[programming paradigm]], a given search problem is represented by a logic program so that the stable models of the program correspond to solutions. Then programs with many stable models correspond to problems with many solutions, and programs without stable models correspond to unsolvable problems. For instance, the [[eight queens puzzle]] has 92 solutions; to solve it using answer set programming, we encode it by a logic program with 92 stable models. From this point of view, logic programs with exactly one stable model are rather special in answer set programming, like polynomials with exactly one root in algebra.
==Properties of the stable model semantics==
Line 269:
:<math>A \leftarrow B_{1},\dots,B_{m},\operatorname{not} C_{1},\dots,\operatorname{not} C_{n}</math>
where <math>A,B_{1},\dots,B_{m},C_{1},\dots,C_{n}</math> are atoms. One [[simple extension]] allows programs to contain ''constraints''—rules with the empty head:
:<math>\leftarrow B_{1},\dots,B_{m},\operatorname{not}C_{1},\dots,\operatorname{not} C_{n}.</math>
Line 343:
has two stable models, <math>\empty</math> and <math>\{p\}</math>. The latter is not minimal, and it is a proper superset of the former.
Testing whether a [[finite set]] of propositional formulas has a stable model is [[Polynomial hierarchy|<math>\Sigma_2^{\rm P}</math>-complete]], as in the case of [[#Disjunctive programs|disjunctive programs]].
== See also ==
| |||