Introduction
Assumption-Based Argumentation (ABA) is a prominent framework in the field of Artificial Intelligence for modeling defeasible reasoning. In its standard "flat" form, ABA distinguishes strictly between assumptions—which can be retracted—and rules, which define how conclusions are drawn. However, real-world reasoning often requires a more expressive "non-flat" structure where rules can conclude assumptions themselves. While more powerful, non-flat ABA has historically been plagued by theoretical inconsistencies and computational inefficiencies. This paper presents a novel six-valued labeling semantics that resolves these issues, restoring the fundamental properties of existence and uniqueness while maintaining computational tractability.
The Problem: Why Non-Flat ABA is Challenging
In a flat ABA framework, assumptions are never the heads (conclusions) of rules. This restriction ensures that the framework behaves similarly to Dung’s abstract argumentation frameworks, allowing for well-defined semantics like grounded, preferred, and complete extensions.
When this restriction is lifted to create non-flat ABA, three major problems emerge:
- Non-existence of Extensions: Some frameworks fail to produce any "complete" set of acceptable arguments, leaving the reasoner with no valid conclusions.
- Non-uniqueness of Grounded Extensions: The grounded extension, intended to represent the set of "skeptically" accepted arguments, may not be unique, leading to ambiguity.
- Computational Complexity Explosion: Tasks that are solvable in polynomial time in flat ABA often jump to higher complexity classes (like coNP or $\Pi^P_2$-complete) in the non-flat case, making them impractical for large-scale applications.
The root of these problems lies in the traditional three-valued labeling system (in, out, undecided). This system is too coarse to distinguish between different types of uncertainty. For instance, an assumption might be "undecided" because of a lack of information, or because it is part of a logical contradiction within the rule set.
Methods: The SIX Labeling System
To address these shortcomings, the authors propose a "fine-grained" labeling system based on an algebraic structure called a bilattice. Instead of three values, they utilize six distinct labels derived from an underlying 8-valued structure called EIGHT.
The core innovation is decomposing the status of an assumption into three binary components:
- Inferred ($i$): Is the assumption derivable via the rules?
- Defended ($d$): Are all its attackers themselves attacked by accepted assumptions?
- Unrejected ($u$): Is the assumption currently free from successful attacks?
By combining these components into triples $(i, d, u)$, the authors define the SIX labeling system:
- in (1, 1, 1): Inferred, defended, and unrejected.
- out (0, 0, 0): Not inferred, not defended, and rejected.
- undec (0, 0, 1): Not inferred, not defended, but unrejected (standard uncertainty).
- dis (1, 0, 1): Dissonant—inferred and unrejected, but not defended.
- cont (1, 0, 0): Contradictory—inferred and rejected, but not defended.
- conf (1, 1, 0): Conflicting—inferred, defended, and rejected.
This structure allows the system to acknowledge that a conclusion has been reached (it is "inferred") even if it remains problematic (e.g., "contradictory" or "dissonant"). By explicitly tracking these states, the framework avoids the logical "crashes" that occur when forced to use a simpler three-valued logic.
Key Results and Insights
The introduction of the SIX labeling system yields several significant theoretical and practical results:
- Existence and Uniqueness Guaranteed: Every ABA framework is guaranteed to have a unique grounded labeling under the SIX semantics, restoring predictability to non-flat reasoning.
- Backward Compatibility: For flat ABA frameworks, the new semantics perfectly align with standard Dung-style results, ensuring the system is a true generalization.
- Complexity Preservation: Surprisingly, the 6-valued approach reduces the computational complexity of non-flat ABA back to the levels of flat ABA. For frameworks using Horn-rules, computing the grounded state remains in P (Polynomial time), avoiding the complexity jump seen in previous treatments.
Conclusion
By refining the way we label uncertainty and inference, this research provides a robust foundation for non-flat Assumption-Based Argumentation. The SIX labeling system not only fixes long-standing theoretical gaps but also ensures that the increased expressivity of non-flat frameworks does not come at the cost of computational feasibility. Future work will focus on extending these results to other semantics like "stable" or "ideal" and implementing these rules in practical solvers for large-scale knowledge bases.
Summary updated