BackJumping Techniques for Rules Instantiation in the DLV System
Nicola Leone, Simona Perri, Francesco Scarcello · 2004
The computation of the answer sets in Answer Set Programming (ASP) ASP systems is performed on simple ground (i.e., variable free) programs, first computed by a pre-processing phase, called instantiation. This phase may be computationally expensive, and in fact it has been recognized to be a key issue for solving real-world problems by using Answer Set Programming. Given a program P, a good instantiation for P is a ground program P ′ having precisely the same answer sets as P and such that: (i) P ′ can be computed efficiently from P, and (ii) P ′ does not contain “useless ” rules, (P ′ is as small as possible) and can be thus evaluated efficiently. In this paper, we present a structure-based backjumping algorithm for the instantiation of logic programs, that meets the above requirements. In particular, given a rule r to be grounded, our algorithm exploits both the semantical and the structural information about r for computing efficiently the ground instances of r, avoiding the generation of “useless ” rules. That is, from each general rule r, we are able to compute only a relevant subset of all its possible ground instances. We have implemented this algorithm in the ASP system DLV, and we have carried out an experimentation activity on a collection of benchmark problems. The results are very positive, as the new technique improves sensibly the efficiency of the DLV system on many kind of programs.