[Back]

T. Eiter, M. Fink, H. Tompits, S. Woltran:
"Simplifying Logic Programs under Uniform and Strong Equivalence";
Talk: International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR), Fort Lauderdale, FL, USA; 2004-01-06 - 2004-01-08; in: "Proceedings of the 7th International Conference on Logic Programming and Nonmonotonic Reasoning", V. Lifschitz, I. Niemelä (ed.); Springer, LNAI 2923 (2004), ISBN: 3-540-20721-x; 87 - 99.

We consider the simplification of logic programs under the stable-model semantics, with respect to the notions of strong and uniform equivalence between logic programs, respectively. Both notions have recently been considered for nonmonotonic logic programs (the latter dates back to the 1980s, though) and provide semantic foundations for optimizing programs with input. Extending previous work, we investigate syntactic and semantic rules for program transformation, based on proper notions of consequence. We furthermore provide encodings of these notions in answer-set programming, and give characterizations of programs which are semantically equivalent to positive and Horn programs, respectively. Finally, we investigate the complexity of program simplification and determining semantical equivalence, showing that the problems range between coNP and $\Pi^P_2$ complexity, and we present some tractable cases.
This work was partially supported by the Austrian Science Fund (FWF) under project Z29-N04, and the European Commission under projects FET-2001-37004 WASP and IST-2001-33570 INFOMIX.

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

http://www.springerlink.com/app/home/content.asp?wasp=3n25ykxhxr1vwr6lwvtp&referrer=contribution&format=2&page=1&pagecount=13