ApproxASP – a Scalable Approximate Answer Set Counter

Answer Set Programming (ASP) is a framework in artificial intelligence and knowledge representation for declarative modeling and problem solving. Modern ASP solvers focus on the computation or enumeration of answer sets. However, a variety of probabilistic applications in reasoning or logic programming require counting answer sets. While counting can be done by enumeration, simple enumeration becomes immediately infeasible if the number of solutions is high. On the other hand, approaches to exact counting are of high worst-case complexity. In fact, in propositional model counting, exact counting becomes impractical. In this work, we present a scalable approach to approximate counting for ASP. Our approach is based on systematically adding parity (XOR) constraints to ASP programs, which divide the search space. We prove that adding random XOR constraints partitions the answer sets of an ASP program. In practice, we use a Gaussian eliminationbased approach by lifting ideas from SAT to ASP and integrate it into a state of the art ASP solver, which we call ApproxASP. Finally, our experimental evaluation shows the scalability of our approach over existing ASP systems.

Authors

• Mohimenul Kabir National University of Singapore
• Flavio O Everardo
• Ankit K Shukla
• Markus Hecher Massachusetts Institute of Technology Univ. Artois, CNRS, UMR 8188, Centre de Recherche en Informatique de Lens (CRIL)
• Johannes Klaus Fichte
• Kuldeep S Meel

Keywords

No keywords are indexed for this paper.