On the Decomposition of ADFs and the Complexity of Naive-based Semantics

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

Sarah Alice Gaggl, Sebastian Rudolph, Hannes Straß
On the Decomposition of ADFs and the Complexity of Naive-based Semantics
Journal of Artificial Intelligence Research, 70:1-64, January 2021

Details
Bibtex

KurzfassungAbstract
Abstract dialectical frameworks (ADFs) are a recently introduced powerful generalization of Dung's popular abstract argumentation frameworks (AFs).
Inspired by similar work for AFs, we introduce a decomposition scheme for ADFs, which proceeds along the ADF's strongly connected components. We find that, for several semantics, the decomposition-based version coincides with the original semantics, whereas for others, it gives rise to a new semantics. These new semantics allow us to deal with pertinent problems such as odd-length negative cycles in a more general setting, that for instance also encompasses logic programs. We perform an exhaustive analysis of the computational complexity of these new, so-called 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.
Weitere Informationen unter:Further Information: Link
Projekt:Project: CPEC, DeciGUT, NAVAS
Forschungsgruppe:Research Group: Computational LogicComputational Logic, Logische Programmierung und ArgumentationLogic Programming and Argumentation

@article{GRS2021,
  author  = {Sarah Alice Gaggl and Sebastian Rudolph and Hannes Stra{\ss}},
  title   = {On the Decomposition of {ADFs} and the Complexity of Naive-based
             Semantics},
  journal = {Journal of Artificial Intelligence Research},
  volume  = {70},
  year    = {2021},
  month   = {January},
  pages   = {1-64},
  doi     = {10.1613/jair.1.11348}
}