Stable Model Semantics of Abstract Dialectical Frameworks Revisited: A Logic Programming Perspective

Mario Alviano, Wolfgang FaberIJCAI 2015

Introduction

In the field of Knowledge Representation and Reasoning (KR), two powerful formalisms have emerged to model complex logical dependencies: Abstract Dialectical Frameworks (ADFs) and Logic Programming (LP). ADFs are primarily used in formal argumentation to determine the acceptance of arguments based on flexible "acceptance conditions," while Logic Programming uses rule-based systems to derive truths.

Despite their different origins, both fields independently developed the concept of "stable model semantics" to identify consistent, grounded sets of truths or accepted arguments. However, the parallel development of these definitions led to a fragmented landscape where the relationships between ADF stable models and LP stable models remained unclear. This paper provides a "Rosetta Stone" for these domains, introducing a unifying framework that proves several independently developed definitions are mathematically equivalent.

The Definitorial Bridge: DLPBFs

The authors bridge the gap between argumentation and logic by introducing Definitorial Logic Programs with Boolean Functions (DLPBFs). In this framework, every propositional atom is defined by exactly one rule, creating a structured environment where different semantics can be compared directly.

To analyze these programs, the authors utilize two primary logical tools:

  1. Program Reducts: A method of simplifying a complex program based on a "candidate" model. The research identifies four specific ways to reduce Boolean functions: keep_all, keep_subsets, keep_equal, and keep_supsets.
  2. Immediate Consequence Operator: A standard tool used to determine what can be derived from these simplified (reduced) programs.

By mapping ADFs and various types of Logic Programs into this definitorial format, the authors were able to compare the underlying reducts used by different researchers across the two fields.

Key Insights and Equivalences

The core contribution of this work is the formal proof of equivalences between previously disconnected semantics. The paper establishes several critical links:

  • ADF and LP Convergence: The authors prove that the ADF stable models proposed by Brewka et al. are mathematically equivalent to the LPBF stable models proposed by Pelov, Son, and Pontelli. Similarly, the ADF models defined by Strass match the LPBF models proposed by Gelfond and Zhang.
  • A Hierarchy of Strictness: The research establishes a clear relationship between semantics. For instance, the paper demonstrates that every "G-stable" model (Gelfond and Zhang) is also a "P-stable" model (Son and Pontelli), though the reverse is not necessarily true.
  • F-Stable Models and Circularity: The authors introduce "F-stable" models (based on the work of Faber and Ferraris) to the ADF domain. These models are shown to be less restrictive, allowing for certain types of dynamic reasoning—such as those found in the "Lazy Programmers" benchmark—that other semantics might reject as being "circularly justified."

Practical Implications and Tooling

These theoretical equivalences have significant practical benefits for the AI community. By proving that ADFs and Logic Programs share the same underlying structures, the authors demonstrate that existing high-performance Answer Set Programming (ASP) solvers, such as clasp and DLV, can be utilized to solve ADF problems with minimal translation.

Furthermore, the paper allows for the transfer of complexity results. Since the computational complexity of logic programs is well-documented (often NP-complete or higher), these results now apply directly to the corresponding ADF semantics. To facilitate this cross-pollination, the authors provided a tool that enables modern ASP solvers to compute Strass’s stable models for ADFs.

Conclusion

This work resolves a long-standing ambiguity in the KR community by unifying the stable model semantics of ADFs and Logic Programming. While the authors acknowledge that the process of "compiling" general programs into a definitorial format can introduce auxiliary atoms that may impact performance on very large scales, the theoretical clarity provided is invaluable.

The paper highlights a remaining philosophical divide regarding "circular justifications." Whether a semantics should allow or forbid such justifications remains dependent on the specific application. However, by providing a unified view, this research opens the door for future cross-disciplinary breakthroughs and the continued development of robust reasoning tools.

Summary updated

BibTeX
@inproceedings{alviano2015stable,
  author = {Mario Alviano and Wolfgang Faber},
  title = {{Stable Model Semantics of Abstract Dialectical Frameworks Revisited: A Logic Programming Perspective}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}
Figure