[Back]

J. Puehrer, H. Tompits, S. Woltran:
"Elimination of Disjunction and Negation in Answer-Set Programs under Hyperequivalence";
Talk: International Conference on Logic Programming (ICLP), Udine, Italien; 12-09-2008 - 12-13-2008; in: "Proceedings of the 24th Conference on Logic Programming (ICLP'08)", M. de la Banda, E. Pontelli (ed.); Springer LNCS, 5366 (2008), ISSN: 0302-9743; 561 - 575.

The study of different notions of equivalence is one of the cornerstones of current research in answer-set programming. This is mainly motivated by the needs of program simplification and modular programming, for which ordinary equivalence is insufficient. A recently introduced equivalence notion in this context is hyperequivalence, which includes as special cases strong, uniform, and ordinary equivalence. We study in this paper the question of replacing programs by syntactically simpler ones preserving hyperequivalence (we refer to such a replacement as a casting). In particular, we provide necessary and sufficient semantic conditions under which the elimination of disjunction, negation, or both, in programs is possible, preserving hyperequivalence. In other words, we characterise in model-theoretic terms when a disjunctive logic program can be replaced by a hyperequivalent normal, positive, or Horn program, respectively. Furthermore, we study the computational complexity of the considered tasks and, based on similar results for strong equivalence developed in previous work, we provide methods for constructing the respective hyperequivalent programs. Our results contribute to the understanding of problem settings in logic programming in the sense that they show in which scenarios the usage of certain constructs are superfluous or not.

answer set programming, equivalence, logic programming, hyperequivalence, disjunction, negation

http://dx.doi.org/10.1007/978-3-540-89982-2

http://publik.tuwien.ac.at/files/PubDat_169733.pdf

Project Head Hans Tompits:
Formale Methoden zur Optimierung Nichtmonotoner Logikprogramme