Quantitative extensions of logic programming often require the solution of so called second levelinference tasks, that is, problems that involve a third operation, such as maximization or normalization,on top of addition and multiplication, and thus go beyond the well-known weightedor algebraic model counting setting of probabilistic logic programming under the distribution semantics.We introduce Second Level Algebraic Model Counting (2AMC) as a generic frameworkfor these kinds of problems. As 2AMC is to (algebraic) model counting what forall-exists-SATis to propositional satisfiability, it is notoriously hard to solve. First level techniques based onKnowledge Compilation (KC) have been adapted for specific 2AMC instances by imposing variableorder constraints on the resulting circuit. However, those constraints can severely increasethe circuit size and thus decrease the efficiency of such approaches. We show that we can exploitthe logical structure of a 2AMC problem to omit parts of these constraints, thus limiting thenegative effect. Furthermore, we introduce and implement a strategy to generate a sufficientset of constraints statically, with a priori guarantees for the performance of KC. Our empiricalevaluation on several benchmarks and tasks confirms that our theoretical results can translateinto more efficient solving in practice.
展开▼
