[Back]

F. Everardo, M. Hecher, A. Shukla:
"Extending XORRO with Approximate Model Counting";
Talk: Workshop ASPOCP 2020, University of Calabria, Rende, Italy; 2020-09-18.

Answer Set Programming (ASP) is a declarative framework that is
well-suited for problems in KR, AI, and other areas as well as plenty of practical applications, in both academia and industry. While modern ASP solvers not only compute one solution (answer set), but actually support different reasoning modes, the problem of counting answer sets has not been subject to intense studies yet.
This is in contrast to the neighboring area of propositional satisfiability (SAT), where several applications and problems related to quantitative reasoning trace back to model counting. However, due to high computational complexity and depending on the actual application, approximate counting might be sufficient.
Indeed, there are plenty of applications, where approximate counting for SAT is well-suited. This work deals with establishing approximate model counting for ASP, thereby lifting ideas from SAT to ASP. We present the first approximate counter for ASP by extending the clingo-based system xorro and also show preliminary experiments for several problems.

Approximate Counting, Answer Set Solving, Answer Set Programming, Counting Problems, Model Counting, Parity Constraints, xorro

Project Head Stefan Woltran:
HYPAR

Project Head Stefan Woltran:
START