On the Computational Complexity of Naive-Based Semantics for Abstract Dialectical Frameworks

Gaggl, Sarah Alice; Rudolph, Sebastian; Strass, Hannes

On the Computational Complexity of Naive-Based Semantics for Abstract Dialectical Frameworks

Sarah Alice Gaggl, Sebastian Rudolph, Hannes Strass

Download BibTeX Cite

Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence. Special Track on Knowledge Representation and Reasoning. Pages 2985-2990.

Abstract

Abstract dialectical frameworks (ADFs) are a powerful generalization of Dung’s abstract argumentation frameworks. ADFs allow to model argumentation scenarios such that ADF semantics then provide interpretations of the scenarios. Among the considerable number of ADF semantics, the naive-based ones are built upon the fundamental concept of conflict-freeness. Intuitively, a three-valued interpretation of an ADF’s statements is conflict-free iff all true statements can possibly be accepted, and all false statements cannot possibly be accepted. In this paper, we perform an exhaustive analysis of the computational complexity of naive-based semantics. The results are quite interesting, for some of them involve little-known classes of the so-called Boolean hierarchy (another hierarchy in between classes of the polynomial hierarchy). Furthermore in credulous and sceptical entailment, the complexity can be different depending on whether we check for truth or falsity of a specific statement.

Sarah Alice Gaggl, Sebastian Rudolph, and Hannes Strass. 2015. On the Computational Complexity of Naive-Based Semantics for Abstract Dialectical Frameworks. In Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-15. IJCAI, 2985–2990. https://ijcai.org/proceedings/2015/422

@inproceedings{ijcai2015p422,
  title     = {On the Computational Complexity of Naive-Based Semantics for Abstract Dialectical Frameworks},
  author    = {Gaggl, Sarah Alice and Rudolph, Sebastian and Strass, Hannes},
  booktitle = {Proceedings of the Twenty-Fourth International Joint Conference on
               Artificial Intelligence, {IJCAI-15}},
  publisher = {International Joint Conferences on Artificial Intelligence},
  editor    = {Qiang Yang and Michael Wooldridge},
  pages     = {2985--2990},
  year      = {2015},
  month     = {7},
  note      = {Special Track on Knowledge Representation and Reasoning},
  url       = {https://ijcai.org/proceedings/2015/422},
}

TY  - CPAPER
TI  - On the Computational Complexity of Naive-Based Semantics for Abstract Dialectical Frameworks
AU  - Gaggl, Sarah Alice
AU  - Rudolph, Sebastian
AU  - Strass, Hannes
T2  - Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-15
PB  - International Joint Conferences on Artificial Intelligence
PY  - 2015
SP  - 2985
EP  - 2990
UR  - https://ijcai.org/proceedings/2015/422
ER  -