Space Efficient Evaluation of ASP Programs with Bounded Predicate Arities

Answer Set Programming (ASP) has been deployed in many applications, thanks to the availability of efficient solvers. Most programs encountered in practice have an important property: Their predicate arities are bounded by a constant, and in this case it is known that the relevant computations can be done using polynomial space. However, all competitive ASP systems rely on grounding, due to which they may use exponential space for these programs. We present three evaluation methods that respect the polynomial space bound and a generic framework architecture for realization. Experimental results for a prototype implementation indicate that the methods are effective. They show not only benign space consumption, but interestingly also good runtime compared to some state of the art ASP solvers.

Eiter, T., Faber, W., Mushthofa, M. (2010) Space Efficient Evaluation of ASP Programs with Bounded Predicate Arities. AAAI-10 303-308.

VIB / UGent
Bioinformatics & Evolutionary Genomics
Technologiepark 927
B-9052 Gent
+32 (0) 9 33 13807 (phone)
+32 (0) 9 33 13809 (fax)

Don't hesitate to contact the in case of problems with the website!

You are visiting an outdated page of the BEG/Van de Peer Lab site.

Not all pages have been ported, so these archived pages are still available.

Redirect to the new website?