{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,27]],"date-time":"2025-08-27T15:44:56Z","timestamp":1756309496558,"version":"3.40.5"},"reference-count":89,"publisher":"Cambridge University Press (CUP)","issue":"3","license":[{"start":{"date-parts":[[2024,2,21]],"date-time":"2024-02-21T00:00:00Z","timestamp":1708473600000},"content-version":"unspecified","delay-in-days":0,"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":[[2024,5]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Answer set programming (ASP) is a popular declarative programming paradigm with various applications. Programs can easily have many answer sets that cannot be enumerated in practice, but counting still allows quantifying solution spaces. If one counts under assumptions on literals, one obtains a tool to comprehend parts of the solution space, so-called <jats:italic>answer set navigation<\/jats:italic>. However, navigating through parts of the solution space requires counting many times, which is expensive in theory. <jats:italic>Knowledge compilation<\/jats:italic> compiles instances into representations on which counting works in polynomial time. However, these techniques exist only for conjunctive normal form (CNF) formulas, and compiling ASP programs into CNF formulas can introduce an exponential overhead. This paper introduces a technique to iteratively count answer sets under assumptions on knowledge compilations of CNFs that encode supported models. Our anytime technique uses the inclusion\u2013exclusion principle to improve bounds by over- and undercounting systematically. In a preliminary empirical analysis, we demonstrate promising results. After compiling the input (offline phase), our approach quickly (re)counts.<\/jats:p>","DOI":"10.1017\/s1471068424000036","type":"journal-article","created":{"date-parts":[[2024,2,21]],"date-time":"2024-02-21T12:58:33Z","timestamp":1708520313000},"page":"505-532","update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":1,"title":["IASCAR: Incremental Answer Set Counting by Anytime Refinement"],"prefix":"10.1017","volume":"24","author":[{"given":"JOHANNES K.","family":"FICHTE","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2425-6089","authenticated-orcid":false,"given":"SARAH ALICE","family":"GAGGL","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0131-6771","authenticated-orcid":false,"given":"MARKUS","family":"HECHER","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"DOMINIK","family":"RUSOVAC","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2024,2,21]]},"reference":[{"key":"S1471068424000036_ref37","doi-asserted-by":"crossref","unstructured":"Fichte, J. K. , Hecher, M. and Nadeem, M. A. 2022c. Plausibility reasoning via projected answer set counting - a hybrid approach. In Proceedings of the 31st International Joint Conference on Artificial Intelligence, (IJCAI\u201922), L. D. Raedt, Ed. International Joint Conferences on Artificial Intelligence Organization, 2620\u20132626.","DOI":"10.24963\/ijcai.2022\/363"},{"key":"S1471068424000036_ref26","unstructured":"Dvo\u0159\u00e1k, W. , Gaggl, S. A. , Rapberger, A. , Wallner, J. P. and Woltran, S. 2020. The ASPARTIX system suite. In Proceedings of the 8th International Conference on Computational Models of Argument (COMMA\u201920), Prakken, H. , Bistarelli, S. , Santini, F. and Taticchi, C. , Eds. FAIA, vol. 326. IOS Press, 461\u2013462."},{"key":"S1471068424000036_ref30","doi-asserted-by":"crossref","unstructured":"Fichte, J. K. , Gaggl, S. A. , Hecher, M. and Rusovac, D. 2022a. IASCAR: Incremental answer set counting by anytime refinement. In Proceedings of the 16th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR\u201922), G. Gottlob, D. Inclezan and M. Maratea, Eds. Lecture Notes in Computer Science, vol. 13416. Springer, 217\u2013230.","DOI":"10.1007\/978-3-031-15707-3_17"},{"volume-title":"Graduate Texts in Mathematics","year":"2008","author":"Bondy","key":"S1471068424000036_ref12"},{"key":"S1471068424000036_ref55","volume-title":"Cambridge Tracts in Theoretical Computer Science","volume":"48","author":"Kleine B\u00fcning","year":"1999"},{"volume-title":"Handbook of Automated Reasoning (in 2 volumes)","year":"2001","author":"Robinson","key":"S1471068424000036_ref77"},{"key":"S1471068424000036_ref86","first-page":"466","volume-title":"On the Complexity of Derivation in Propositional Calculus","author":"Tseytin","year":"1983"},{"key":"S1471068424000036_ref46","doi-asserted-by":"crossref","first-page":"52","DOI":"10.1016\/j.artint.2012.04.001","article-title":"Conflict-driven answer set solving: From theory to practice","volume":"187","author":"Gebser","year":"2012","journal-title":"Artificial Intelligence"},{"key":"S1471068424000036_ref24","doi-asserted-by":"crossref","unstructured":"Dimopoulos, Y. , Nebel, B. and Koehler, J. 1997. Encoding planning problems in nonmonotonic logic programs. In Proceedings of the 4th European Conference on Planning (ECP\u201997), Steel, S. and Alami, R. , Eds. Springer, 169\u2013181.","DOI":"10.1007\/3-540-63912-8_84"},{"key":"S1471068424000036_ref6","unstructured":"Bistarelli, S. , Kotthoff, L. , Santini, F. and Taticchi, C. 2020. A first overview of iccma\u201919. In Proceedings of the Workshop on Advances in Argumentation in Artificial Intelligence 2020 co-located with the 19th International Conference of the Italian Association for Artificial Intelligence (AIxIA\u201920), B. Fazzinga, F. Furfaro and F. Parisi, Eds. Workshop Proceedings, CEUR , vol. 2777. CEUR-WS.org, 90\u2013102."},{"key":"S1471068424000036_ref61","doi-asserted-by":"crossref","first-page":"413","DOI":"10.1007\/s10817-016-9370-8","article-title":"On preprocessing techniques and their impact on propositional model counting","volume":"58b","author":"Lagniez","year":"2017","journal-title":"Journal of Automated Reasoning"},{"key":"S1471068424000036_ref68","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.artint.2004.04.004","article-title":"ASSAT: Computing answer sets of a logic program by SAT solvers","volume":"157","author":"Lin","year":"2004","journal-title":"Artificial Intelligence"},{"key":"S1471068424000036_ref82","doi-asserted-by":"crossref","unstructured":"Stockmeyer, L. 1983. The complexity of approximate counting. In Proceedings of the 15h Annual ACM Symposium on Theory of Computing (STOC\u201983), New York, NY, USA. Association for Computing Machinery, 118\u2013126.","DOI":"10.1145\/800061.808740"},{"key":"S1471068424000036_ref40","doi-asserted-by":"crossref","first-page":"128","DOI":"10.1017\/S147106842100003X","article-title":"Exploiting database management systems and treewidth for counting","volume":"22e","author":"Fichte","year":"2022","journal-title":"Theory and Practice of Logic Programming"},{"key":"S1471068424000036_ref1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.artint.2023.103931","article-title":"ASP and subset minimality: Enumeration, cautious reasoning and MUSes","volume":"320","author":"Alviano","year":"2023","journal-title":"Artificial Intelligence"},{"key":"S1471068424000036_ref11","unstructured":"Bomanson, J. , Gebser, M. and Janhunen, T. 2016. Rewriting optimization statements in answer-set programs. In Technical Communications of the 32nd International Conference on Logic Programming (ICLP\u201916), Carro, M. , King, A. , Saeedloei, N. and Vos, M. D. , Eds. OpenAccess Series in Informatics (OASIcs), vol. 52, Dagstuhl, Germany. Dagstuhl Publishing, 5:1\u20135:15."},{"key":"S1471068424000036_ref8","doi-asserted-by":"crossref","first-page":"4","DOI":"10.1017\/S1471068415000162","article-title":"Knowledge compilation of logic programs using approximation fixpoint theory","volume":"15","author":"Bogaerts","year":"2015","journal-title":"Theory and Practice of Logic Programming"},{"key":"S1471068424000036_ref28","first-page":"51","article-title":"Consistency of clark\u2019s completion and existence of stable models","volume":"1","author":"Fages","year":"1994","journal-title":"Journal of Methods of Logic in Computer Science"},{"key":"S1471068424000036_ref69","unstructured":"Mailly, J. , Lonca, E. , Lagniez, J. and Rossit, J. 2021. The fourth international competition on computational models of argumentation (ICCMA\u201921). http:\/\/argumentationcompetition.org\/2021\/index.html."},{"key":"S1471068424000036_ref72","unstructured":"Masina, G. , Spallitta, G. and Sebastiani, R. 2023. On CNF Conversion for Disjoint SAT Enumeration. In Proceedings of the 26th International Conference on Theory and Applications of Satisfiability Testing (SAT\u201923), Mahajan, M. and Slivovsky, F. , Eds. Leibniz International Proceedings in Informatics (LIPIcs), vol. 271, Alghero, Italy. Dagstuhl Publishing, 15:1\u201315:16."},{"key":"S1471068424000036_ref76","doi-asserted-by":"crossref","unstructured":"Pontelli, E. , Son, T. , Baral, C. and Gelfond, G. 2012. Answer set programming and planning with knowledge and world-altering actions in multiple agent domains. In Correct Reasoning \u2013 Essays on Logic-Based AI in Honour of Vladimir Lifschitz, E. Erdem, J. Lee, Y. Lierler and D. Pearce, Eds. Lecture Notes in Computer Science, vol. 7265. Springer, 509\u2013526.","DOI":"10.1007\/978-3-642-30743-0_35"},{"key":"S1471068424000036_ref73","unstructured":"Meel, K. S. , Shrotri, A. A. and Vardi, M. Y. 2018. On hashing-based approaches to approximate DNF-counting. In Proceedings of the 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS\u201917), Lokam, S. and Ramanujam, R. , Eds., Leibniz International Proceedings in Informatics (LIPIcs), vol. 93, Dagstuhl, Germany. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, 41:1\u201341:14."},{"key":"S1471068424000036_ref13","doi-asserted-by":"crossref","first-page":"92","DOI":"10.1145\/2043174.2043195","article-title":"Answer set programming at a glance","volume":"54","author":"Brewka","year":"2011","journal-title":"Communications of the ACM"},{"key":"S1471068424000036_ref89","first-page":"3","article-title":"Satisfiability-based set membership filters","volume":"8","author":"Weaver","year":"2012","journal-title":"Journal on Satisfiability, Boolean Modeling and Computation"},{"key":"S1471068424000036_ref53","doi-asserted-by":"crossref","unstructured":"Janhunen, T. and Niemel\u00e4, I. 2011. Compact translations of non-disjunctive answer set programs to propositional clauses. In Logic Programming, Knowledge Representation, and Nonmonotonic Reasoning \u2013 Essays Dedicated to Michael Gelfond on the Occasion of His 65th Birthday, M. Balduccini and T. Son, Eds. Lecture Notes in Artificial Intelligence, vol. 6565. Springer, 111\u2013130.","DOI":"10.1007\/978-3-642-20832-4_8"},{"key":"S1471068424000036_ref83","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0304-3975(76)90061-X","article-title":"The polynomial-time hierarchy","volume":"3","author":"Stockmeyer","year":"1976","journal-title":"Theoretical Computer Science"},{"key":"S1471068424000036_ref43","doi-asserted-by":"crossref","first-page":"103193","DOI":"10.1016\/j.artint.2019.103193","article-title":"Design and results of the second international competition on computational models of argumentation","volume":"279","author":"Gaggl","year":"2020","journal-title":"Artificial Intelligence"},{"key":"S1471068424000036_ref78","doi-asserted-by":"crossref","first-page":"139","DOI":"10.3233\/SAT190083","article-title":"Controlling a solver execution with the runsolver tool","volume":"7","author":"Roussel","year":"2011","journal-title":"Journal on Satisfiability, Boolean Modeling and Computation"},{"key":"S1471068424000036_ref9","doi-asserted-by":"crossref","unstructured":"B\u00f6hl, E. and Gaggl, S. A. 2022. Tunas - fishing for diverse answer sets: A multi-shot trade up strategy. In Proceedings of the 16th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR\u201922), G. Gottlob, D. Inclezan and M. Maratea, Eds. Notes, Lecture in Computer Science, vol. 13416. Springer, 89\u2013102.","DOI":"10.1007\/978-3-031-15707-3_8"},{"key":"S1471068424000036_ref31","doi-asserted-by":"crossref","unstructured":"Fichte, J. K. , Gaggl, S. A. , Hecher, M. and Rusovac, D. 2023. IASCAR: Incremental answer set counting by anytime refinement (experiments).","DOI":"10.1007\/978-3-031-15707-3_17"},{"key":"S1471068424000036_ref75","doi-asserted-by":"crossref","unstructured":"Nogueira, M. , Balduccini, M. , Gelfond, M. , Watson, R. and Barry, M. 2001. An a-prolog decision support system for the space shuttle. In Proceedings of the 3rd International Symposium on Practical Aspects of Declarative Languages (PADL\u201901), I. V. Ramakrishnan, Ed., Vegas, Las , Nevada, USA. Springer , 169\u2013183.","DOI":"10.1007\/3-540-45241-9_12"},{"key":"S1471068424000036_ref84","doi-asserted-by":"crossref","first-page":"865","DOI":"10.1137\/0220053","article-title":"PP is as hard as the polynomial-time hierarchy","volume":"20","author":"Toda","year":"1991","journal-title":"SIAM Journal on Computing"},{"key":"S1471068424000036_ref87","unstructured":"van der Kouwe, E. , Andriesse, D. , Bos, H. , Giuffrida, C. and Heiser, G. 2018. Benchmarking crimes: An emerging threat in systems security. CoRR, abs\/1801.02381, 1\u201317."},{"key":"S1471068424000036_ref17","doi-asserted-by":"crossref","unstructured":"Dachselt, R. , Gaggl, S. A. , Kr\u00f6tzsch, M. , M\u00e9ndez, J. , Rusovac, D. and Yang, M. 2022. NEXAS: A visual tool for navigating and exploring argumentationsolution spaces. In Proceedings of the 9th International Conference on Computational Models of Argument (COMMA\u201922), F. Toni, Ed. FAIA, vol. 220146. IOS Press, 116\u2013127.","DOI":"10.3233\/FAIA220146"},{"key":"S1471068424000036_ref51","doi-asserted-by":"crossref","first-page":"103651","DOI":"10.1016\/j.artint.2021.103651","article-title":"Treewidth-aware reductions of normal ASP to SAT \u2013 Is normal ASP harder than SAT after all?","volume":"304","author":"Hecher","year":"2022","journal-title":"Artificial Intelligence"},{"key":"S1471068424000036_ref22","unstructured":"Dell, H. , Komusiewicz, C. , Talmon, N. and Weller, M. 2017. The pace 2017 parameterized algorithms and computational experiments challenge: The second iteration. In Proceedings of the 12th International Symposium on Parameterized and Exact Computation, IPEC\u201917, Lokshtanov, D. and Nishimura, N. , Eds. Leibniz International Proceedings in Informatics (LIPIcs). Dagstuhl Publishing, 30:1\u201430:13."},{"key":"S1471068424000036_ref10","doi-asserted-by":"crossref","unstructured":"B\u00f6hl, E. , Gaggl, S. A. and Rusovac, D. 2023. Representative answer sets: Collecting something of everything. In Proceedings of the 26th European Conference on Artificial Intelligence (ECAI\u201923), Gal, K. , Now\u00e9, A. , Nalepa, G. J. , Fairstein, R. and Radulescu, R. , Eds. FAIA, vol. 372. IOS Press, 271\u2013278.","DOI":"10.3233\/FAIA230280"},{"key":"S1471068424000036_ref44","doi-asserted-by":"crossref","unstructured":"Gebser, M. , Kaminski, R. , K\u00f6nig, A. and Schaub, T. 2011. Advances in gringo series 3. In Proceedings of the 11th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR\u201911), Delgrande, J. P. and Faber, W. , Eds. Springer, 345\u2013351.","DOI":"10.1007\/978-3-642-20895-9_39"},{"key":"S1471068424000036_ref60","doi-asserted-by":"crossref","unstructured":"Lagniez, J. and Marquis, P. 2017a. An improved decision-DDNF compiler. In Proceedings of the 26th International Joint Conference on Artificial Intelligence (IJCAI\u201917), C. Sierra, Ed., Melbourne, VIC, Australia. The AAAI Press, 667\u2013673.","DOI":"10.24963\/ijcai.2017\/93"},{"key":"S1471068424000036_ref15","doi-asserted-by":"crossref","unstructured":"Chakraborty, S. , Fremont, D. J. , Meel, K. S. , Seshia, S. A. and Vardi, M. Y. 2014. Distribution-aware sampling and weighted model counting for SAT. In Proceedings of the 28th AAAI Conference on Artificial Intelligence (AAAI\u201914), Brodley, C. E. and Stone, P. , Eds., Qu\u00e9bec City, QC, Canada. The AAAI Press, 1722\u20131730.","DOI":"10.1609\/aaai.v28i1.8990"},{"key":"S1471068424000036_ref20","first-page":"318","volume-title":"Proceedings of the 16th European Conference on Artificial Intelligence (ECAI\u201904)","author":"Darwiche","year":"2004"},{"key":"S1471068424000036_ref62","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1016\/0020-0190(83)90044-3","article-title":"Bpp and the polynomial hierarchy","volume":"17","author":"Lautemann","year":"1983","journal-title":"Information Processing Letters"},{"key":"S1471068424000036_ref34","doi-asserted-by":"crossref","unstructured":"Fichte, J. K. , Hecher, M. and Hamiti, F. 2021a. The model counting competition. ACM Journal of Experimental Algorithmics, 26a, 1\u201326.","DOI":"10.1145\/3459080"},{"key":"S1471068424000036_ref18","unstructured":"Darwiche, A. 1999. Compiling knowledge into decomposable negation normal form. In Proceedings of the 16th International Joint Conference on Artificial Intelligence, (IJCAI\u201999), T. Dean, Ed. Kaufmann, Morgan , 284\u2013289."},{"key":"S1471068424000036_ref41","doi-asserted-by":"crossref","unstructured":"Fichte, J. K. , Manthey, N. , Schidler, A. and Stecklina, J. 2020. Towards faster reasoners by using transparent huge pages. In Proceedings of the 26th International Conference on Principles and Practice of Constraint Programming (CP\u201920), H. Simonis, Ed. Lecture Notes in Computer Science. Springer, 304\u2013322.","DOI":"10.1007\/978-3-030-58475-7_18"},{"key":"S1471068424000036_ref85","doi-asserted-by":"crossref","first-page":"881","DOI":"10.1017\/S1471068410000463","article-title":"Trichotomy and dichotomy results on the complexity of reasoning with disjunctive logic programs","volume":"11","author":"Truszczy\u0144ski","year":"2011","journal-title":"Theory and Practice of Logic Programming"},{"key":"S1471068424000036_ref36","doi-asserted-by":"crossref","unstructured":"Fichte, J. K. , Hecher, M. , Morak, M. and Woltran, S. 2017. Answer set solving with bounded treewidth revisited. In Proceedings of the 14th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR\u201917), M. Balduccini and T. Janhunen, Eds. Lecture Notes in Computer Science, vol. 10377. Springer, 132\u2013145.","DOI":"10.1007\/978-3-319-61660-5_13"},{"key":"S1471068424000036_ref32","doi-asserted-by":"crossref","unstructured":"Fichte, J. K. , Gaggl, S. A. and Rusovac, D. 2022b. Rushing and strolling among answer sets \u2013 navigation made easy. In Proceedings of the 36th AAAI Conference on Artificial Intelligence (AAAI\u201922). AAAI Press, 5651\u20135659.","DOI":"10.1609\/aaai.v36i5.20506"},{"key":"S1471068424000036_ref80","doi-asserted-by":"crossref","unstructured":"Sipser, M. 1983. A complexity theoretic approach to randomness. In Proceedings of the 15th Annual ACM Symposium on Theory of Computing (STOC\u201983), Boston, Massachusetts, USA, 330\u2013335.","DOI":"10.1145\/800061.808762"},{"key":"S1471068424000036_ref19","doi-asserted-by":"crossref","first-page":"1","DOI":"10.3166\/jancl.11.11-34","article-title":"On the tractable counting of theory models and its application to truth maintenance and belief revision","volume":"11","author":"Darwiche","year":"2001","journal-title":"Journal of Applied Non-Classical Logics"},{"year":"2003","author":"Lee","key":"S1471068424000036_ref64"},{"key":"S1471068424000036_ref45","doi-asserted-by":"crossref","unstructured":"Gebser, M. , Kaufmann, B. and Schaub, T. 2009. The conflict-driven answer set solver clasp: Progress report. In Proceedings of the 10th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR\u201909), Erdem, E. , Lin, F. and Schaub, T. , Eds. Springer, 509\u2013514.","DOI":"10.1007\/978-3-642-04238-6_50"},{"key":"S1471068424000036_ref67","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1145\/1131313.1131316","article-title":"Why are there so many loop formulas?","volume":"7","author":"Lifschitz","year":"2006","journal-title":"ACM Transactions on Computational Logic"},{"key":"S1471068424000036_ref70","doi-asserted-by":"crossref","unstructured":"Marek, V. W. and Truszczy\u0144ski, M. 1999. Stable models and an alternative logic programming paradigm. In The Logic Programming Paradigm: A 25-Year Perspective, K. R. Apt, Marek, V. W. , Truszczy\u0144ski, M. and Warren, D. S. , Eds. Artificial Intelligence. Springer, 375\u2013398.","DOI":"10.1007\/978-3-642-60085-2_17"},{"key":"S1471068424000036_ref33","unstructured":"Fichte, J. K. and Hecher, M. 2023. The model counting competitions 2021\u20132023. https:\/\/mccompetition.org\/past_iterations."},{"first-page":"4218","year":"2015","author":"Wang","key":"S1471068424000036_ref88"},{"key":"S1471068424000036_ref48","unstructured":"Gelfond, M. and Lifschitz, V. 1988. The stable model semantics for logic programming. In Proceedings of the 5th International Conference and Symposium on Logic Programming (ICLP\/SLP\u201988), Kowalski, R. A. and Bowen, K. A. , Eds., vol. 2. MIT Press, 1070\u20131080."},{"key":"S1471068424000036_ref39","unstructured":"Fichte, J. K. , Hecher, M. and Roland, V. 2022d. Proofs for Propositional Model Counting. In Proceedings of the 25th International Conference on Theory and Applications of Satisfiability Testing (SAT\u201922), Meel, K. S. and Strichman, O. , Eds. Leibniz International Proceedings in Informatics (LIPIcs), vol. 236, Dagstuhl, Germany. Dagstuhl Publishing, 30:1\u201330:24."},{"key":"S1471068424000036_ref16","doi-asserted-by":"crossref","unstructured":"Clark, K. L. 1978. Negation as failure. In Logic and Data Bases. Springer, 293\u2013322.","DOI":"10.1007\/978-1-4684-3384-5_11"},{"key":"S1471068424000036_ref47","doi-asserted-by":"crossref","unstructured":"Gebser, M. , Maratea, M. and Ricca, F. 2017. The design of the seventh answer set programming competition. In Proceedings of the 14th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR\u201917), Balduccini, M. and Janhunen, T. , Eds. Springer, 3\u20139.","DOI":"10.1007\/978-3-319-61660-5_1"},{"key":"S1471068424000036_ref50","doi-asserted-by":"crossref","unstructured":"Hahn, S. , Sabuncu, O. , Schaub, T. and Stolzmann, T. 2022. Clingraph: ASP-based visualization. In Proceedings of the 16th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR\u201922), G. Gottlob, D. Inclezan and M. Maratea, Eds. Lecture Notes in Computer Science, vol. 13416. Springer, 401\u2013414.","DOI":"10.1007\/978-3-031-15707-3_31"},{"key":"S1471068424000036_ref57","doi-asserted-by":"crossref","unstructured":"Kuiter, E. , Krieter, S. , Sundermann, C. , Th\u00fcm, T. and Saake, G. 2023. Tseitin or not tseitin? the impact of cnf transformations on feature-model analyses. In Proceedings of the 37th IEEE\/ACM International Conference on Automated Software Engineering (ASE\u201922), Rochester, MI, USA. ACM.","DOI":"10.1145\/3551349.3556938"},{"key":"S1471068424000036_ref66","doi-asserted-by":"crossref","first-page":"357","DOI":"10.1007\/978-3-642-60085-2_16","volume-title":"The Logic Programming Paradigm","author":"Lifschitz","year":"1999"},{"key":"S1471068424000036_ref65","unstructured":"Lee, J. and Wang, Y. 2015. A probabilistic extension of the stable model semantics. In 2015 AAAI Spring Symposia, Stanford University. AAAI Press."},{"key":"S1471068424000036_ref54","doi-asserted-by":"crossref","unstructured":"Kabir, M. , Everardo, F. O. , Shukla, A. K. , Hecher, M. , Fichte, J. K. and Meel, K. S. 2022. ApproxASP \u2013 a scalable approximate answer set counter. Proceedings of the 36th AAAI Conference on Artificial Intelligence (AAAI\u201922), 5755\u20135764.","DOI":"10.1609\/aaai.v36i5.20518"},{"key":"S1471068424000036_ref35","unstructured":"Fichte, J. K. , Hecher, M. , McCreesh, C. and Shahab, A. 2021b. Complications for computational experiments from modern processors. In Proceedings of the 27th International Conference on Principles and Practice of Constraint Programming, (CP\u201921), L. D. Michel, Ed. Leibniz International Proceedings in Informatics (LIPIcs), vol. 210. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 25:1\u201325:21."},{"key":"S1471068424000036_ref58","unstructured":"Lagniez, J. , Lonca, E. and Marquis, P. 2016. Improving model counting by leveraging definability. In Proceedings of 25th International Joint Conference on Artificial Intelligence (IJCAI\u201916), S. Kambhampati, Ed., New York City, NY, USA. The AAAI Press, 751\u2013757."},{"key":"S1471068424000036_ref23","doi-asserted-by":"crossref","unstructured":"Dewoprabowo, R. , Fichte, J. K. , Gorczyca, P. J. and Hecher, M. 2022. A practical account into counting dung\u2019s extensions by dynamic programming. In Proceedings of the 16th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR\u201922), Gottlob, G. , Inclezan, D. and Maratea, M. , Eds. Springer, 387\u2013400.","DOI":"10.1007\/978-3-031-15707-3_30"},{"key":"S1471068424000036_ref52","doi-asserted-by":"crossref","first-page":"1","DOI":"10.3166\/jancl.16.35-86","article-title":"Some (in)translatability results for normal logic programs and propositional theories","volume":"16","author":"Janhunen","year":"2006","journal-title":"Journal of Applied Non-Classical Logics"},{"key":"S1471068424000036_ref2","doi-asserted-by":"crossref","unstructured":"Apt, K. R. , Blair, H. A. and Walker, A. 1988. Towards a theory of declarative knowledge. In Foundations of Deductive Databases and Logic Programming. Elsevier, 89\u2013148.","DOI":"10.1016\/B978-0-934613-40-8.50006-3"},{"key":"S1471068424000036_ref38","unstructured":"Fichte, J. K. , Hecher, M. and Roland, V. 2021c. Parallel model counting with CUDA: Algorithm engineering for efficient hardware utilization. In Proceedings of the 27th International Conference on Principles and Practice of Constraint Programming (CP\u201921), L. D. Michel, Ed. Leibniz International Proceedings in Informatics (LIPIcs), vol. 210. Dagstuhl Publishing, 24:1\u201324:20."},{"key":"S1471068424000036_ref59","doi-asserted-by":"crossref","unstructured":"Lagniez, J. and Marquis, P. 2014. Preprocessing for propositional model counting. In Proceedings of the 28th AAAI Conference on Artificial Intelligence (AAAI\u201914), Brodley, C. E. and Stone, P. , Eds., Qu\u00e9bec City, QC, Canada. The AAAI Press, 2688\u20132694.","DOI":"10.1609\/aaai.v28i1.9116"},{"key":"S1471068424000036_ref3","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511543357","volume-title":"Knowledge Representation, Reasoning and Declarative Problem Solving","author":"Baral","year":"2003"},{"key":"S1471068424000036_ref21","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1613\/jair.989","article-title":"A knowledge compilation map","volume":"17","author":"Darwiche","year":"2002","journal-title":"Journal of Artificial Intelligence Research"},{"key":"S1471068424000036_ref14","unstructured":"Bryant, R. E. , Nawrocki, W. , Avigad, J. and Heule, M. J. H. 2023. Certified knowledge compilation with application to verified model counting. In Proceedings of the 26th International Conference on Theory and Applications of Satisfiability Testing (SAT\u201923), Mahajan, M. and Slivovsky, F. , Eds. Leibniz International Proceedings in Informatics (LIPIcs), vol. 271. Dagstuhl Publishing, 6:1\u20136:20."},{"key":"S1471068424000036_ref42","doi-asserted-by":"crossref","first-page":"358","DOI":"10.1017\/S1471068414000076","article-title":"Inference and learning in probabilistic logic programs using weighted Boolean formulas","volume":"15","author":"Fierens","year":"2015","journal-title":"Theory and Practice of Logic Programming"},{"key":"S1471068424000036_ref27","doi-asserted-by":"crossref","unstructured":"Eiter, T. , Hecher, M. and Kiesel, R. 2021. Treewidth-aware cycle breaking for algebraic answer set counting. In Proceedings of the 18th International Conference on Principles of Knowledge Representation and Reasoning (KR\u201921), Bienvenu, M. , Lakemeyer, G. and Erdem, E. , Eds. Organization, IJCAI , 269\u2013279.","DOI":"10.24963\/kr.2021\/26"},{"key":"S1471068424000036_ref5","unstructured":"Beyersdorff, O. , Hoffmann, T. and Spachmann, L. N. 2023. Proof Complexity of Propositional Model Counting. In Proceedings of the 26th International Conference on Theory and Applications of Satisfiability Testing (SAT\u201923), Mahajan, M. and Slivovsky, F. , Eds. Leibniz International Proceedings in Informatics (LIPIcs), vol. 271. Dagstuhl Publishing, 2:1\u20132:18."},{"key":"S1471068424000036_ref25","unstructured":"Dodaro, C. , Redl, C. and Sch\u00fcller, P. 2019. The answer set programming challenge. https:\/\/sites.google.com\/view\/aspcomp2019\/."},{"key":"S1471068424000036_ref4","doi-asserted-by":"crossref","first-page":"575","DOI":"10.1017\/S1471068421000399","article-title":"Utilizing treewidth for quantitative reasoning on epistemic logic programs","volume":"21","author":"Besin","year":"2021","journal-title":"Theory and Practice of Logic Programming"},{"key":"S1471068424000036_ref74","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1023\/A:1018930122475","article-title":"Logic programs with stable model semantics as a constraint programming paradigm","volume":"25","author":"Niemel\u00e4","year":"1999","journal-title":"Annals of Mathematics and Artificial Intelligence"},{"key":"S1471068424000036_ref29","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1007\/s10472-006-9025-2","article-title":"A generalization of the lin-zhao theorem","volume":"47","author":"Ferraris","year":"2006","journal-title":"Annals of Mathematics and Artificial Intelligence"},{"key":"S1471068424000036_ref56","unstructured":"Korhonen, T. and J\u00e4rvisalo, M. 2021. Integrating tree decompositions into decision heuristics of propositional model counters. In Proceedings of the 27th International Conference on Principles and Practice of Constraint Programming (CP\u201921), L. D. Michel, Ed. Leibniz International Proceedings in Informatics (LIPIcs), vol. 210, Dagstuhl, Germany. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik, 8:1\u20138:11."},{"key":"S1471068424000036_ref71","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1016\/0304-3975(92)90019-C","article-title":"The relationship between stable, supported, default and autoepistemic semantics for general logic programs","volume":"103","author":"Marek","year":"1992","journal-title":"Theoretical Computer Science"},{"key":"S1471068424000036_ref81","unstructured":"Spallitta, G. , Sebastiani, R. and Biere, A. 2023. Enumerating disjoint partial models without blocking clauses. CoRR, abs\/2306.00461."},{"year":"2005","author":"Lee","key":"S1471068424000036_ref63"},{"key":"S1471068424000036_ref79","unstructured":"Sang, T. , Beame, P. and Kautz, H. 2005. Performing Bayesian inference by weighted model counting. In AAAI\u201905, Pittsburgh, Pennsylvania, USA. The AAAI Press."},{"key":"S1471068424000036_ref49","doi-asserted-by":"crossref","unstructured":"Gelfond, M. and Lifschitz, V. 1991. Classical negation in logic programs and disjunctive databases. New Generation Computing, 9, 3\/4, 365\u2013386.","DOI":"10.1007\/BF03037169"},{"key":"S1471068424000036_ref7","doi-asserted-by":"crossref","first-page":"422","DOI":"10.1145\/362686.362692","article-title":"Space\/time trade-offs in hash coding with allowable errors","volume":"13","author":"Bloom","year":"1970","journal-title":"Communications of the ACM"}],"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\/S1471068424000036","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,10]],"date-time":"2024-10-10T13:02:50Z","timestamp":1728565370000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S1471068424000036\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,2,21]]},"references-count":89,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,5]]}},"alternative-id":["S1471068424000036"],"URL":"https:\/\/doi.org\/10.1017\/s1471068424000036","relation":{},"ISSN":["1471-0684","1475-3081"],"issn-type":[{"type":"print","value":"1471-0684"},{"type":"electronic","value":"1475-3081"}],"subject":[],"published":{"date-parts":[[2024,2,21]]},"assertion":[{"value":"\u00a9 The Author(s), 2024. 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"}]}}