[Back]

W. Dvorak, C. Spanring:
"Comparing the expressiveness of argumentation semantics";
Report No. DBAI-TR-2014-90, 2015; 32 pages.

Understanding the expressiveness of a formalism is undoubtedly an important part of understanding its possibilities and limitations. Translations between different formalisms have proven to be valuable tools for understanding this very expressiveness.
In this work we complement recent investigations of the intertranslatability of argumentation semantics for Dung´s abstract argumentation frameworks. As our focus is on the expressiveness of argumentation semantics we expand the area of interest beyond efficiently computable translations and also consider translations that might not (always) be efficiently computable. This allows us to provide translations between certain semantics, where under established complexity assumptions no efficiently computable translation exists. However, for some semantics we give strong translational impossibility results stating that even with arbitrary computational power we can not in all situations translate one to the other. Finally, this allows us to draw a hierarchy for the expressiveness of argumentation semantics.