[Back]

M. Hecher, M. Morak, S. Woltran:
"Structural Decompositions of Epistemic Logic Programs";
Talk: TAASP - Workshop on Trends and Applications of Answer Set Programming, Wien; 2019-11-18 - 2019-11-19; in: "TAASP 2019", (2019), 1 - 15.

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 rst 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.