# Structural Decompositions of Epistemic Logic Programs

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Jan 2020.

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

- [Treewidth-aware Reductions of Normal ASP to SAT -- Is Normal ASP Harder than SAT after All?](https://mlsanity.com/paper/2210.03553/) (2022)
- [Thirty years of Epistemic Specifications](https://mlsanity.com/paper/2108.07669/) (2021)
- [Utilizing Treewidth for Quantitative Reasoning on Epistemic Logic Programs](https://mlsanity.com/paper/2108.03022/) (2021)
- [Solving Projected Model Counting by Utilizing Treewidth and its Limits](https://mlsanity.com/paper/2305.19212/) (2023)
- [Epistemic Logic Programs: Non-Ground and Counting Complexity](https://mlsanity.com/paper/2503.04731/) (2025)

## Abstract (arXiv)

Epistemic logic programs (ELPs) are a popular generalization of standard Answer Set Programming (ASP) providing means for reasoning over answer sets within the language. This richer formalism comes at the price of higher computational complexity reaching up to the fourth level of the polynomial hierarchy. However, in contrast to standard ASP, dedicated investigations towards tractability have not been undertaken yet. In this paper, we give first results in this direction and show that central ELP problems can be solved in linear time for ELPs exhibiting structural properties in terms of bounded treewidth. We also provide a full dynamic programming algorithm that adheres to these bounds. Finally, we show that applying treewidth to a novel dependency structure---given in terms of epistemic literals---allows to bound the number of ASP solver calls in typical ELP solving procedures.