Vorträge und Posterpräsentationen (mit Tagungsband-Eintrag):
J. Fichte, M. Hecher:
"Exploiting Treewidth for Counting Projected Answer Sets";
Vortrag: International Conference on Principles of Knowledge Representation and Reasoning - KR,
Tempe, Arizona, USA;
27.10.2018
- 29.10.2018; in: "Principles of Knowledge Representation and Reasoning: Proceedings of the Sixteenth International Conference, {KR} 2018",
AAAI Press,
(2018),
ISBN: 978-1-57735-803-9;
S. 639
- 640.
Kurzfassung englisch:
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.
Schlagworte:
Parameterized Algorithms;Tree Decompositions;Multi-Pass Dynamic Programming;Projected Answer Set Counting;Answer Set Programming
Elektronische Version der Publikation:
https://publik.tuwien.ac.at/files/publik_273301.pdf
Zugeordnete Projekte:
Projektleitung Stefan Woltran:
START
Erstellt aus der Publikationsdatenbank der Technischen Universität Wien.