[Zurück]

T. Eiter, W. Faber, M. Fink, G. Pfeifer, S. Woltran:
"Complexity of Answer Set Checking and Bounded Predicate Arities for Non-ground Answer Set Programming";
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. 69 - 83.

We present new complexity results on answer set checking for
non-ground programs under a variety of syntactic restrictions. For
several of these problems, the kind of representation of the answer
set to be checked is important. In particular, we consider set-based
and bitmap-based representations, which are popular in implementations
of Answer Set Programming systems. Furthermore, we present new complexity results for various reasoning tasks under the assumption that predicate arities are bounded by some constant.
These results imply that in such a setting -- which appears to be a
reasonable assumption in practice -- more efficient implementations than those currently available may be feasible.

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

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