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

Aus International Center for Computational Logic
Wechseln zu:Navigation, Suche

Toggle side column

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

Sarah Alice GagglSarah Alice Gaggl,  Sebastian RudolphSebastian Rudolph,  Hannes StrassHannes Strass
On the Computational Complexity of Naive-based Semantics for Abstract Dialectical Frameworks


Slides: On the Computational Complexity of Naive-based Semantics for Abstract Dialectical Frameworks

Sarah Alice Gaggl, Sebastian Rudolph, Hannes Strass
On the Computational Complexity of Naive-based Semantics for Abstract Dialectical Frameworks
In Qiang Yang and Michael Wooldridge, eds., Proceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI 2015), AAAI Press, 2985--2991, July 2015. AAAI Press
  • KurzfassungAbstract
    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.
  • Forschungsgruppe:Research Group: Computational Logic
@inproceedings{GRS2015,
  author    = {Sarah Alice Gaggl and Sebastian Rudolph and Hannes Strass},
  title     = {On the Computational Complexity of Naive-based Semantics for
               Abstract Dialectical Frameworks},
  editor    = {Qiang Yang and Michael Wooldridge},
  booktitle = {Proceedings of the 24th International Joint Conference on
               Artificial Intelligence (IJCAI 2015)},
  series    = {AAAI Press},
  publisher = {AAAI Press},
  year      = {2015},
  month     = {July},
  pages     = {2985--2991}
}