On the Relative Expressiveness of Argumentation Frameworks, Normal Logic Programs and Abstract Dialectical Frameworks
This work addresses a foundational problem in formal AI and logic, providing clarity on the relative capabilities of these frameworks for researchers in computational argumentation and knowledge representation.
The paper analyzed the expressiveness of two-valued semantics in abstract argumentation frameworks, normal logic programs, and abstract dialectical frameworks, showing they form a neat hierarchy based on their ability to encode desired interpretations, despite similar computational complexity.
We analyse the expressiveness of the two-valued semantics of abstract argumentation frameworks, normal logic programs and abstract dialectical frameworks. By expressiveness we mean the ability to encode a desired set of two-valued interpretations over a given propositional signature using only atoms from that signature. While the computational complexity of the two-valued model existence problem for all these languages is (almost) the same, we show that the languages form a neat hierarchy with respect to their expressiveness.