Loading [MathJax]/extensions/tex2jax.js

Counting complexity for reasoning in abstract argumentation

Publikation: Beitrag in Buch/Bericht/Sammelwerk/KonferenzbandAufsatz in KonferenzbandForschungPeer-Review

Autorschaft

Externe Organisationen

  • Technische Universität Dresden (TUD)
  • Technische Universität Wien (TUW)
  • Universität Potsdam

Details

OriginalspracheEnglisch
Titel des SammelwerksAAAI-19, IAAI-19, EAAI-19 Proceedings
Seiten2827-2834
Seitenumfang8
Band1
PublikationsstatusVeröffentlicht - 23 Juli 2019
Veranstaltung33rd 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, USA / Vereinigte Staaten
Dauer: 27 Jan. 20191 Feb. 2019

Publikationsreihe

NameProceedings of the AAAI Conference on Artificial Intelligence
Herausgeber (Verlag)OJS/PKP
Band33
ISSN (Print)2159-5399
ISSN (elektronisch)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 Sachgebiete

Zitieren

Counting complexity for reasoning in abstract argumentation. / Fichte, Johannes Klaus; Hecher, Markus; Meier, Arne.
AAAI-19, IAAI-19, EAAI-19 Proceedings. Band 1 2019. S. 2827-2834 (Proceedings of the AAAI Conference on Artificial Intelligence; Band 33).

Publikation: Beitrag in Buch/Bericht/Sammelwerk/KonferenzbandAufsatz in KonferenzbandForschungPeer-Review

Fichte, JK, Hecher, M & Meier, A 2019, Counting complexity for reasoning in abstract argumentation. in AAAI-19, IAAI-19, EAAI-19 Proceedings. Bd. 1, Proceedings of the AAAI Conference on Artificial Intelligence, Bd. 33, S. 2827-2834, 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, USA / Vereinigte Staaten, 27 Jan. 2019. https://doi.org/10.48550/arXiv.1811.11501, https://doi.org/10.1609/aaai.v33i01.33012827
Fichte, J. K., Hecher, M., & Meier, A. (2019). Counting complexity for reasoning in abstract argumentation. In AAAI-19, IAAI-19, EAAI-19 Proceedings (Band 1, S. 2827-2834). (Proceedings of the AAAI Conference on Artificial Intelligence; Band 33). https://doi.org/10.48550/arXiv.1811.11501, https://doi.org/10.1609/aaai.v33i01.33012827
Fichte JK, Hecher M, Meier A. Counting complexity for reasoning in abstract argumentation. in AAAI-19, IAAI-19, EAAI-19 Proceedings. Band 1. 2019. S. 2827-2834. (Proceedings of the AAAI Conference on Artificial Intelligence). doi: 10.48550/arXiv.1811.11501, 10.1609/aaai.v33i01.33012827
Fichte, Johannes Klaus ; Hecher, Markus ; Meier, Arne. / Counting complexity for reasoning in abstract argumentation. AAAI-19, IAAI-19, EAAI-19 Proceedings. Band 1 2019. S. 2827-2834 (Proceedings of the AAAI Conference on Artificial Intelligence).
Download
@inproceedings{2c9087594e9f4309b6963371fc62813d,
title = "Counting complexity for reasoning in abstract argumentation",
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.",
author = "Fichte, {Johannes Klaus} and Markus Hecher and Arne Meier",
note = "Copyright {\textcopyright} 2019, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.; 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 ; Conference date: 27-01-2019 Through 01-02-2019",
year = "2019",
month = jul,
day = "23",
doi = "10.48550/arXiv.1811.11501",
language = "English",
isbn = "978-157735809-1",
volume = "1",
series = "Proceedings of the AAAI Conference on Artificial Intelligence",
publisher = "OJS/PKP",
pages = "2827--2834",
booktitle = "AAAI-19, IAAI-19, EAAI-19 Proceedings",

}

Download

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 -

Von denselben Autoren