[Back]

M. Hecher, M. Morak, S. Woltran:
"Structural Decompositions of Epistemic Logic Programs";
Talk: 34th AAAI Conference on Artificial Intelligence (AAAI-20), New York, New York, USA; 2020-02-07 - 2020-02-12; in: "The Thirty-Fourth {AAAI} Conference on Artificial Intelligence, {AAAI} 2020, The Thirty-Second Innovative Applications of Artificial Intelligence Conference, {IAAI} 2020, The Tenth {AAAI} Symposium on Educational Advances in Artificial Intelligence, {EAAI} 2020, New York, NY, USA, February 7-12, 2020", (2020), 2830 - 2837.

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.

Project Head Stefan Woltran:
HYPAR

Project Head Stefan Woltran:
START