Replacements in Non-Ground Answer-Set Programming.
Thomas Eiter, Michael Fink, Hans Tompits, Patrick Traxler, Stefan Woltran · 2006
Abstract. In this paper, we propose a formal framework for specifying rule replacements in non-monotonic logic programs within the answer-set programming paradigm. Of particular interest are replacement schemas retaining specic notions of equivalence, among them the prominent notions of strong and uniform equivalence, which have been introduced as theoretical tools for program optimiza-tion and verication. We derive some general properties of the replacement framework with respect to these notions of equivalence. Moreover, we generalize results about particular replacement schemas which have been established for ground programs to the non-ground case. Finally, we report a number of complexity results which address the problem of deciding how hard it is to apply a replacement to a given program. Our results provide an important step towards the development of effective optimiza-tion methods for non-ground answer-set programming, an issue which has not been addressed much so far. 1