Abstract
Abstract Dialectical Frameworks (ADFs) generalize argumentation frameworks by allowing arbitrary acceptance conditions for arguments. A fundamental question regarding their expressive power is the realizability problem: given a set of three-valued interpretations, does there exist an ADF that has exactly these interpretations as its models under a given semantics? This paper provides the first necessary and sufficient conditions for the realizability of sets of interpretations under admissible, complete, grounded, and preferred semantics. We present constructive proofs and analyze the computational complexity of the associated decision problems, identifying significant differences in expressiveness between semantics.
Introduction
In formal argumentation, Abstract Dialectical Frameworks (ADFs) provide a flexible way to model complex debates where arguments can have sophisticated relationships beyond simple attacks. The "semantics" of these frameworks define which sets of arguments are reasonable to accept together. However, the limits of what an ADF can express remained largely unknown. This paper addresses the realizability problem: determining if a specific set of desired outcomes (interpretations) can be produced by a formal ADF structure. By solving this, we can understand the "signature" of different reasoning styles and determine the relative expressivity of various formalisms.
Methods
The research employs a theoretical and constructive methodology to define the boundaries of ADF expressiveness.
Information Ordering and Approximation Lattices
Central to the analysis is the concept of the "approximation lattice." Interpretations are ordered by their information content, ranging from the completely undefined state ($v_{\mathbf{u}}$) to fully determined states (True or False). This lattice structure is essential for defining the closure properties required for different semantics.
Canonical Constructions and Complexity
The author develops a "recipe" for building ADFs: if a target set of interpretations satisfies the identified necessary conditions, a canonical acceptance formula can be synthesized to realize that set. For complete semantics, the author introduces a "com-characterization" function to map relationships between interpretations. The decision problem for realizability under complete semantics is proven to be in NEXPTIME, suggesting it is computationally harder than other semantics.
Key Results
The paper provides definitive characterizations for four major semantics:
- Admissible Semantics: A set $V$ is realizable if and only if it is "adm-closed" (Theorem 1). This means if the set contains certain viewpoints, it must also contain the intermediate, less-defined viewpoints that lead to them in the information lattice.
- Preferred Semantics: Realizability requires the set to be non-empty, incomparable (no viewpoint is a more-defined version of another), and satisfy a specific closure property (Theorem 6).
- Grounded Semantics: The results reinforce that grounded semantics are uniquely restrictive; an ADF can have exactly one grounded interpretation, representing the "skeptical" consensus.
- The Join Operator Paradox: A practical finding involves merging ADFs. While the common ground (intersection) of two admissible frameworks can always be represented by a new ADF, this is impossible for complete semantics. Merging two complete frameworks might result in a set of viewpoints that no single ADF can legally produce.
Conclusion and Future Work
This work establishes the fundamental limits of what ADFs can express under standard semantics. The combinatorial analysis highlights a significant "cardinality gap": out of millions of possible interpretation sets for small systems, only a tiny fraction are actually realizable. Future research into "weak realizability"—which allows for auxiliary "hidden" arguments—and the study of restricted subclasses like Bipolar ADFs will be crucial for applying these theoretical insights to practical AI systems.
Summary updated