Existing works on stability of incomplete argumentation frameworks (IAFs) discuss the status of an argument or a set of arguments under a given semantics during the changing of an IAF towards complete AFs. We argue that the stability of an IAF itself is worth studying, i.e., checking whether all extensions under a semantics are the same in every completion of the IAF. When an IAF becomes stable in this sense, there is no need to investigate the uncertain arguments or attacks within the IAF as in the end all its complete AFs will share the same extensions. We further present a relaxed notion called weak stability so that the same extensions are required solely within the shared arguments of every two completions rather than all arguments in the IAF. In this paper we study six common semantics of AF and show precise complexity results of checking the (weak) stability of an IAF, which turns to be more complex than checking a set of arguments whereas less complex than checking an argument. Meanwhile, we give a SAT encoding for the stability problems with coNP-c complexity.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Stability of Extensions in Incomplete Argumentation Frameworks

  • Anshu Xiong,
  • Huan Zhang,
  • Songmao Zhang

摘要

Existing works on stability of incomplete argumentation frameworks (IAFs) discuss the status of an argument or a set of arguments under a given semantics during the changing of an IAF towards complete AFs. We argue that the stability of an IAF itself is worth studying, i.e., checking whether all extensions under a semantics are the same in every completion of the IAF. When an IAF becomes stable in this sense, there is no need to investigate the uncertain arguments or attacks within the IAF as in the end all its complete AFs will share the same extensions. We further present a relaxed notion called weak stability so that the same extensions are required solely within the shared arguments of every two completions rather than all arguments in the IAF. In this paper we study six common semantics of AF and show precise complexity results of checking the (weak) stability of an IAF, which turns to be more complex than checking a set of arguments whereas less complex than checking an argument. Meanwhile, we give a SAT encoding for the stability problems with coNP-c complexity.