ML Anthology

On the Complexity of Enumerating the Extensions of Abstract Argumentation Frameworks

Markus Kröll, Reinhard Pichler, Stefan Woltran
IJCAI 2017 pp. 1145-1152
doi:10.24963/IJCAI.2017/159 /ijcai/2017/kroll2017ijcai-complexity/

Abstract

Several computational problems of abstract argumentation frameworks (AFs) such as skeptical and credulous reasoning, existence of a non-empty extension, verification, etc. have been thoroughly analyzed for various semantics. In contrast, the enumeration problem of AFs (i.e., the problem of computing all extensions according to some semantics) has been left unexplored so far. The goal of this paper is to fill this gap. We thus investigate the enumeration complexity of AFs for a large collection of semantics and, in addition, consider the most common structural restrictions on AFs.

PDF IJCAI Semantic Scholar

Cite

Text

Kröll et al. "On the Complexity of Enumerating the Extensions of Abstract Argumentation Frameworks." International Joint Conference on Artificial Intelligence, 2017. doi:10.24963/IJCAI.2017/159

Markdown

[Kröll et al. "On the Complexity of Enumerating the Extensions of Abstract Argumentation Frameworks." International Joint Conference on Artificial Intelligence, 2017.](https://mlanthology.org/ijcai/2017/kroll2017ijcai-complexity/) doi:10.24963/IJCAI.2017/159

BibTeX

@inproceedings{kroll2017ijcai-complexity,
  title     = {{On the Complexity of Enumerating the Extensions of Abstract Argumentation Frameworks}},
  author    = {Kröll, Markus and Pichler, Reinhard and Woltran, Stefan},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year      = {2017},
  pages     = {1145-1152},
  doi       = {10.24963/IJCAI.2017/159},
  url       = {https://mlanthology.org/ijcai/2017/kroll2017ijcai-complexity/}
}