Utilizing Treewidth for Quantitative Reasoning on Epistemic Logic Programs (Extended Abstract)

Utilizing Treewidth for Quantitative Reasoning on Epistemic Logic Programs (Extended Abstract)

Viktor Besin, Markus Hecher, Stefan Woltran

Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence
Sister Conferences Best Papers. Pages 5264-5268. https://doi.org/10.24963/ijcai.2022/732

Extending the popular Answer Set Programming (ASP) 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, i.e., 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 deci- sion problems (complexity analysis) and enumeration (development of systems) of world views. In this paper, we first 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 capable of efficiently solving the underlying counting problems required for quantitative reasoning. Our system exploits the graph-based measure treewidth by iteratively finding (graph) abstractions of ELPs.
Keywords:
Artificial Intelligence: General