KR Conference 2016 Conference Paper
A central question in knowledge representation is the following: given some knowledge representation formalism, is it possible, and if so how, to simplify parts of a knowledge base without affecting its meaning, even in the light of additional information? The term strong equivalence was coined in the literature, i. e. strongly equivalent knowledge bases can be locally replaced by each other in a bigger theory without changing the semantics of the latter. In contrast to classical (monotone) logics where standard and strong equivalence coincide, it is possible to find ordinary but not strongly equivalent objects for any nonmonotonic formalism available in the literature. This paper addresses these questions in the context of abstract argumentation theory. Much effort has been spent to characterize several argumentation tailored equivalence notions w. r. t. extension-based semantics. In recent times labelling-based semantics have received increasing attention, for example in connection with algorithms computing extensions, proof procedures, dialogue games, dynamics in argumentation as well as belief revision in general. Of course, equivalence notions allowing for replacements are of high interest for the mentioned topics. In this paper we provide kernel-based characterization theorems for semantics based on complete labellings as well as admissible labellings w. r. t. eight different equivalence notions including the aforementioned most prominent one, namely strong equivalence. Is it possible, and if so, under which conditions, to locally replace parts of a given AF, s. t. the modified version and the initial framework cannot be semantically distinguished, even in the light of additional information? For this task w. r. t. other formalisms the term strong equivalence was coined in the literature, i. e. strongly equivalent theories can be replaced by each other within a bigger theory without changing the meaning of the latter. In contrast to classical (monotone) logics where standard and strong equivalence coincide, it is possible to find ordinarily but not strongly equivalent theories for any nonmonotonic formalism available in the literature. Consequently, much effort has been devoted to characterizing strong equivalence for nonmonotonic formalisms, such as logic programs (Lifschitz, Pearce, and Valverde 2001), causal theories (Turner 2004), default logic (Turner 2001) and nonmonotonic logics in general (Truszczynski 2006; Baumann and Strass 2016). The characterization theorems in case of abstract argumentation (Oikarinen and Woltran 2011) are quite different from those for the aforementioned formalisms since being strongly equivalent can be decided syntactically in abstract argumentation. More precisely, the authors introduced the notion of a kernel of an AF F, which is (informally speaking) a subgraph of F where certain attacks are deleted, and showed that syntactical identity of suitably chosen kernels characterizes strong equivalence w. r. t. the considered semantics. Later it was pointed out that in many argumentation scenarios the potentially occurring type of modification can be anticipated and, more importantly, does not range over arbitrary expansions as required for strong equivalence (Baumann 2012; 2014a). This applies, for instance, if we use argumentation theory for the purpose of nonmonotonic entailment, so-called instantiation-based argumentation (Caminada and Amgoud 2007), where AFs are built from an underlying