{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,16]],"date-time":"2026-06-16T13:14:18Z","timestamp":1781615658702,"version":"3.54.5"},"reference-count":25,"publisher":"Cambridge University Press (CUP)","issue":"4","license":[{"start":{"date-parts":[[2022,8,3]],"date-time":"2022-08-03T00:00:00Z","timestamp":1659484800000},"content-version":"unspecified","delay-in-days":33,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["Theory and Practice of Logic Programming"],"published-print":{"date-parts":[[2022,7]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Quantitative extensions of logic programming often require the solution of so called <jats:italic>second level<\/jats:italic> inference 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 weighted or algebraic model counting setting of probabilistic logic programming under the distribution semantics. We introduce Second Level Algebraic Model Counting (2AMC) as a generic framework for these kinds of problems. As 2AMC is to (algebraic) model counting what forall-exists-SAT is to propositional satisfiability, it is notoriously hard to solve. First level techniques based on Knowledge Compilation (KC) have been adapted for specific 2AMC instances by imposing variable order constraints on the resulting circuit. However, those constraints can severely increase the circuit size and thus decrease the efficiency of such approaches. We show that we can exploit the logical structure of a 2AMC problem to omit parts of these constraints, thus limiting the negative effect. Furthermore, we introduce and implement a strategy to generate a sufficient set of constraints statically, with a priori guarantees for the performance of KC. Our empirical evaluation on several benchmarks and tasks confirms that our theoretical results can translate into more efficient solving in practice.<\/jats:p>","DOI":"10.1017\/s147106842200014x","type":"journal-article","created":{"date-parts":[[2022,8,3]],"date-time":"2022-08-03T12:42:14Z","timestamp":1659530534000},"page":"505-522","update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":9,"title":["Efficient Knowledge Compilation Beyond Weighted Model Counting"],"prefix":"10.1017","volume":"22","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8866-3452","authenticated-orcid":false,"given":"RAFAEL","family":"KIESEL","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5845-6914","authenticated-orcid":false,"given":"PIETRO","family":"TOTIS","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6742-4057","authenticated-orcid":false,"given":"ANGELIKA","family":"KIMMIG","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"56","published-online":{"date-parts":[[2022,8,3]]},"reference":[{"key":"S147106842200014X_ref14","first-page":"46","article-title":"Algebraic model counting","author":"Kimmig","year":"2017","journal-title":"JAL 22"},{"key":"S147106842200014X_ref17","first-page":"495","article-title":"Combining stochastic constraint optimization and probabilistic programming - from knowledge compilation to constraint solving","author":"Latour","year":"2017","journal-title":"CP"},{"key":"S147106842200014X_ref20","first-page":"3141","article-title":"A top-down compiler for sentential decision diagrams","author":"Oztok","year":"2015","journal-title":"In IJCAI"},{"key":"S147106842200014X_ref22","unstructured":"Skryagin, A. , Stammer, W. , Ochs, D. , Dhami, D. S. and Kersting, K. 2021. SLASH: Embracing probabilistic circuits into neural answer set programming. CoRR, abs\/2110.03395."},{"key":"S147106842200014X_ref21","first-page":"433","article-title":"The pita system: Tabling and answer subsumption for reasoning under uncertainty","volume":"4","author":"Riguzzi","year":"2011","journal-title":"TPLP 11"},{"key":"S147106842200014X_ref25","first-page":"1755","article-title":"Neurasp: Embracing neural networks into answer set programming","author":"Yang","year":"2020","journal-title":"In IJCAI"},{"key":"S147106842200014X_ref24","doi-asserted-by":"crossref","unstructured":"Van den Broeck, G. , Thon, I. , van Otterlo, M. and De Raedt, L. 2010. DTProbLog: A decision-theoretic probabilistic Prolog. In AAAI.","DOI":"10.1609\/aaai.v24i1.7755"},{"key":"S147106842200014X_ref10","first-page":"269","article-title":"Treewidth-aware cycle breaking for algebraic answer set counting","author":"Eiter","year":"2021","journal-title":"KR"},{"key":"S147106842200014X_ref3","first-page":"57","article-title":"Probabilistic reasoning with answer sets","volume":"1","author":"Baral","year":"2009","journal-title":"TPLP 9"},{"key":"S147106842200014X_ref15","article-title":"Integrating tree decompositions into decision heuristics of propositional model counters (short paper)","volume":"210","author":"Korhonen","year":"2021","journal-title":"CP. LIPIcs"},{"key":"S147106842200014X_ref2","doi-asserted-by":"publisher","DOI":"10.1038\/scientificamerican0503-60"},{"key":"S147106842200014X_ref18","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v31i1.10686"},{"key":"S147106842200014X_ref5","first-page":"328","article-title":"New advances in compiling CNF into decomposable negation normal form","author":"Darwiche","year":"2004","journal-title":"ECAI"},{"key":"S147106842200014X_ref7","unstructured":"Dell, H. , Komusiewicz, C. , Talmon, N. and Weller, M. 2017. PACE: The second iteration. In International Symposium on Parameterized and Exact Computation (IPEC), 30:1\u201330:13."},{"key":"S147106842200014X_ref12","unstructured":"Gebser, M. , Kaminski, R. , Kaufmann, B. and Schaub, T. 2014. Clingo= ASP+ control: Preliminary report. arXiv preprint arXiv:1405.3694."},{"key":"S147106842200014X_ref4","first-page":"641","article-title":"MAP inference for probabilistic logic programming","volume":"5","author":"Bellodi","year":"2020","journal-title":"TPLP 20"},{"key":"S147106842200014X_ref1","first-page":"3468","article-title":"Stable model counting and its application in probabilistic logic programming","author":"Aziz","year":"2015","journal-title":"AAAI"},{"key":"S147106842200014X_ref13","doi-asserted-by":"crossref","unstructured":"Kimmig, A. , Van den Broeck, G. and De Raedt, L. 2011. An algebraic prolog for reasoning about possible worlds. In AAAI.","DOI":"10.1609\/aaai.v25i1.7852"},{"key":"S147106842200014X_ref8","first-page":"2462","article-title":"ProbLog: A probabilistic Prolog and its application in link discovery","volume":"7","author":"De Raedt","year":"2007","journal-title":"In IJCAI"},{"key":"S147106842200014X_ref16","first-page":"751","article-title":"Improving model counting by leveraging definability","author":"Lagniez","year":"2016","journal-title":"In IJCAI"},{"key":"S147106842200014X_ref19","first-page":"3749","article-title":"DeepProbLog: Neural probabilistic logic programming","author":"Manhaeve","year":"2018","journal-title":"NeurIPS"},{"key":"S147106842200014X_ref9","first-page":"2569","article-title":"Algebraic circuits for decision theoretic inference and learning","volume":"325","author":"Derkinderen","year":"2020","journal-title":"ECAI"},{"key":"S147106842200014X_ref23","unstructured":"Totis, P. , Kimmig, A. and De Raedt, L. 2021. SMProbLog: Stable model semantics in ProbLog and its applications in argumentation. StarAI, abs\/2110.01990."},{"key":"S147106842200014X_ref6","unstructured":"Darwiche, A. 2011. SDD: A new canonical representation of propositional knowledge bases. In IJCAI."},{"key":"S147106842200014X_ref11","first-page":"358","article-title":"Inference and learning in probabilistic logic programs using weighted boolean formulas","volume":"3","author":"Fierens","year":"2015","journal-title":"TPLP 15"}],"container-title":["Theory and Practice of Logic Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S147106842200014X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,4,2]],"date-time":"2023-04-02T23:40:31Z","timestamp":1680478831000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S147106842200014X\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,7]]},"references-count":25,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2022,7]]}},"alternative-id":["S147106842200014X"],"URL":"https:\/\/doi.org\/10.1017\/s147106842200014x","relation":{},"ISSN":["1471-0684","1475-3081"],"issn-type":[{"value":"1471-0684","type":"print"},{"value":"1475-3081","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,7]]},"assertion":[{"value":"\u00a9 The Author(s), 2022. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}},{"value":"This is an Open Access article, distributed under the terms of the Creative Commons Attribution licence (http:\/\/creativecommons.org\/licenses\/by\/4.0\/), which permits unrestricted re-use, distribution and reproduction, provided the original article is properly cited.","name":"license","label":"License","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}