Strong Equivalence in Argumentation

Abstract

The problem of equivalence has received substantial attention in the knowledge-representation (KR) community in the past several years. This is due to the fact that the replacement theorem from classical logic does not necessarily hold in typical (non-monotonic) KR formalisms. In fact, the problem is as follows: Consider a theory S is replaced by another theory S′ within a larger knowledge base T. Naturally, one wants to ensure that the resulting knowledge base (T ∖ S) ∪ S′ has the same meaning as T. But this is not guaranteed by standard equivalence between S and S′ under nonmonotonic semantics, and therefore, stronger notions of equivalence are required. In particular, the following definition of equivalence guarantees that a replacement as discussed above is faithful: two theories S and S′ are called strongly equivalent, if and only if S ∪ T and S′ ∪ T have the same same meaning for each theory T.

In this, talk we first give a brief overview of seminal results on strong equivalence from the areas of datalog and answer-set programming. Then, we focus on argumentation and present recent characterisations for strong equivalence between argumentation frameworks with respect to the most important semantics proposed for such frameworks. We also discuss some variants of strong equivalence, which are defined in terms of acceptance. Since argumentation is an inherently dynamic process, it is of great importance to understand the effect of incorporating new information into given argumentation frameworks. By its definition, strong equivalence gives some fundamental insight into this issue.

This work is supported by the Vienna Science and Technology Fund (WWTF) under grant ICT08-028.