Comparing the expressiveness of argumentation semantics

摘要

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 are not only interested in efficiently computable translations but 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 cannot in all situations translate one to the other. Finally, this allows us to draw a hierarchy for the expressiveness of argumentation semantics.