[Back]

M. Hecher, M. Morak, S. Woltran:
"Structural Decompositions of Epistemic Logic Programs";
Talk: ICLP 2020, Rende, Italien; 2020-09-18 - 2020-09-24; in: "International Conference on Logic Programming 2020 Workshop Proceedings co-located with 36th International Conference on Logic Programming {(ICLP} 2020), Rende, Italy, September 18-19, 2020", CEUR-WS.org, (2020), 1 - 13.

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 ofhigher computational complexity reaching up to the fourth level of the polynomial hierarchy. However, in contrastto standard ASP, dedicated investigations towards tractability have not been undertaken yet. In this paper, we givefirst results in this direction and show that central ELP problems can be solved in linear time for ELPs exhibitingstructural properties in terms of bounded treewidth. We also provide a full dynamic programming algorithm thatadheres to these bounds. Finally, we show that applying treewidth to a novel dependency structure-given in termsof epistemic literals-allows to bound the number of ASP solver calls in typical ELP solving procedures.

Project Head Stefan Woltran:
START