Advanced BackJumping Techniques for Rule Instantiations
Simona Perri, Francesco Scarcello · 2003
The interest in the area of non-monotonic reasoning and declarative logic programming is growing rapidly after the recent development of a number of Answer Set Programming (ASP) systems. The logic-based languages supported by such systems are rich enough to represent in a natural and declarative way a large number of problems from di#erent domains. Nevertheless, the computation of the answer sets is always performed by these systems 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 any program P , a good instantiation for it is a ground program P # having the same answer sets as P and such that: P # can be computed e#ciently from P , and P # does not contain useless rules and thus can be evaluated e#ciently.