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

Sarah Alice GagglSarah Alice Gaggl, Sebastian RudolphSebastian Rudolph, Hannes StraßHannes Straß

ISBN: 978-1-57735-738-4
Download
Slides

Sarah Alice Gaggl, Sebastian Rudolph, Hannes Straß
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

Details
Bibtex

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 LogicComputational Logic, Logische Programmierung und ArgumentationLogic Programming and Argumentation

@inproceedings{GRS2015,
  author    = {Sarah Alice Gaggl and Sebastian Rudolph and Hannes Stra{\ss}},
  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}
}