Name
Abstract | ||
|---|---|---|
This paper introduces nondeterminism into logic programs with negation by associating functional dependencies with some predicates, and develops the well-founded choice semantics. Each program has at least one well-founded choice model. The well-founded choice semantics extends the well-founded semantics with nondeterminism, while maintaining the robustness and polynomial time data complexity of the well-founded semantics. It generalizes the stable model semantics of Datalog with choice to logic programs with negation, and yet avoids the problem of NP-completeness of the existence of stable models in general. Although model-theoretic in nature, the well-founded choice semantics expresses precisely nondeterministic polynomial-time queries (NDB-PTIME). We present a nondeterministic fixpoint semantics that is sound and complete with respect to the well-founded choice semantics. |
Year | DOI | Venue |
|---|---|---|
1996 | 10.1016/0743-1066(95)00091-7 | The Journal of Logic Programming |
DocType | Volume | Issue |
Journal | 26 | 3 |
ISSN | Citations | PageRank |
0743-1066 | 1 | 0.45 |
References | Authors | |
3 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Weidong Chen | 1 | 11 | 2.57 |
| Jinghong Zeng | 2 | 1 | 0.45 |