Algorithms for decision problems in argument systems under preferred semantics

作者：Nofal Samer^*; Atkinson Katie; Dunne Paul E

来源：Artificial Intelligence, 2014, 207: 23-51.

DOI：10.1016/j.artint.2013.11.001

• Abstract argumentation
• Preferred extensions
• Algorithms
• Skeptical acceptance
• Credulous acceptance
• Value based argumentation
• Subjective acceptance
• Objective acceptance

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.

• 出版日期2014-2