TL;DR
This paper establishes a formal equivalence between Assumption-Based Argumentation (ABA) and Logic Programming (LP). It demonstrates that ABA can be translated into LP such that their respective semantics align, and vice-versa, opening doors for applying LP's computational tools to ABA.
What Problem Does This Paper Address?
Formal argumentation systems, like Assumption-Based Argumentation (ABA), provide frameworks for reasoning with incomplete or uncertain information. ABA, in particular, uses arguments constructed from inference rules and defeasible assumptions, with semantics defined by "assumption labellings." While ABA has been shown to subsume various non-monotonic reasoning formalisms, including logic programming, the authors investigate the reverse: can ABA be captured by logic programming? This paper addresses the question of whether the expressive power of ABA is equivalent to that of logic programming, specifically focusing on flat ABA frameworks.
Methods
The core of this work is a translation between ABA frameworks and logic programs.
- ABA to LP Translation: A flat ABA framework $F = \langle L, R, A, \bar{\cdot} \rangle$ is translated into a normal logic program $P_F$. This is achieved by replacing each assumption $x$ in the ABA rules with its negated contrary, i.e.,
not x. The semantics of the resulting logic program are then shown to coincide with the semantics of the original ABA framework. - LP to ABA Translation: The authors also describe a translation from a logic program $P$ to an ABA framework $F_P$. Here, negation-as-failure (
not x) in the logic program is replaced by an assumptionnot_x. - Semantic Equivalence: The paper establishes bijective mappings,
Lab2ModandMod2Lab, between assumption labellings in ABA and 3-valued stable models in LP. These mappings preserve various semantic notions, such as preferred/regular, stable/(2-valued) stable, grounded/well-founded, and ideal semantics.
Datasets
Not discussed in the paper.
Key Insights and Ideas
- Symmetric Equivalence: The most significant insight is the demonstration of a formal, symmetric equivalence between flat ABA and normal logic programming. This means that the reasoning capabilities of these two formalisms are fundamentally the same.
- ABA as Syntactic Sugar for LP: The paper suggests that flat ABA can be viewed as a syntactic variation of LP. The difference lies primarily in how conclusions are represented: ABA uses assumptions (which correspond to negation-as-failure atoms in LP) to represent defeasible information, while LP directly uses atoms.
- Ideal Semantics Connection: The authors prove that the ideal semantics for ABA is not just inspired by, but actually coincides with, the ideal semantics for LP.
- Leveraging LP Tools for ABA: By establishing this equivalence, the work paves the way for applying efficient computational methods developed for LP semantics (like those for answer set programming) to solve problems in ABA, potentially avoiding exponential blow-ups.
Key Results
The paper establishes a formal correspondence between different types of assumption labellings in ABA and various semantics of logic programs:
- Complete Assumption Labellings $\iff$ 3-valued Stable Models
- Preferred Assumption Labellings $\iff$ Regular Models
- Stable Assumption Labellings $\iff$ (2-valued) Stable Models
- Grounded Assumption Labellings $\iff$ Well-founded Models
- Ideal Assumption Labellings $\iff$ Ideal Models
These equivalences are preserved through the Lab2Mod and Mod2Lab translation functions.
Limitations and Future Work
The authors acknowledge several limitations on the ABA framework for their translation to work:
- Flat ABA: The framework must be "flat," meaning no assumption can appear in the head of an ABA rule.
- Single Contrary: Each assumption must have exactly one contrary, not a set of contraries.
- Contrary Not an Assumption: The contrary of an assumption should not itself be an assumption.
Workarounds exist for the latter two restrictions, involving translating to an equivalent ABA framework that satisfies these conditions before proceeding.
Future work suggested includes:
- Applying LP Computation Methods: Utilizing efficient LP computation methods to determine ABA semantics.
- Handling Non-Flat ABA: Extending the translation to non-flat ABA frameworks.
- Investigating Other Semantics: Further exploring the relationship between ABA and LP semantics, particularly semi-stable labellings and L-stable models, which showed a direct equivalence when the ABA framework is "assumption-spanning."
Summary updated