NONDETERMINISM THROUGH WELL-FOUNDED CHOICE

This paper introduces nondeterminism into logic programs with negation by associating functional dependencies with some predicates, and deve lops the well-founded choice semantics. Each program has at least one well-founded choice model. The well-founded choice semantics extends t he well-founded semantics with nondeterminism, while maintaining the r obustness and polynomial time data complexity of the well-founded sema ntics. It generalizes the stable model semantics of Datalog with choic e to logic programs with negation, and yet avoids the problem of NP-co mpleteness of the existence of stable models in general. Although mode l-theoretic in nature, the well-founded choice semantics expresses pre cisely nondeterministic polynomial-time queries (NDB-PTIME). We presen t a nondeterministic fixpoint semantics that is sound and complete wit h respect to the well-founded choice semantics.