Treewidth-Aware Cycle Breaking for Algebraic Answer Set Counting

Abstract

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.

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.