[Back]

F. Everardo, M. Hecher, A. Shukla:
"An Approximate Model Counter for ASP";
Talk: NMR 2020 - 18th INTERNATIONAL WORKSHOP ON NON-MONOTONIC REASONING, Rhodes, Greece; 2020-09-12 - 2020-09-18; in: "18th INTERNATIONAL WORKSHOP ON NON-MONOTONIC REASONING", (2020), 208 - 216.

Answer Set Programming (ASP) is a declarative frameworkthat is well-suited for problems in KR, AI, and other areaswith plenty of practical applications, in both the academy andin the industry. While modern ASP solvers not only computeone solution (answer set) but support different (reasoning)problems, the problem of counting answer sets has not beensubject to intense studies. This is in contrast to the neighbor-ing area of propositional satisfiability (SAT), where severalapplications and problems related to quantitative reasoningtrace back to model counting. However, due to high compu-tational complexity and depending on the actual application,approximate counting might be sufficient. Indeed, there areplenty of applications, where approximate counting for SATis well-suited. This work deals with establishing approximatemodel counting for ASP, thereby lifting ideas from SAT toASP. We present the first approximate counter for ASP byextending theclingo-based systemxorroand also show pre-liminary experiments for several problems. While we do nothave specific guarantees in terms of accuracy, our preliminaryresults look promising.

Project Head Stefan Woltran:
START