Talks and Poster Presentations (with Proceedings-Entry):
W. Dvorak, M. König, S. Woltran:
"On the Complexity of Preferred Semantics in Argumentation Frameworks with Bounded Cycle Length";
Talk: KR 2021 - 18th International Conference on Principles of Knowledge Representation and Reasoning,
virtual event;
2021-11-03
- 2021-11-12; in: "Proceedings of the 18th International Conference on Principles of Knowledge Representation and Reasoning, {KR} 2021, Online event, November 3-12, 2021",
(2021),
671
- 675.
English abstract:
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.
"Official" electronic version of the publication (accessed through its Digital Object Identifier - DOI)
http://dx.doi.org/10.24963/kr.2021/67
Related Projects:
Project Head Stefan Woltran:
HYPAR
Project Head Stefan Woltran:
START
Created from the Publication Database of the Vienna University of Technology.