On the Relative Expressiveness of Argumentation Frameworks, Normal Logic Programs and Abstract Dialectical Frameworks

2014/05/05 by Strass, Hannes
#Artificial Intelligence (cs.AI) #FOS: Computer and information sciences #Logic in Computer Science (cs.LO)

paper · doi:10.48550/arxiv.1405.0805

Abstract

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.

Related

• Expressiveness of Logic Programs under General Stable Model Semantics
• Disjunctive Logic Programs versus Normal Logic Programs
• On the Equivalence Between Abstract Dialectical Frameworks and Logic Programs
• Translations: generalizing relative expressiveness between logics
• On the Semantics of Abstract Argumentation Frameworks: A Logic Programming Approach