Abstract Dialectical Frameworks
Origin. Brewka, Woltran (2010). Generalized argumentation. Acceptance conditions. Beyond attack. Flexible argumentative structure.
Models. Arguments with conditions. Generalized links. Acceptance functions. Boolean conditions.
Formalism.
ADF: D = ⟨S, L, C⟩ where: S: statements (arguments). L ⊆ S × S: links. C = {Cₛ}_{s∈S}: acceptance conditions.
Acceptance condition: Cₛ: 2^{par(s)} → {in, out}. par(s) = {r : (r,s) ∈ L}: parents. Boolean function. When s accepted.
Link types (derived): (r,s) supporting if Cₛ monotone increasing in r. (r,s) attacking if Cₛ monotone decreasing in r. Can be both/neither. Generalized.
Interpretation: v: S → {t, f, u}. Three-valued. t: true/in. f: false/out. u: undecided.
Operator: Γ_D(v)(s) based on Cₛ and v of parents. t if Cₛ true for all completions of v. f if Cₛ false for all completions. u otherwise.
Semantics: Admissible: v ≤_i Γ_D(v). Complete: v = Γ_D(v). Grounded: least fixpoint. Preferred, stable: adapted.
Relation to Dung: Dung AFs: special case. Cₛ = ¬r₁ ∧ ... ∧ ¬rₙ. Only attacks. ADFs generalize.
Bipolar ADFs: Links only support or attack. No mixed links. Common subclass.
Symbols.
| Symbol | Unicode | Name | Meaning |
|---|---|---|---|
| ⟨ | U+27E8 | Mathematical left angle bracket | Opens the framework triple |
| ⟩ | U+27E9 | Mathematical right angle bracket | Closes the framework triple |
| ⊆ | U+2286 | Subset | Links lie inside S × S |
| × | U+00D7 | Multiplication sign / Cartesian product | Links are ordered pairs of statements |
| ∈ | U+2208 | Membership | Statement in S, or link in L |
| ₛ | U+209B | Latin subscript small letter s | Indexes an acceptance condition to its statement |
| ₁ | U+2081 | Subscript one | Index on the first parent |
| ₙ | U+2099 | Latin subscript small letter n | Index on the last parent |
| → | U+2192 | Rightwards arrow / Function | Type of an acceptance condition or an interpretation |
| Γ | U+0393 | Greek capital gamma / Characteristic operator | Revises an interpretation from the acceptance conditions |
| ≤ | U+2264 | Less-than or equal to / Information order | v ≤_i w : w decides at least as much as v |
| ¬ | U+00AC | Negation | Attack, written into an acceptance condition |
| ∧ | U+2227 | Conjunction | Joins the conjuncts of an acceptance condition |
| 2 | U+0032 | Digit two / Power set | 2^{par(s)} is the set of subsets of the parents |
| t | U+0074 | Latin small letter t / True | Statement accepted |
| f | U+0066 | Latin small letter f / False | Statement rejected |
| u | U+0075 | Latin small letter u / Undecided | Statement given neither value |
| S | — | Statements | Nodes of the framework |
| L | — | Links | Dependencies between statements |
| C | — | Acceptance conditions | One Boolean condition per statement |
| Cₛ | — | Acceptance condition | When s is accepted, as a function of its parents |
| par(s) | — | Parents | Statements that s depends on |
| v | — | Interpretation | Three-valued assignment to statements |
| D | — | Framework | The triple ⟨S, L, C⟩ |
| in | — | Value | Acceptance condition satisfied |
| out | — | Value | Acceptance condition not satisfied |
| ADF | — | Abstract dialectical framework | The formalism as a whole |
Metatheory. Brewka and Woltran (2010) introduced ADFs and Brewka, Ellmauthaler, Strass, Wallner and Woltran (2013) revised the semantics, defining Γ_D by consensus over the two-valued completions of a three-valued interpretation. That operator is monotone with respect to the information ordering, so by Knaster–Tarski it has a least fixpoint — the grounded interpretation — while complete interpretations are its fixpoints and preferred ones the maximally informative among them, mirroring Dung exactly. Dung frameworks are the instance in which every acceptance condition is a conjunction of negated parents, and the ADF semantics restrict to Dung's on that class. The generality raises the complexity. Strass (2013) placed the semantics inside approximation fixpoint theory and gave translations showing ADFs, normal logic programs and default logic to be mutually expressible, and Strass and Wallner (2015) showed that acceptance sits one level higher in the polynomial hierarchy than for Dung frameworks — credulous acceptance Σ₂ᵖ-complete, skeptical acceptance under preferred semantics Π₃ᵖ-complete — because evaluating an acceptance condition is itself a hard step. Restricting to bipolar ADFs returns the complexity to the Dung levels.
Applies to. Argumentation. Non-monotonic reasoning. Flexible dependencies. Mixed support/attack.
Limitations. An ADF is only as compact as its acceptance conditions: a statement with n parents carries a condition over n variables, so the framework can be exponentially larger than the graph it is drawn on. Because evaluating a condition is an NP-hard step in its own right, the general acceptance problems sit a level higher in the polynomial hierarchy than the Dung problems they generalize, and the polynomial grounded semantics of Dung frameworks has no polynomial counterpart here. Link types are derived from the conditions rather than declared, so whether a link supports or attacks can depend on the rest of the condition, and a link may be neither; the bipolar restriction that recovers the Dung complexity is a restriction on admissible conditions, not a property of the graph. Statements are Boolean, leaving degrees, weights and preferences outside the ontology, and as with Dung frameworks the structure is static.
© 2026 Lingenic LLC