Donald Bren School of Information and Computer Sciences
Propositional semantics for disjunctive logic programs
- Author(s): Ben-Eliyahu, Rachel
- Dechter, Rina
- et al.
In this paper we study the properties of the class of head-cycle-free extended disjunctive logic programs (HEDLPs), which includes, as a special case, all nondisjunctive extended logic programs. We show that any propositional HEDLP can be mapped in polynomial time into a prepositional theory such that each model of the latter corresponds to an answer set, as defined by stable model semantics, of the former. Using this mapping, we show that many queries over HEDLPs can be determined by solving propositional satisfiability problems.