Utilizing Treewidth for Quantitative Reasoning on Epistemic Logic Programs

Extending the popular Answer Set Programming (ASP) paradigm by introspective\nreasoning capacities has received increasing interest within the last years.\nParticular attention is given to the formalism of epistemic logic programs\n(ELPs) where standard rules are equipped with modal operators which allow to\nexpress conditions on literals for being known or possible, i.e., contained in\nall or some answer sets, respectively. ELPs thus deliver multiple collections\nof answer sets, known as world views. Employing ELPs for reasoning problems so\nfar has mainly been restricted to standard decision problems (complexity\nanalysis) and enumeration (development of systems) of world views. In this\npaper, we take a next step and contribute to epistemic logic programming in two\nways: First, we establish quantitative reasoning for ELPs, where the acceptance\nof a certain set of literals depends on the number (proportion) of world views\nthat are compatible with the set. Second, we present a novel system that is\ncapable of efficiently solving the underlying counting problems required to\nanswer such quantitative reasoning problems. Our system exploits the\ngraph-based measure treewidth and works by iteratively finding and refining\n(graph) abstractions of an ELP program. On top of these abstractions, we apply\ndynamic programming that is combined with utilizing existing search-based\nsolvers like (e)clingo for hard combinatorial subproblems that appear during\nsolving. It turns out that our approach is competitive with existing systems\nthat were introduced recently. This work is under consideration for acceptance\nin TPLP.\n

Paper

Similar papers

© 2026 NYSGPT2525 LLC