Tags:Abstract argumentation, Computational complexity, Incomplete knowledge and Stability
Abstract:
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 evolving 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 classical 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 kind of SAT encoding for the stability problems with coNP-c complexity.
Stability of Extensions in Incomplete Argumentation Frameworks