On the Computational Complexity of Naive-based Semantics for Abstract Dialectical Frameworks
From International Center for Computational Logic
On the Computational Complexity of Naive-based Semantics for Abstract Dialectical Frameworks
Sarah Alice GagglSarah Alice Gaggl, Sebastian RudolphSebastian Rudolph, Hannes StraßHannes Straß
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
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 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}
}