Details
| Original language | English |
|---|---|
| Title of host publication | Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI 2021, Virtual Event / Montreal, Canada, 19-27 August 2021. |
| Editors | Zhi-Hua Zhou |
| Pages | 1880-1886 |
| Number of pages | 7 |
| ISBN (electronic) | 9780999241196 |
| Publication status | Published - 2021 |
| Event | Thirty-Fifth AAAI Conference on Artificial Intelligence - online Duration: 2 Feb 2021 → 9 Feb 2021 |
Publication series
| 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 subject areas
- Computer Science(all)
- Artificial Intelligence
Cite this
- 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.. ed. / Zhi-Hua Zhou. 2021. p. 1880-1886 (IJCAI International Joint Conference on Artificial Intelligence).
Research output: Chapter in book/report/conference proceeding › Conference contribution › Research › 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 -