Bipolar Abstract Dialectical Frameworks Are Covered by Kleene's Three-valued Logic

Ringo Baumann, Maximilian HeinrichIJCAI 2023 · DOI

TL;DR

This paper shows that a specific type of argumentation framework, Bipolar Abstract Dialectical Frameworks (BADFs), can be evaluated using Kleene's three-valued logic. This significantly speeds up computations by avoiding the need to consider all possible two-valued interpretations, a common bottleneck in current methods.

What Problem Does This Paper Address?

Argumentation frameworks are a powerful tool for modeling reasoning and decision-making, especially in AI systems that need to provide explanations. Classical argumentation frameworks (AFs) have limitations in expressing complex relationships between arguments. Abstract Dialectical Frameworks (ADFs) generalize AFs by allowing arguments to have acceptance conditions, which can specify complex relationships like support and attack. However, evaluating these conditions can be computationally expensive, often requiring a step up in the polynomial hierarchy.

A particularly interesting subclass is Bipolar Abstract Dialectical Frameworks (BADFs). BADFs offer more expressive power than standard AFs while maintaining a similar level of computational complexity. The semantics of ADFs rely on a "Gamma-operator" that takes a three-valued interpretation (true, false, unknown) and returns a new one. A key challenge has been that this operator traditionally requires considering all possible two-valued "completions" of a three-valued interpretation, which is computationally intensive. This paper addresses the question of whether a simpler, truth-functional three-valued logic can be used to achieve the same results for BADFs, thereby improving computational efficiency.

Methods

The core contribution of this paper is demonstrating that Kleene's three-valued logic (K3) can be used to evaluate the acceptance conditions of BADFs, bypassing the need for computationally expensive two-valued completions.

  1. Bipolar Disjunctive Normal Form (bipolar DNF): The authors introduce a new propositional formula class called bipolar DNFs. These are disjunctive normal forms where atoms have a consistent polarity (either always positive or always negative) across the entire formula. They prove that this form is expressive enough to represent semantically bipolar functions, which are the acceptance conditions in BADFs.
  2. Kleene's K3 Equivalence: The central theorem shows that for any formula in bipolar DNF, evaluating it using Kleene's K3 logic yields the same result as the traditional method of considering all two-valued completions and applying the consensus operator. This is proven via structural induction on the formula.
  3. Extension to Syntactically Bipolar Formulas: The result is then extended from bipolar DNFs to a broader class of "syntactically bipolar" formulas. These are formulas where no atom appears with both positive and negative polarity. This is achieved by showing that any syntactically bipolar formula can be transformed into an equivalent bipolar DNF.
  4. Experimental Validation: The authors implement a solver to compare the runtime of evaluating BADFs using the traditional two-valued completion method versus the Kleene's K3 approach.

Datasets

Not discussed in the paper. The experiments involved generating random BADFs with varying numbers of statements and acceptance formulas.

Key Insights and Ideas

  • Kleene's K3 as a Shortcut: The most significant insight is that Kleene's three-valued logic provides a computationally efficient way to evaluate the acceptance conditions of BADFs, directly mirroring the behavior of the more complex Gamma-operator without explicit two-valued completions.
  • Bipolar DNFs as a Bridge: The introduction of bipolar DNFs is crucial. This specific syntactic form allows for a clean, inductive proof of the equivalence between Kleene's K3 evaluation and the traditional method.
  • Syntactic Bipolarity Implies Semantic Bipolarity (for K3): The paper establishes that the property of "syntactic bipolarity" in formulas is sufficient for them to be evaluated correctly by Kleene's K3 logic in the context of BADFs. This broadens the applicability of the efficient method beyond just the strict bipolar DNF form.
  • Practical Implications for Explainable AI: By speeding up the evaluation of argumentation frameworks, this work contributes to making AI systems more efficient and thus more practical for applications requiring explainability, such as in finance or criminal justice.

Key Results

  • Theorem 2: For any formula $\phi$ in bipolar DNF and any three-valued interpretation $v$, $v_{K3}(\phi) = \Pi_{w \in [v]_2} \{w(\phi)\}$. This means Kleene's K3 evaluation of $\phi$ is equivalent to the consensus of $\phi$ over all two-valued completions of $v$.
  • Theorem 3: This equivalence is extended to all syntactically bipolar formulas.
  • Experimental Speedup: The experiments showed a significant speedup when using Kleene's K3 logic compared to the traditional method. For instance, for 10 statements, the speedup factor was around 10x for admissible, complete, and preferred semantics. Even for a small number of statements (e.g., 10), the traditional method approached a 30-minute timeout, while the Kleene-based approach was still fast.

Limitations and Future Work

  • Scalability Limits: While the Kleene-based approach is faster, both methods exhibit exponential runtime growth with the number of statements, as the number of possible three-valued interpretations grows exponentially. The experiments showed timeouts even for the Kleene method for statement numbers over 12.
  • Further Theoretical Exploration: The authors suggest that the established correspondence can be used for further theoretical investigations, such as re-evaluating complexity results for BADFs.
  • Hybrid Solvers: A promising direction is to develop hybrid solvers that can identify syntactically bipolar acceptance formulas and use the faster Kleene-based evaluation for them, while falling back to traditional methods for non-bipolar formulas.
  • Integration with Existing Tools: The authors envision integrating these findings into existing ADF solvers (like goDIAMOND, YADF, or Tweety) to improve their performance.

Summary updated

BibTeX
@inproceedings{baumann2023bipolar,
  author = {Ringo Baumann and Maximilian Heinrich},
  title = {{Bipolar Abstract Dialectical Frameworks Are Covered by Kleene's Three-valued Logic}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.24963/ijcai.2023/348},
}
Figure