# Utilizing Treewidth for Quantitative Reasoning on Epistemic Logic Programs

arXiv: https://arxiv.org/abs/2108.03022 · HTML: https://mlsanity.com/paper/2108.03022/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 45 references that are in the map.
- First posted on arXiv 6 Aug 2021.

## Builds on (most cited first, 11 of 11)

- [The Model Counting Competition 2020](https://mlsanity.com/paper/2012.01323/) (2020)
- [selp: A Single-Shot Epistemic Logic Program Solver](https://mlsanity.com/paper/2001.01089/) (2020)
- [Omission-based Abstraction for Answer Set Programs](https://mlsanity.com/paper/2004.01410/) (2020)
- [eclingo: A solver for Epistemic Logic Programs](https://mlsanity.com/paper/2008.02018/) (2020)
- [Lower Bounds for QBFs of Bounded Treewidth](https://mlsanity.com/paper/1910.01047/) (2019)
- [Treewidth-Aware Complexity in ASP: Not all Positive Cycles are Equally Hard](https://mlsanity.com/paper/2007.04620/) (2020)
- [Structural Decompositions of Epistemic Logic Programs](https://mlsanity.com/paper/2001.04219/) (2020)
- [Splitting Epistemic Logic Programs](https://mlsanity.com/paper/1812.08763/) (2018)
- [Clique-Width and Directed Width Measures for Answer-Set Programming](https://mlsanity.com/paper/1606.09449/) (2016)
- [Combining Treewidth and Backdoors for CSP](https://mlsanity.com/paper/1610.03298/) (2016)
- [Epistemic Logic Programs: A Different World View](https://mlsanity.com/paper/1909.08233/) (2019)

## Built on by (most cited first, 3 of 3)

- [Treewidth-aware Reductions of Normal ASP to SAT -- Is Normal ASP Harder than SAT after All?](https://mlsanity.com/paper/2210.03553/) (2022)
- [IASCAR: Incremental Answer Set Counting by Anytime Refinement](https://mlsanity.com/paper/2311.07233/) (2023)
- [Epistemic Logic Programs: Non-Ground and Counting Complexity](https://mlsanity.com/paper/2503.04731/) (2025)

## Abstract (arXiv)

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 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. This work is under consideration for acceptance in TPLP.