Talks and Poster Presentations (with Proceedings-Entry):
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.
English abstract:
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.
Keywords:
Parameterized Algorithms;Tree Decompositions;Multi-Pass Dynamic Programming;Projected Answer Set Counting;Answer Set Programming
Electronic version of the publication:
https://publik.tuwien.ac.at/files/publik_273301.pdf
Related Projects:
Project Head Stefan Woltran:
START
Created from the Publication Database of the Vienna University of Technology.