J. Fichte,M. Hecher:

"Exploiting Treewidth for Counting Projected Answer Sets";

Talk: International Conference on Principles of Knowledge Representation and Reasoning - KR, Tempe, Arizona, USA; 2018-10-27 - 2018-10-29; in: "Principles of Knowledge Representation and Reasoning: Proceedings of the Sixteenth International Conference, {KR} 2018", AAAI Press, (2018), ISBN: 978-1-57735-803-9; 639 - 640.

Answer Set Programming (ASP) is an active research area of artificial intelligence. We consider the problem projected answer set counting (#PDA) for disjunctive propositional ASP. #PDA asks to count the number of answer sets with respect to a given set of projected atoms, where multiple answer sets that are identical when restricted to the projected atoms count as only one projected answer set. Our approach exploits small treewidth of the primal graph of the input instance. Finally, we state a hypothesis (3ETH) that one cannot solve 3-QBF in polynomial time in the instance size while being significantly better than triple exponential in the treewidth. Taking 3ETH into account, we show that one can not expect to solve #PDA significantly better than triple exponential in the treewidth.

Parameterized Algorithms;Tree Decompositions;Multi-Pass Dynamic Programming;Projected Answer Set Counting;Answer Set Programming

https://publik.tuwien.ac.at/files/publik_273301.pdf

Project Head Stefan Woltran:

START

Created from the Publication Database of the Vienna University of Technology.