[Zurück]

T. Eiter, M. Fink, H. Tompits, S. Woltran:
"Eliminating Disjunction from Propositional Logic Programs under Stable Model Preservation";
Vortrag: 2nd Intl. Answer Set Programming Workshop, Messina, Italy; 26.09.2003 - 28.09.2003; in: "Answer Set Programming - Advances in Theory and Implementation", M. De Vos, A. Provetti (Hrg.); CEUR-WS, 78 (2003), ISSN: 1613-0073; S. 151 - 165.

In general, disjunction is considered to add
expressive power to propositional logic programs under stable model
semantics, and to enlarge the range of problems which can be
expressed. However, from a semantical point of view, disjunction is
often not really needed, in that an equivalent program without disjunction can b
e given. We thus consider
the question, given a disjunctive logic program P, does
there exist an equivalent normal (i.e., disjunction-free) logic program P'? In fact, we consider this issue for different notions of equivalence, namely for
ordinary equivalence (regarding the collections of all stable models of the prog
rams) as
well as for the more restrictive notions of strong and uniform equivalence.
We resolve the issue for propositional programs, and present a simple,
appealing semantic criterion for the programs from which all
disjunctions can be eliminated under strong equivalence; testing this
criterion is co-NP-complete. We also show that under ordinary and
uniform equivalence, this elimination is
always possible. In all cases, there are constructive methods to
achieve this. Our results extend and complement recent results on
simplifying logic programs under different notions of
equivalence, and add to the foundations of improving implementations
of Answer Set Solvers.

http://aleph.ub.tuwien.ac.at/F?base=tuw01&func=find-c&ccl_term=AC04404477

http://sunsite.informatik.rwth-aachen.de/Publications/CEUR-WS//Vol-78/asp03-final-eiter-elim.pdf