[Back]

M. Morak, S. Woltran:
"Preprocessing of Complex Non-Ground Rules in Answer Set Programming";
Report No. DBAI-TR-2011-72, 2011; 14 pages.

In this paper we present a novel method for preprocessing complex non-ground rules for answer set programming (ASP) in such a way that the grounding of such a rule remains small. A single non-ground rule in a logic program is therefore seen as a hypergraph. ASP is a language well known for its clarity and readability, however rules that are easy to read often contain many variables, in which case grounders often generate an unnecessary large grounding. Using a well-known result from the area of conjunctive query evaluation,
hypertree decompositions of such rules can be used for preprocessing in such a way that the grounder is made aware of the structure of the rule, resulting in a better grounding. We propose a preprocessing algorithm that makes use of such hypertree decompositions. Using a prototype implementation and the benchmark suites of the Answer Set Programming Competition 2011, we perform extensive tests of our algorithm that clearly show the improvements in grounding time and size.