Optimizing answer set computation via heuristic-based decomposition

Answer Set Programming (ASP) is a purely declarative formalism developed in the field of logic programming and nonmonotonic reasoning. With ASP, computational problems are encoded by logic programs whose answer sets, corresponding to solutions, are computed by an ASP system. In general, several semantically equivalent programs might be defined for the same problem; however, performance of ASP systems while evaluating them might significantly vary. We propose an approach for automatically transforming an input logic program into an equivalent one that can be evaluated more efficiently. To this aim, one can make use of existing tree-decomposition techniques for rewriting selected rules into a set of multiple ones. The idea is to guide and adaptively apply them on the basis of proper new heuristics, in order to obtain a smart rewriting algorithm to be integrated into an ASP system. The method is rather general: it can be adapted to the system at hand and implement different preference policies. Furthermore, we define a set of new heuristics explicitly tailored at optimizing one of the main phases of the typical ASP computation, namely the grounding process; we make use of them in order to actually implement the approach into the ASP system DLV, and in particular into its grounding subsystem I-DLV, and carry out an extensive experimental activity aimed at assessing the impact of the proposal.