Algorithms for decision problems in argument systems under preferred semantics

摘要

For Dungʼs model of abstract argumentation under preferred semantics, argumentation frameworks may have several distinct preferred extensions: i.e., in informal terms, sets of acceptable arguments. Thus the acceptance problem (for a specific argument) can consider deciding whether an argument is in at least one such extensions (credulously accepted) or in all such extensions (skeptically accepted). We start by presenting a new algorithm that enumerates all preferred extensions. Following this we build algorithms that decide the acceptance problem without requiring explicit enumeration of all extensions. We analyze the performance of our algorithms by comparing these to existing ones, and present experimental evidence that the new algorithms are more efficient with respect to the expected running time. Moreover, we extend our techniques to solve decision problems in a widely studied development of Dungʼs model: namely value-based argumentation frameworks (vafs). In this regard, we examine analogous notions to the problem of enumerating preferred extensions and present algorithms that decide subjective, respectively objective, acceptance.