[Zurück]


Vorträge und Posterpräsentationen (mit Tagungsband-Eintrag):

W. Dvorak, M. König, S. Woltran:
"On the Complexity of Preferred Semantics in Argumentation Frameworks with Bounded Cycle Length";
Vortrag: KR 2021 - 18th International Conference on Principles of Knowledge Representation and Reasoning, virtual event; 03.11.2021 - 12.11.2021; in: "Proceedings of the 18th International Conference on Principles of Knowledge Representation and Reasoning, {KR} 2021, Online event, November 3-12, 2021", (2021), S. 671 - 675.



Kurzfassung englisch:
Argumentation frameworks are a core formalism in the field of formal argumentation, with several semantics being proposed in the literature. Among them, preferred semantics is one of the most popular but comes with relatively high complexity. In fact, deciding whether an argument is skeptically accepted, i.e. contained in each preferred extension, is Pi^P_2-complete. In this work we study the complexity of this problem w.r.t. the length of the cycles in the considered AF.
Our results show which bounds are necessary to decrease the complexity to coNP and P, respectively. We also consider argumentation frameworks with collective attacks and achieve Pi^P_2-hardness already for cycles of length 4.


"Offizielle" elektronische Version der Publikation (entsprechend ihrem Digital Object Identifier - DOI)
http://dx.doi.org/10.24963/kr.2021/67



Zugeordnete Projekte:
Projektleitung Stefan Woltran:
HYPAR

Projektleitung Stefan Woltran:
START


Erstellt aus der Publikationsdatenbank der Technischen Universität Wien.