[Back]

T. Eiter, M. Hecher, R. Kiesel:
"aspmc: An Algebraic Answer Set Counter.";
Talk: 37th International Conference on Logic Programming (ICLP 2021), Porto, Portugal; 2020-09-20 - 2020-09-21; in: "Proceedings of the International Conference on Logic Programming 2021 Workshops co-located with the 37th International Conference on Logic Programming (ICLP 2021), Porto, Portugal (virtual), September 20th-21st, 2021", (2021).

We report about aspmc, which is the working prototype implementation of recent advances in Algebraic Answer Set Counting (AASC). AASC refers to counting the answer sets of a normal answer set program with weights over a semiring. This includes many problems that have recently received growing attention, among them probabilistic reasoning, parameter learning, and most probable explanation inference for answer set programs. aspmc employs a treewidth-aware cycle-breaking to reduce AASC to Algebraic Model Counting (AMC) over a propositional formula with only a slightly increased treewidth. This allows us to lift the performance bounds for AMC in terms of treewidth to AASC. The experimental evaluation of aspmc reveals that these bounds are not only of theoretical interest but also allow us to improve upon the efficiency of other exact counters on standard benchmarks.

Wir berichten über aspmc, den funktionierenden Prototyp, der die jüngsten Fortschritte in der algebraischen Answer Set Counting (AASC) ist. AASC bezieht sich auf das Zählen der Antwortmengen eines normalen Antwortmengenprogramms mit Gewichten über einem Semiring. Dazu gehören viele Probleme, die in letzter Zeit immer mehr Aufmerksamkeit erhalten haben, darunter probabilistisches Schlussfolgern, Parameterlernen und Inferenz der wahrscheinlichsten Erklärung für Antwortmengenprogramme. Antwortmengenprogramme. aspmc verwendet ein baumbreitenbewusstes Cycle-Breaking, um AASC auf Algebraic Model Counting (AMC) über eine propositionale Formel mit nur leicht erhöhter Baumbreite. Dies ermöglicht können wir die Leistungsgrenzen für AMC in Bezug auf die Baumbreite auf AASC anheben. Die experimentelle Auswertung von aspmc zeigt, dass diese Schranken nicht nur von theoretischem Interesse sind, sondern es uns auch ermöglichen, die Effizienz anderer exakter Zähler bei Standard-Benchmarks zu verbessern.

ASP, Model Counting, Treewidth, Semiring

https://publik.tuwien.ac.at/files/publik_302167.pdf

Project Head Stefan Szeider:
DK - Logic

Project Head Stefan Woltran:
HYPAR

Project Head Stefan Woltran:
START