{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,1]],"date-time":"2026-03-01T11:53:47Z","timestamp":1772366027702,"version":"3.50.1"},"reference-count":25,"publisher":"Cambridge University Press (CUP)","issue":"5","license":[{"start":{"date-parts":[[2021,11,5]],"date-time":"2021-11-05T00:00:00Z","timestamp":1636070400000},"content-version":"unspecified","delay-in-days":65,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["Theory and Practice of Logic Programming"],"published-print":{"date-parts":[[2021,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Extending the popular answer set programming paradigm by introspective reasoning capacities has received increasing interest within the last years. Particular attention is given to the formalism of epistemic logic programs (ELPs) where standard rules are equipped with modal operators which allow to express conditions on literals for being known or possible, that is, contained in all or some answer sets, respectively. ELPs thus deliver multiple collections of answer sets, known as world views. Employing ELPs for reasoning problems so far has mainly been restricted to standard decision problems (complexity analysis) and enumeration (development of systems) of world views. In this paper, we take a next step and contribute to epistemic logic programming in two ways: First, we establish quantitative reasoning for ELPs, where the acceptance of a certain set of literals depends on the number (proportion) of world views that are compatible with the set. Second, we present a novel system that is capable of efficiently solving the underlying counting problems required to answer such quantitative reasoning problems. Our system exploits the graph-based measure treewidth and works by iteratively finding and refining (graph) abstractions of an ELP program. On top of these abstractions, we apply dynamic programming that is combined with utilizing existing search-based solvers like (e)clingo for hard combinatorial subproblems that appear during solving. It turns out that our approach is competitive with existing systems that were introduced recently.<\/jats:p>","DOI":"10.1017\/s1471068421000399","type":"journal-article","created":{"date-parts":[[2021,11,5]],"date-time":"2021-11-05T14:49:45Z","timestamp":1636123785000},"page":"575-592","update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":2,"title":["Utilizing Treewidth for Quantitative Reasoning on Epistemic Logic Programs"],"prefix":"10.1017","volume":"21","author":[{"given":"VIKTOR","family":"BESIN","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0131-6771","authenticated-orcid":false,"given":"MARKUS","family":"HECHER","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1594-8972","authenticated-orcid":false,"given":"STEFAN","family":"WOLTRAN","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2021,11,5]]},"reference":[{"key":"S1471068421000399_ref7","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068420000228"},{"key":"S1471068421000399_ref6","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-20528-7_10"},{"key":"S1471068421000399_ref18","doi-asserted-by":"crossref","unstructured":"Hecher, M. , Thier, P. and Woltran, S. 2020b. Taming high treewidth with abstraction, nested dynamic programming, and database technology. In SAT 2020. LNCS, vol. 12178. Springer, 343\u2013360.","DOI":"10.1007\/978-3-030-51825-7_25"},{"key":"S1471068421000399_ref1","doi-asserted-by":"crossref","unstructured":"Abseher, M. , Musliu, N. and Woltran, S. 2017. htd \u2013 A free, open-source framework for (customized) tree decompositions and beyond. In CPAIOR\u201917. LNCS, vol. 10335. Springer Verlag, 376\u2013386.","DOI":"10.1007\/978-3-319-59776-8_30"},{"key":"S1471068421000399_ref13","unstructured":"Ganian, R. , Ramanujan, M. S. , and Szeider, S. 2017. Combining treewidth and backdoors for CSP. In STACS\u201917. 36:1\u201336:17."},{"key":"S1471068421000399_ref9","unstructured":"Fichte, J. K. , Hecher, M. and Meier, A. 2021. Knowledge-base degrees of inconsistency: Complexity and counting. In AAAI. AAAI Press, 6349\u20136357."},{"key":"S1471068421000399_ref15","unstructured":"Hanks, S. and Mcdermott, D. 1986. Default reasoning, nonmonotonic logics, and the frame problem. In AAAI\u201986: Proceedings of the Fifth AAAI National Conference on Artificial Intelligence, 328\u2013333."},{"key":"S1471068421000399_ref22","doi-asserted-by":"crossref","unstructured":"Morak, M. 2019. Epistemic logic programs: A different world view. In Proc. ICLP, 52\u201364.","DOI":"10.4204\/EPTCS.306.11"},{"key":"S1471068421000399_ref12","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068414000076"},{"key":"S1471068421000399_ref24","first-page":"1269","article-title":"On computing world views of epistemic logic programs","author":"Son","year":"2017","journal-title":"In IJCAI"},{"key":"S1471068421000399_ref17","doi-asserted-by":"crossref","unstructured":"Hecher, M. , Morak, M. and Woltran, S. 2020. Structural decompositions of epistemic logic programs. In AAAI 2020. AAAI Press, 2830\u20132837.","DOI":"10.1609\/aaai.v34i03.5672"},{"key":"S1471068421000399_ref20","doi-asserted-by":"publisher","DOI":"10.1093\/logcom\/exv065"},{"key":"S1471068421000399_ref21","doi-asserted-by":"crossref","unstructured":"Lonc, Z. and Truszczynski, M. 2003. Fixed-parameter complexity of semantics for logic programs. ACM Trans. Comput. Log. 4, 1, 91\u2013119.","DOI":"10.1145\/601775.601779"},{"key":"S1471068421000399_ref4","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1996.0049"},{"key":"S1471068421000399_ref11","doi-asserted-by":"publisher","DOI":"10.1007\/s10472-019-09633-x"},{"key":"S1471068421000399_ref16","doi-asserted-by":"publisher","DOI":"10.24963\/kr.2020\/49"},{"key":"S1471068421000399_ref8","doi-asserted-by":"publisher","DOI":"10.1007\/BF01536399"},{"key":"S1471068421000399_ref2","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068420000022"},{"key":"S1471068421000399_ref14","unstructured":"Gelfond, M. 1991. Strong introspection. In Proc. AAAI. AAAI Press\/The MIT Press, 386\u2013391."},{"key":"S1471068421000399_ref23","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2016.04.004"},{"key":"S1471068421000399_ref10","doi-asserted-by":"crossref","unstructured":"Fichte, J. K. , Hecher, M. , and Pfandler, A. 2020. Lower bounds for QBFs of bounded treewidth. In LICS. ACM, 410\u2013424.","DOI":"10.1145\/3373718.3394756"},{"key":"S1471068421000399_ref19","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-04238-6_22"},{"key":"S1471068421000399_ref3","unstructured":"Bliem, B. , Ordyniak, S. and Woltran, S. 2016. Clique-width and directed width measures for answer-set programming. In Proc. ECAI. 1105\u20131113."},{"key":"S1471068421000399_ref5","doi-asserted-by":"publisher","DOI":"10.1145\/2043174.2043195"},{"key":"S1471068421000399_ref25","doi-asserted-by":"crossref","unstructured":"Truszczynski, M. 2011. Revisiting epistemic specifications. In Logic Programming, Knowledge Representation, and Nonmonotonic Reasoning. LNCS, vol. 6565. Springer Verlag, 315\u2013333.","DOI":"10.1007\/978-3-642-20832-4_20"}],"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\/S1471068421000399","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,11,18]],"date-time":"2021-11-18T09:18:11Z","timestamp":1637227091000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S1471068421000399\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,9]]},"references-count":25,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2021,9]]}},"alternative-id":["S1471068421000399"],"URL":"https:\/\/doi.org\/10.1017\/s1471068421000399","relation":{},"ISSN":["1471-0684","1475-3081"],"issn-type":[{"value":"1471-0684","type":"print"},{"value":"1475-3081","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,9]]},"assertion":[{"value":"\u00a9 The Author(s), 2021. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}}]}}