Vorträge und Posterpräsentationen (mit Tagungsband-Eintrag):
J. Fichte, M. Hecher, Y. Mahmood, A. Meier:
"Decomposition-Guided Reductions for Argumentation and Treewidth";
Vortrag: IJCAI 2021 - 30th International Joint Conference on Artificial Intelligence,
Montreal, Canada;
19.08.2021
- 27.08.2021; in: "Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, {IJCAI} 2021, Virtual Event / Montreal, Canada, 19-27 August 2021",
(2021),
S. 1880
- 1886.
Kurzfassung englisch:
Argumentation is a widely applied framework for modeling and evaluating arguments and its reasoning with various applications. Popular frameworks are abstract argumentation (Dung´s framework) or logic-based argumentation (Besnard-Hunter´s framework). Their computational complexity has been studied quite in-depth. Incorporating treewidth into the complexity analysis is particularly interesting, as solvers oftentimes employ SAT-based solvers, which can solve instances of low treewidth fast. In this paper, we address whether one can design reductions from argumentation problems to SAT-problems while linearly preserving the treewidth, which results in decomposition-guided (DG) reductions. It turns out that the linear treewidth overhead caused by our DG reductions, cannot be significantly improved under reasonable assumptions. Finally, we consider logic-based argumentation and establish new upper bounds using DG reductions and lower bounds
Schlagworte:
Knowledge Representation and Reasoning: Computational Complexity of Reasoning Knowledge Representation and Reasoning: Computational Models of Argument Constraints and SAT: Constraint Satisfaction
"Offizielle" elektronische Version der Publikation (entsprechend ihrem Digital Object Identifier - DOI)
http://dx.doi.org/10.24963/ijcai.2021/259
Zugeordnete Projekte:
Projektleitung Stefan Woltran:
START
Erstellt aus der Publikationsdatenbank der Technischen Universität Wien.