Details
| Originalsprache | Englisch |
|---|---|
| Titel des Sammelwerks | Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI 2021, Virtual Event / Montreal, Canada, 19-27 August 2021. |
| Herausgeber/-innen | Zhi-Hua Zhou |
| Seiten | 1880-1886 |
| Seitenumfang | 7 |
| ISBN (elektronisch) | 9780999241196 |
| Publikationsstatus | Veröffentlicht - 2021 |
| Veranstaltung | Thirty-Fifth AAAI Conference on Artificial Intelligence - online Dauer: 2 Feb. 2021 → 9 Feb. 2021 |
Publikationsreihe
| Name | IJCAI International Joint Conference on Artificial Intelligence |
|---|---|
| ISSN (Print) | 1045-0823 |
Abstract
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.
ASJC Scopus Sachgebiete
- Informatik (insg.)
- Artificial intelligence
Zitieren
- Standard
- Harvard
- Apa
- Vancouver
- BibTex
- RIS
Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI 2021, Virtual Event / Montreal, Canada, 19-27 August 2021.. Hrsg. / Zhi-Hua Zhou. 2021. S. 1880-1886 (IJCAI International Joint Conference on Artificial Intelligence).
Publikation: Beitrag in Buch/Bericht/Sammelwerk/Konferenzband › Aufsatz in Konferenzband › Forschung › Peer-Review
}
TY - GEN
T1 - Decomposition-Guided Reductions for Argumentation and Treewidth
AU - Fichte, Johannes Klaus
AU - Hecher, Markus
AU - Mahmood, Yasir
AU - Meier, Arne
N1 - Funding Information: ∗The work is supported by Austrian Science Fund (FWF), Grants Y698 and P32830, the Vienna Science and Technology Fund, Grant WWTF ICT19-065, and the DFG (ME4279/1-2) under 247444366.
PY - 2021
Y1 - 2021
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85125493639&partnerID=8YFLogxK
U2 - 10.24963/ijcai.2021/259
DO - 10.24963/ijcai.2021/259
M3 - Conference contribution
T3 - IJCAI International Joint Conference on Artificial Intelligence
SP - 1880
EP - 1886
BT - Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI 2021, Virtual Event / Montreal, Canada, 19-27 August 2021.
A2 - Zhou, Zhi-Hua
T2 - Thirty-Fifth AAAI Conference on Artificial Intelligence
Y2 - 2 February 2021 through 9 February 2021
ER -