🤖 AI

Splitting Assumption-Based Argumentation Frameworks

This paper addresses the computational intractability of Assumption-Based Argumentation by introducing and generalizing a splitting technique that operates directly on the knowledge base rather than its graph-based instantiation, thereby avoiding exponential growth while enabling efficient, divide-and-conquer reasoning.

Original authors: Giovanni Buraglio, Wolfgang Dvorak, Stefan Woltran

Published 2026-05-01

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Giovanni Buraglio, Wolfgang Dvorak, Stefan Woltran

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to solve a massive, tangled knot of logic puzzles. In the world of Artificial Intelligence, this is called Assumption-Based Argumentation (ABA). It's a way for computers to debate, reason, and decide what to believe when information is conflicting or uncertain.

The problem? These knots can get so huge and complex that even the fastest computers get stuck trying to untangle them all at once. This is the "computational complexity" problem the authors are tackling.

Here is how the paper proposes to solve it, using simple analogies:

The Old Way: Building a Giant Map

Usually, to solve an ABA problem, computers first translate the logical rules into a giant "argument map" (specifically, a graph where dots are arguments and lines are attacks).

The Analogy: Imagine you have a recipe book (the knowledge base). To figure out the final dish, you try to draw a massive flowchart showing every single ingredient, every step, and every possible mistake.
The Problem: If the recipe book is big, the flowchart becomes exponentially huge. It's like trying to draw a map of every single grain of sand on a beach just to find one shell. The paper notes that this "instantiation" step is often too expensive and creates a map so big it defeats the purpose of trying to solve it.

The New Strategy: "Splitting" the Problem

The authors introduce a technique called Splitting. Think of this not as drawing a giant map, but as hiring a team of specialists to solve the problem in smaller, manageable chunks.

1. The "Bottom-Up" Kitchen (Standard Splitting)

Imagine a kitchen with a Bottom Counter (where you prep basic ingredients) and a Top Counter (where you cook the final meal).

The Rule: You can only move a dish from the Bottom to the Top if the Top doesn't need to send instructions back down to change the prep work.
The Process:
1. Split: The computer looks at the recipe book and finds a natural break point. It separates the "Bottom" rules (independent facts) from the "Top" rules (dependent conclusions).
2. Solve the Bottom: It solves the Bottom Counter first. It figures out which ingredients are safe to use.
3. Modify the Top: It takes the results from the Bottom and "modifies" the Top Counter. If the Bottom decided "Ingredient X is bad," the Top Counter removes any recipe that needs Ingredient X.
4. Solve the Top: Now, the Top Counter is smaller and easier to solve because it only has to deal with the remaining valid ingredients.
5. Combine: The final answer is just the combination of the Bottom solution and the Top solution.

This works great if the kitchen is perfectly separated. But what if the Top Counter does need to send a message back to the Bottom?

2. The "Parametrised" Kitchen (Handling the Messy Parts)

Sometimes, the rules aren't perfectly separated. Maybe a Top rule says, "If you use Salt, you can't use Sugar," but Sugar is prepped on the Bottom. This creates a loop that stops the simple splitting.

The authors introduce Parametrised Splitting.

The Analogy: Imagine the Top Counter sends a "Maybe" note to the Bottom Counter: "I might need Salt, but I'm not sure yet."
The Fix: The computer creates a "dummy" version of the Bottom Counter. It asks: "What if we do use Salt? What if we don't?" It runs two tiny simulations.
The Result: It solves the problem for both scenarios, then stitches the correct one together. This allows them to split the problem even when the rules are slightly tangled, without having to draw the whole giant map first.

Why This Matters (According to the Paper)

The paper claims two main victories:

Direct Solving: They figured out how to split the recipe book (the knowledge base) directly, without needing to draw the giant, messy flowchart first. This saves a massive amount of computer memory and time.
Generalization: They proved that this "divide and conquer" method works for all the standard ways computers judge arguments (like finding the "most stable" or "most preferred" solution).

The Bottom Line

Instead of trying to untangle a giant knot of logic all at once (which is slow and hard), this paper teaches the computer to:

Find a place to cut the knot into two smaller pieces.
Solve the first piece.
Adjust the second piece based on the first.
Solve the second piece.
Glue the answers together.

By doing this, they can solve complex reasoning problems much faster, even if the original problem was too big to handle in one go. They also showed how to handle the "messy" parts where the pieces aren't perfectly independent, ensuring the method works for almost any scenario.

Technical Summary: Splitting Assumption-Based Argumentation Frameworks

1. Problem Statement

