Pruning Operators for Answer Set Programming Systems

Answer Set Programming (ASP) is a novel paradigm in Logic Programming, which allows for solving problems in a simple and highly declarative way. The language of ASP (function-free disjunctive logic programming) is very expressive and supports the representation of problems of high computational complexity (specifically, all problems in the complexity class $\SigmaP{2} = \NP^{\NP}$). Importantly, the ASP encoding of a large variety of problems is often very concise, simple, and elegant. In this paper, we explain the computational process performed by ASP systems, with a focus on search space pruning, which is crucial for efficiency. We analyze the properties of two main pruning operators, namely (Fitting's operator and Well-founded operator), discuss their peculiarities and differences with respect to efficiency and effectiveness. We design an intelligent strategy for combining the two operators, which exploits the advantages of both. We implement our approach in the ASP system dlv, and perform some experiments. The experiments show interesting results, and evidence how the choice of the pruning operator affects the performance of ASP systems.