Details
| Original language | English |
|---|---|
| Title of host publication | AAAI-19, IAAI-19, EAAI-19 Proceedings |
| Pages | 2827-2834 |
| Number of pages | 8 |
| Volume | 1 |
| Publication status | Published - 23 Jul 2019 |
| Event | 33rd AAAI Conference on Artificial Intelligence, AAAI 2019, 31st Annual Conference on Innovative Applications of Artificial Intelligence, IAAI 2019 and the 9th AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2019 - Honolulu, United States Duration: 27 Jan 2019 → 1 Feb 2019 |
Publication series
| Name | Proceedings of the AAAI Conference on Artificial Intelligence |
|---|---|
| Publisher | OJS/PKP |
| Volume | 33 |
| ISSN (Print) | 2159-5399 |
| ISSN (electronic) | 2374-3468 |
Abstract
In this paper, we consider counting and projected model counting of extensions in abstract argumentation for various semantics. When asking for projected counts we are interested in counting the number of extensions of a given argumentation framework while multiple extensions that are identical when restricted to the projected arguments count as only one projected extension. We establish classical complexity results and parameterized complexity results when the problems are parameterized by treewidth of the undirected argumentation graph. To obtain upper bounds for counting projected extensions, we introduce novel algorithms that exploit small treewidth of the undirected argumentation graph of the input instance by dynamic programming (DP). Our algorithms run in time double or triple exponential in the treewidth depending on the considered semantics. Finally, we take the exponential time hypothesis (ETH) into account and establish lower bounds of bounded treewidth algorithms for counting extensions and projected extension.
ASJC Scopus subject areas
- Computer Science(all)
- Artificial Intelligence
Cite this
- Standard
- Harvard
- Apa
- Vancouver
- BibTeX
- RIS
AAAI-19, IAAI-19, EAAI-19 Proceedings. Vol. 1 2019. p. 2827-2834 (Proceedings of the AAAI Conference on Artificial Intelligence; Vol. 33).
Research output: Chapter in book/report/conference proceeding › Conference contribution › Research › peer review
}
TY - GEN
T1 - Counting complexity for reasoning in abstract argumentation
AU - Fichte, Johannes Klaus
AU - Hecher, Markus
AU - Meier, Arne
N1 - Copyright © 2019, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.
PY - 2019/7/23
Y1 - 2019/7/23
N2 - In this paper, we consider counting and projected model counting of extensions in abstract argumentation for various semantics. When asking for projected counts we are interested in counting the number of extensions of a given argumentation framework while multiple extensions that are identical when restricted to the projected arguments count as only one projected extension. We establish classical complexity results and parameterized complexity results when the problems are parameterized by treewidth of the undirected argumentation graph. To obtain upper bounds for counting projected extensions, we introduce novel algorithms that exploit small treewidth of the undirected argumentation graph of the input instance by dynamic programming (DP). Our algorithms run in time double or triple exponential in the treewidth depending on the considered semantics. Finally, we take the exponential time hypothesis (ETH) into account and establish lower bounds of bounded treewidth algorithms for counting extensions and projected extension.
AB - In this paper, we consider counting and projected model counting of extensions in abstract argumentation for various semantics. When asking for projected counts we are interested in counting the number of extensions of a given argumentation framework while multiple extensions that are identical when restricted to the projected arguments count as only one projected extension. We establish classical complexity results and parameterized complexity results when the problems are parameterized by treewidth of the undirected argumentation graph. To obtain upper bounds for counting projected extensions, we introduce novel algorithms that exploit small treewidth of the undirected argumentation graph of the input instance by dynamic programming (DP). Our algorithms run in time double or triple exponential in the treewidth depending on the considered semantics. Finally, we take the exponential time hypothesis (ETH) into account and establish lower bounds of bounded treewidth algorithms for counting extensions and projected extension.
UR - http://www.scopus.com/inward/record.url?scp=85075741804&partnerID=8YFLogxK
U2 - 10.48550/arXiv.1811.11501
DO - 10.48550/arXiv.1811.11501
M3 - Conference contribution
AN - SCOPUS:85075741804
SN - 978-157735809-1
VL - 1
T3 - Proceedings of the AAAI Conference on Artificial Intelligence
SP - 2827
EP - 2834
BT - AAAI-19, IAAI-19, EAAI-19 Proceedings
T2 - 33rd AAAI Conference on Artificial Intelligence, AAAI 2019, 31st Annual Conference on Innovative Applications of Artificial Intelligence, IAAI 2019 and the 9th AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2019
Y2 - 27 January 2019 through 1 February 2019
ER -