Assumption-Based Argumentation (ABA) is a prominent formalism for modeling debates involving conflicting or uncertain information. However, core reasoning tasks in ABA suffer from high computational complexity. A common strategy to mitigate this is instantiation, where an ABA framework (ABAF) is converted into a graph-based argumentation framework (such as Dung's AF or SETAFs) to apply existing graph-based solvers.

The critical bottleneck is that this instantiation process can result in an exponential explosion of arguments and attacks, particularly when using Dung's AFs. Even with more concise representations like Argumentation Frameworks with Collective Attacks (SETAFs), the instantiation step itself remains computationally expensive.

Divide-and-conquer strategies, specifically splitting, have been successfully applied to graph-based frameworks (AFs) to solve reasoning tasks incrementally by decomposing the framework into sub-frameworks. However, applying splitting directly to ABAFs via instantiation is often inefficient or invalid due to the exponential growth of the graph. Conversely, applying splitting directly to the ABA knowledge base has been neglected because the structural differences between rule-based ABA and graph-based AFs make direct translation of splitting theorems non-trivial.

2. Methodology

The authors propose a comprehensive approach to splitting that operates at two levels: the graph level (SETAFs) and the knowledge base level (ABAFs).

A. Splitting SETAFs (The Graph Level)

The paper first generalizes the concept of splitting from standard Dung AFs to SETAFs (which allow sets of arguments to attack a single argument).

Splitting Definition: A SETAF is split into two sub-frameworks ( $SF_1, SF_2$ ) separated by a set of "links" ( $R_3$ ) representing attacks from $SF_1$ to $SF_2$ .
Reduct and Modification: To compute extensions incrementally:
1. Reduct: $SF_2$ is modified based on an extension $E_1$ of $SF_1$ . Arguments in $SF_2$ attacked by $E_1$ are removed, and attacks involving defeated arguments are filtered.
2. Modification: To handle undecided links (attacks where the tail is not defeated but not fully accepted), the framework introduces set-self-attacks in the modified $SF_2$ . This ensures that if an argument in $SF_1$ remains undecided, it can still influence the status of arguments in $SF_2$ via self-attacks.
Theorem: The authors prove that extensions of the original SETAF can be reconstructed by combining extensions of the modified sub-frameworks for standard semantics (stable, admissible, complete, preferred, grounded).

B. Splitting ABAFs (The Knowledge Base Level)

To avoid the cost of instantiation, the paper introduces a direct splitting schema for ABAFs based on the syntactic structure of the deductive system.

Splitting Sets: A set of sentences $S$ is a splitting set if it partitions the rules such that no rule in the "top" part derives a contrary of an assumption in the "bottom" part. This ensures the bottom part ( $D_1$ ) can be evaluated independently.
Reduct ( $D_2^E$ ): Given an extension $E$ of the bottom framework $D_1$ , the top framework $D_2$ is reduced by removing rules whose bodies are incompatible with $E$ and simplifying remaining rules.
Modification ( $D_2^\star$ ): Similar to SETAFs, the authors handle undecided assumptions (those not in $E$ and whose contraries are not derivable from $E$ ). They introduce a fresh assumption $x_u$ and a loop-rule $x_u \leftarrow x_u$ . Rules in $D_2$ containing undecided sentences in their bodies are modified to include $x_u$ . This propagates the "undecided" status from $D_1$ to $D_2$ .
Parametrised Splitting: Recognizing that strict splitting sets are rare in complex ABAFs, the authors generalize the concept to quasi-splitting (or $k$ -splitting). This allows a limited number of assumptions in the bottom to be attacked by the top. This is handled by introducing "vulnerability" assumptions and meta-rules to encode choices, effectively relaxing the structural constraints while maintaining correctness under stable semantics.

C. Algorithmic Implementation

The paper demonstrates that computing splitting sets for ABAFs can be reduced to finding Strongly Connected Components (SCCs) in a Dependency Graph.

The dependency graph nodes represent sentences, and edges represent rule dependencies and contrary relationships.
By contracting SCCs, the graph becomes a Directed Acyclic Graph (DAG), allowing the use of existing linear-time algorithms (e.g., Tarjan's algorithm) to find optimal splitting points.
This approach allows the reuse of existing graph-splitting algorithms for SETAFs and ABAFs without requiring full instantiation.

3. Key Contributions

SETAF Splitting Scheme: A novel splitting definition for SETAFs that generalizes Dung's AF splitting, handling collective attacks and undecided links via set-self-attacks.
Direct ABA Splitting: A splitting schema that operates directly on ABA knowledge bases, bypassing the need for instantiation into argument graphs. This includes the definition of reduct and modification tailored to the deductive nature of ABA.
Parametrised Splitting for ABA: An extension to quasi-splitting (inspired by Baumann et al. 2012) that allows for limited inter-dependencies between sub-frameworks, significantly increasing the applicability of the method to real-world ABAFs.
Theoretical Guarantees: Formal proofs (Theorems 2 and 3) establishing the correctness of the splitting approach for stable, admissible, complete, preferred, and grounded semantics.
Algorithmic Reduction: A method to compute splitting sets for ABAFs by reducing the problem to graph splitting on dependency graphs, enabling efficient implementation using existing tools.

4. Results

Correctness: The paper proves that the incremental computation of extensions via splitting yields the same results as computing them on the full framework.
Efficiency: The splitting process involves only syntactic modifications (adding at most one rule and one assumption per sub-framework in the standard case, or bounded by $2k$ for $k$ -splitting). This avoids the exponential blow-up associated with full instantiation.
Applicability: The approach works for both the direct approach (reasoning on the ABAF directly) and the indirect approach (reasoning on the instantiated SETAF).
Scalability Potential: By enabling divide-and-conquer reasoning, the method promises to solve large ABA instances that are currently intractable due to the size of their instantiated graphs.

5. Significance

This work bridges a critical gap between the theoretical efficiency of divide-and-conquer strategies and the practical application of Assumption-Based Argumentation.

Overcoming Instantiation Costs: It provides a viable alternative to the "instantiation-first" paradigm, which is often the primary bottleneck in ABA solvers.
Generalization: By generalizing splitting to SETAFs and then to ABAFs, the paper unifies reasoning strategies across different argumentation formalisms.
Future Applications: The authors highlight the potential for applying these techniques to Argumentative Causal Discovery, a field currently struggling with scalability. The ability to split large knowledge bases could enable the analysis of complex causal models that are currently too large to process.
Implementation Readiness: The reduction to dependency graph splitting suggests that these methods can be immediately integrated into existing ABA solvers (e.g., those based on Answer Set Programming) with minimal overhead, potentially yielding significant performance gains (referenced as ~60% acceleration in similar AF contexts).

In summary, the paper presents a robust theoretical and algorithmic framework for decomposing complex Assumption-Based Argumentation problems, offering a path toward scalable and efficient reasoning in non-monotonic logic systems.