The Relative Expressiveness of Abstract Argumentation and Logic Programming

Hannes StrassAAAI 2015 · DOI

Abstract

In Knowledge Representation (KR), formalisms are frequently categorized by their computational complexity. However, complexity classes often fail to distinguish between the representational capabilities of different languages. This paper establishes a formal expressiveness hierarchy among Abstract Argumentation Frameworks (AFs), Logic Programs (LPs), and Abstract Dialectical Frameworks (ADFs). By employing the concept of realizability, the research demonstrates that while these formalisms differ significantly when restricted to a fixed vocabulary, they converge toward universal expressiveness when a linear increase in auxiliary variables is permitted.

Introduction

Many popular formalisms in AI—including Dung’s argumentation frameworks, normal logic programs, and propositional logic—share the same complexity profile (typically NP-complete) for fundamental reasoning tasks. Despite this, researchers intuitively recognize that some languages are more flexible than others. This paper moves beyond complexity to examine relative expressiveness: the ability of a language to exactly represent a specific set of outcomes (models) without introducing "helper" atoms that might bloat the search space or obscure the original problem structure.

Methodology: Realizability and Compactness

The study utilizes a formal framework of realizability. A language $L_2$ is considered at least as expressive as $L_1$ if every set of models representable in $L_1$ can also be represented in $L_2$ over the same vocabulary. This is known as a "compact" translation. The author evaluates several key formalisms:

  • Abstract Argumentation Frameworks (AFs): Directed graphs where nodes represent arguments and edges represent attack relations.
  • Normal Logic Programs (LPs): Sets of rules utilizing negation-as-failure.
  • Abstract Dialectical Frameworks (ADFs): A generalization of AFs where each node is associated with a propositional acceptance condition.
  • Propositional Logic (PL): The standard benchmark for universal expressiveness.

The analysis focuses on two primary semantics: supported models (where every true atom must have a justification) and stable models (which further require that justifications are non-circular).

The Expressiveness Hierarchy

The Antichain Bottleneck

A fundamental finding of the paper concerns the inherent limitations of stable model semantics. Under stable semantics, any set of models must form an antichain—meaning no model in the set can be a proper subset of another. This property creates a natural ceiling on the expressiveness of LPs and AFs, preventing them from reaching the universal expressiveness of Propositional Logic, which has no such restriction.

Comparative Power

The research proves a distinct hierarchy of power based on the chosen semantics:

  1. Supported Semantics: The hierarchy is established as $AF <_e BADF^{su} <_e ADF^{su} \cong LP^{su} \cong PL$. Here, general ADFs and Logic Programs are shown to be "universally expressive," capable of representing any set of models over a fixed vocabulary.
  2. Stable Semantics: The hierarchy shifts to $AF <_e BADF^{st} \cong ADF^{st} \cong LP^{st} <_e PL$. Because of the antichain requirement, these formalisms can never reach the expressiveness of Propositional Logic in a compact setting.

In both cases, Bipolar ADFs (BADFs)—a subclass where links are strictly supporting or attacking—occupy a middle ground, being more expressive than AFs but less so than general ADFs.

Vocabulary Expansion and Universal Realizability

Perhaps the most significant contribution of the paper is the discovery that the expressiveness hierarchy collapses if the "compactness" constraint is relaxed. The author proves that the differences in expressiveness vanish if we allow the introduction of a linear number of new atoms.

Specifically, the paper provides a constructive method showing that for any propositional formula $\phi$, one can construct an AF $F_\phi$ such that the stable extensions of $F_\phi$ correspond exactly to the models of $\phi$. This construction requires only $9 \cdot |\phi| + 3$ additional arguments. This result explains why many polynomial-time translations between these fields exist in the literature: they effectively trade vocabulary size for representational power.

Conclusion and Future Directions

This work provides a rigorous map of the landscape of KR formalisms. While AFs are the least expressive in a compact sense, their ability to simulate any propositional formula with linear overhead highlights their underlying robustness.

The author identifies two primary areas for future research:

  1. Succinctness: While a language may be expressive enough to represent a model set, it might require an exponentially large knowledge base to do so. Measuring the size efficiency of these representations is the logical next step.
  2. Three-Valued Semantics: This study focused on two-valued interpretations (true/false). Extending this framework to three-valued semantics (true/false/undecided), which are common in argumentation, remains an open challenge.

Summary updated

BibTeX
@inproceedings{strass2015relative,
  author = {Hannes Strass},
  title = {{The Relative Expressiveness of Abstract Argumentation and Logic Programming}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2015},
  doi = {10.1609/aaai.v29i1.9392},
}
Figure