pith. sign in

arxiv: 2604.27964 · v1 · submitted 2026-04-30 · 💻 cs.AI

Splitting Assumption-Based Argumentation Frameworks

Giovanni Buraglio , Wolfgang Dvorak , Stefan Woltran This is my paper

Pith reviewed 2026-05-07 05:38 UTC · model grok-4.3

classification 💻 cs.AI
keywords assumption-based argumentationsplittingparametrized splittingknowledge baseargumentation frameworkscomputational complexityextensionsdivide-and-conquer
0
0 comments X

The pith

Splitting can be applied directly to the knowledge base of assumption-based argumentation frameworks to avoid exponential costs from graph instantiation, and generalized to a parametrized version.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

Assumption-based argumentation models debates via assumptions and rules but becomes computationally heavy once instantiated into argument graphs for reasoning tasks. The paper develops splitting directly on the original knowledge base, so that extensions are found by solving smaller sub-bases and then merging the results. This keeps the same output as the full framework while sidestepping the size explosion that occurs during instantiation. The technique is further lifted to a parametrized form that works under different semantics. If the claim holds, large ABA models become feasible for applications that previously hit complexity barriers.

Core claim

Our work investigates the concept of splitting on the knowledge base rather than on its graph-based instantiation. Furthermore, we generalise splitting to its parametrised version for ABAFs, enabling incremental computation of extensions by restricting the search space to sub-frameworks and combining the obtained results.

What carries the argument

Splitting operation defined directly on the ABA knowledge base, which partitions assumptions and rules into sub-bases for separate extension computation before recombination.

If this is right

  • Extensions of the complete ABA framework are recovered exactly by combining results from the split sub-bases.
  • The exponential growth in arguments that normally arises from instantiation is avoided.
  • A parametrized version of splitting applies across different ABA semantics with the same incremental structure.
  • Core reasoning tasks such as extension enumeration become feasible on larger knowledge bases by restricting search to sub-frameworks.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Solver implementations could adopt knowledge-base splitting as a preprocessing step to scale to real-world debate sizes.
  • The same direct splitting idea might transfer to other structured argumentation systems that rest on explicit rule bases rather than flat graphs.
  • Hybrid algorithms could combine this splitting with caching or approximation methods to handle even larger or dynamic knowledge bases.

Load-bearing premise

That splitting defined directly on the ABA knowledge base will correctly compute the same extensions as the full framework while avoiding the exponential growth from graph instantiation, without introducing new correctness issues or requiring post-hoc adjustments.

What would settle it

An ABA framework where the extensions obtained by splitting on the knowledge base differ from those computed on the fully instantiated graph, or where the method fails to reduce overall computation time.

read the original abstract

Assumption-Based Argumentation (ABA) is a well-established formalism for modelling and reasoning over debates, with a wide range of applications. However, the high computational complexity of core reasoning tasks in ABA poses a significant challenge for its applicability. This issue is further aggravated when ABA frameworks (ABAFs) are instantiated into graph-based argumentation formalisms, such as Dung's Argumentation Frameworks (AFs) and Argumentation Frameworks with Collective Attacks (SETAFs). In knowledge representation and reasoning, a key strategy to address computational intractability is to optimise reasoning over a given knowledge base through divide-and-conquer algorithms. A paradigmatic example of this approach is splitting, where extensions of a given framework are computed incrementally, by restricting the search space to sub-frameworks only, and then combining the obtained results. This approach has been successfully applied to AFs, for which also a parametrised version has been introduced under stable semantics. However, the exponential growth produced by the instantiation might undermine the usefulness of splitting on the argument graphs induced by ABAFs. To address this issue, our work investigates the concept of splitting on the knowledge base rather than on its graph-based instantiation. Furthermore, we generalise splitting to its parametrised version for ABAFs.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper claims to develop a splitting technique for Assumption-Based Argumentation Frameworks (ABAFs) that operates directly on the knowledge base (assumptions and rules) rather than on the instantiated graph into AFs or SETAFs. It generalizes this to a parametrised version (under stable semantics) to support divide-and-conquer computation of extensions while avoiding exponential blowup from full instantiation.

Significance. If the KB-level splitting is shown to be sound and complete, the work would offer a practical optimization for ABA reasoning tasks by enabling incremental extension computation on sub-KBs with a subsequent combination step. This extends prior splitting results for AFs in a way that preserves the original semantics without graph construction, which could improve scalability for applications in debate modeling and knowledge representation.

major comments (2)
  1. [§4.2] §4.2 (Definition of KB-splitting): The splitting operator on the ABA knowledge base does not explicitly define the treatment of rules whose bodies or heads reference assumptions belonging to multiple sub-KBs or shared assumptions across parts. This is load-bearing for the central equivalence claim, as any unaccounted cross-part dependency would cause the combination operator to produce incomplete or spurious extensions compared to the full ABAF.
  2. [Theorem 5.3] Theorem 5.3 (Equivalence under stable semantics): The proof of equivalence between extensions computed via KB-splitting plus combination and those of the original ABAF assumes that all relevant attacks and derivations are localized within or between the chosen sub-KBs. No detailed case analysis or counterexample check is provided for inter-dependent rules that span sub-KBs, leaving open the possibility that the parametrised generalisation fails to preserve exact extensions.
minor comments (2)
  1. [§2] The preliminaries section could include a short worked example contrasting graph-level splitting with the proposed KB-level version to illustrate the claimed avoidance of exponential growth.
  2. [§4.3] Notation for the combination operator (e.g., how partial extensions are merged) is introduced without an accompanying small illustrative ABAF that shows step-by-step reconstruction.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the constructive comments, which help clarify the presentation of our KB-level splitting approach for ABAFs. We address each major comment below and will incorporate revisions to strengthen the definitions and proofs.

read point-by-point responses

  1. Referee: [§4.2] §4.2 (Definition of KB-splitting): The splitting operator on the ABA knowledge base does not explicitly define the treatment of rules whose bodies or heads reference assumptions belonging to multiple sub-KBs or shared assumptions across parts. This is load-bearing for the central equivalence claim, as any unaccounted cross-part dependency would cause the combination operator to produce incomplete or spurious extensions compared to the full ABAF.

    Authors: We agree that explicit treatment of rules with assumptions spanning multiple sub-KBs or shared assumptions is necessary for clarity. The current definition in §4.2 partitions the assumption set into disjoint components and assigns each rule to the sub-KB containing its head, with the combination operator then accounting for cross-dependencies via the union of derived attacks. However, this handling is only implicit. In the revised manuscript we will expand the definition with a dedicated clause specifying the assignment of cross-referencing rules (including an illustrative example) and prove that no such rule is omitted from the combination step, thereby eliminating ambiguity in the equivalence claim. revision: yes

  2. Referee: [Theorem 5.3] Theorem 5.3 (Equivalence under stable semantics): The proof of equivalence between extensions computed via KB-splitting plus combination and those of the original ABAF assumes that all relevant attacks and derivations are localized within or between the chosen sub-KBs. No detailed case analysis or counterexample check is provided for inter-dependent rules that span sub-KBs, leaving open the possibility that the parametrised generalisation fails to preserve exact extensions.

    Authors: The proof of Theorem 5.3 proceeds by showing that any stable extension of the full ABAF projects to stable extensions of the sub-ABAFs and that the combination operator reconstructs exactly the original extension under stable semantics. While the general argument covers derivations spanning sub-KBs through the attack relation induced by the union, we accept that an explicit case analysis for inter-dependent rules would strengthen the result. In the revision we will insert a dedicated subsection in the proof that enumerates the possible configurations of rules whose bodies reference assumptions from distinct sub-KBs, verifies that the combination step preserves both acceptability and stability, and confirms no spurious extensions arise. This addition will also include a brief counterexample check for the parametrised case. revision: yes

Circularity Check

0 steps flagged

No circularity: KB-level splitting generalizes AF results via independent definition and proof

full rationale

The paper defines splitting directly on the ABA knowledge base (assumptions + rules) and extends the parametrised version from AFs under stable semantics. This is a generalization motivated by avoiding exponential graph instantiation, not a reduction of the central equivalence claim to fitted parameters, self-definitions, or load-bearing self-citations. The equivalence between KB splitting and full ABAF extensions is presented as a theorem to be established (soundness/completeness), not presupposed by construction or prior author results. No equations or steps in the provided abstract reduce the new claims to the inputs by definition. This matches the reader's assessment of no apparent circular reasoning.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the domain assumption that splitting properties transfer from graph-based frameworks to the underlying ABA knowledge base without loss of correctness or introduction of new parameters.

axioms (1)
  • domain assumption Splitting properties established for AFs and SETAFs under stable semantics can be lifted to ABA frameworks
    The abstract states that splitting has been successfully applied to AFs and now investigates the same for ABAFs.

pith-pipeline@v0.9.0 · 5514 in / 1257 out tokens · 37385 ms · 2026-05-07T05:38:10.986822+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

29 extracted references · 29 canonical work pages

  1. [1]

    Parameterized splitting: A simple modification-based approach. In Erdem, E.; Lee, J.; Lierler, Y .; and Pearce, D., eds.,Correct Reasoning - Essays on Logic-Based AI in Hon- our of Vladimir Lifschitz, volume 7265 ofLecture Notes in Computer Science, 57–71. Springer. Baumann, R.; Brewka, G.; and Wong, R. 2011. Split- ting argumentation frameworks: An empir...

    work page 2011

  2. [2]

    International Foundation for Autonomous Agents and Multiagent Systems. Dung, P. M. 1995. On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic pro- gramming and n-person games.Artif. Intell.77(2):321–358. Dvoˇr´ak, W.; K¨onig, M.; Ulbricht, M.; and Woltran, S. 2024. Principles and their computational consequences for ...

    work page 1995

  3. [3]

    Expressiveness of SETAFs and support-free ADFs under 3-valued semantics.J. Appl. Non Class. Logics33(3- 4):298–327. Fan, X., and Toni, F. 2012. Agent strategies for aba-based information-seeking and inquiry dialogues. In Raedt, L. D.; Bessiere, C.; Dubois, D.; Doherty, P.; Frasconi, P.; Heintz, F.; and Lucas, P. J. F., eds.,ECAI 2012 - 20th European Confe...

    work page 2012

  4. [4]

    In Marquis, P.; Son, T

    Argumentation frameworks induced by assumption- based argumentation: Relating size and complexity. In Marquis, P.; Son, T. C.; and Kern-Isberner, G., eds.,Pro- ceedings of the 20th International Conference on Princi- ples of Knowledge Representation and Reasoning, KR 2023, Rhodes, Greece, September 2-8, 2023, 440–450. Lehtonen, T.; Rapberger, A.; Toni, F....

    work page 2023

  5. [5]

    IfE 1 ∈cf(SF 1)andE 2 ∈cf(mod E1 R3 (SF ′ 2)), thenE 1 ∪ E2 ∈cf(SF)

    work page

  6. [6]

    Proof.(1.) We need to show for each(T, h)∈R 1 ∪R 2 ∪ R3 thatT∪ {h} ̸⊆E=E 1 ∪E 2

    IfE∈cf(SF), thenE 1 =E∩A 1 ∈cf(SF 1)and E∩A 2 ∈cf(SF ′ 2). Proof.(1.) We need to show for each(T, h)∈R 1 ∪R 2 ∪ R3 thatT∪ {h} ̸⊆E=E 1 ∪E 2. LetSF ′ 2 = (A ′ 2, R′ 2) andSF ⋆ 2 = (A ⋆ 2, R⋆ 2). If(T, h)∈R 1 we immediately get T∪ {h} ̸⊆E, since we knowE 1 is conflict-free inSF 1. For(T, h)∈R 2 there are two cases: either (a) the attack is removed when we co...

    work page

  7. [7]

    Thus, we conclude thatE∩A 2 ⊆A ′

    work page

  8. [8]

    Finally, whenever for a link(T, h)∈R 3 withT∩A 1 ⊆Ewe add an attack(T∩A ′ 2, h)∈R ′ 2 when constructing the reduct, we also obtain(T∩A ′ 2)∪ {h} ̸⊆E since otherwiseT∪{h} ⊆E

    Moreover, byE∈cf(SF)we know for each(T, h)∈R 2 thatT∪ {h} ̸⊆Ewhich carries over toSF ′ 2, since the attacks inR 2 may be removed, but are never changed. Finally, whenever for a link(T, h)∈R 3 withT∩A 1 ⊆Ewe add an attack(T∩A ′ 2, h)∈R ′ 2 when constructing the reduct, we also obtain(T∩A ′ 2)∪ {h} ̸⊆E since otherwiseT∪{h} ⊆E. Therefore,E∩A 2 ∈cf(SF ′ 2) co...

    work page

  9. [9]

    IfE 1 ∈σ(SF 1)andE 2 ∈σ(SF ⋆ 2 ), thenE 1 ∪E 2 ∈ σ(SF)

    work page

  10. [10]

    Proof.(stable)

    IfE∈σ(SF), thenE 1 =E∩A 1 ∈σ(SF 1)andE∩ A2 ∈σ(SF ⋆ 2 ). Proof.(stable). (1.) From Proposition 1 together with the assumptions thatE 1 ∈stb(SF 1)andE 2 ∈stb(SF ⋆ 2 ), we know thatE=E 1 ∪E 2 ∈cf(SF). Leta∈A\E, we show thata∈E + R. Ifa∈A 1 byE 1 ∈stb(SF 1)we geta∈ (E1)+ R1, which immediately gives usa∈E + R. Ifa∈A 2, eithera∈A ′ =A ⋆ ora /∈A ′ =A ⋆. Ifa /∈A ...

    work page

  11. [11]

    (admissible)

    =stb(SF ⋆ 2 ). (admissible). (1.) Since admissibility implies conflict- freeness, we know from Proposition 1 thatE=E 1 ∪E 2 ∈ cf(SF). We need to show thatEdefends itself inSF, i.e. for alla∈E, if(T, a)∈R 1 ∪R 2 ∪R 3, then(T ′, t)∈R 1 ∪ R2 ∪R 3 forT ′ ⊆Eandt∈T. Consider an argumenta∈ E1.E 1 defendsafrom each attack inR 1 towardsasince E1 ∈adm(SF 1). Theref...

    work page

  12. [12]

    However, sinceais defended byEinSF, there is a counter-attack(S, t)∈R 2 ∪R 3 s.t.S⊆Eand t∈(T\ {a})(ort∈(T ′ \ {a}), resp.). If(S, t)∈R 2 then fromS⊆EandE 2 ⊆A ′ 2 (which we get fromE 2 ∈ cf(SF ′ 2)via Proposition 1) and the fact that then(S, t)∈R ′ 2 sinceS∪ {t} ⊆A ′ 2 we get thatE 2 defendsavia(S, t) against(T, a)inSF ⋆ 2 . If(S, t)∈R 3 sinceS⊆Ewe have S...

    work page 2006

  13. [13]

    Thus,(T, a)/∈U E1 R3 and ais unattacked inR ⋆

    For the same reason, and given that(E 1)+ R1∪R3 ⊇(E 1)+ R1, we also know thatT∩(E 1)+ R1∪R3 ̸=∅. Thus,(T, a)/∈U E1 R3 and ais unattacked inR ⋆

    work page

  14. [14]

    Contradiction

    Again,ais vacuously defended byE 2 inSF ⋆ 2 andE 2 /∈com(SF⋆ 2 ). Contradiction. Consider now the case where(S, t)∈R 3 for someS⊆E 1 ∪E 2 andt∈ T∩A 2. ifS⊆E 1, thenT∩(E 1)+ R3 ̸=∅and(T∩A ′ 2, a)/∈ R′

    work page

  15. [15]

    For the same reason as before,(T∩A ′ 2, a)/∈R⋆

    work page

  16. [16]

    IfS̸⊆E 1, then(S∩A ′ 2, t)∈R ′ 2 becauseS∩A ′ 2 ̸=∅, t∈A ′ 2,S∩A 1 ⊆E 1 andS∩(E 1)+ R1∪R3 =∅

    Hence, ais vacuously defended byE 2 inSF ⋆ 2 andE 2 /∈com(SF⋆ 2 ). IfS̸⊆E 1, then(S∩A ′ 2, t)∈R ′ 2 becauseS∩A ′ 2 ̸=∅, t∈A ′ 2,S∩A 1 ⊆E 1 andS∩(E 1)+ R1∪R3 =∅. We derive directly that(S∩A ′ 2, t)∈R ⋆ 2 since the modification does not delete attacks. Hence,E 2 defendsainSF ⋆ 2 . Finally, this contradicts our hypothesis thatE2 ∈com(SF ⋆ 2 ), concluding the...

    work page

  17. [17]

    But we know(S, t)∈R ⋆ 2 corresponds to some attack inR 2∪R3

    Note thatt /∈S, as otherwise(S, t)would not counter the attack(T, a)which we assumed. But we know(S, t)∈R ⋆ 2 corresponds to some attack inR 2∪R3. If(S, t)∈R 2 we have thatEdefendsain SF(via(S, t)), a contradiction toE∈com(SF). If on the other hand there is some(S ′, t)∈R 3 withS ′ ⊃Swe know that alsoS ′ ∩A 1 ⊆E 1, as otherwise we would havet∈S (if(S, t)w...

    work page

  18. [18]

    ForE∩A 2, assume now there is anS 2 ∈adm(SF ⋆ 2 )such thatS 2 ⊃E∩A 2

    we obtainE∩A 1 ∈pref(SF 1). ForE∩A 2, assume now there is anS 2 ∈adm(SF ⋆ 2 )such thatS 2 ⊃E∩A 2. For statement 1 of admissible semantics,(E∩A 1)∪S 2 is admissible inSFwhich contradicts the maximality ofE. This conclude the proof. (grounded). (1) Since the grounded extension is also complete, we only need to show thatE 1 ∪E 2 is the mini- mal complete ext...

    work page 2024

  19. [19]

    IfE 1 ∈cf(D 1)andE 2 ∈cf(D ⋆ 2), thenE 1 ∪E 2 ∈cf(D)

    work page

  20. [20]

    Proof.For notational convenience, letE=E 1 ∪E 2 and letD ′ 2 = (L 2,R ′ 2,A 2, 2)be the reduct ofD 2 w.r.t.E 1 = E∩ A 1

    IfE∈cf(D), thenE∩ A 1 ∈cf(D 1)andE∩ A 2 ∈ cf(DE 2 ). Proof.For notational convenience, letE=E 1 ∪E 2 and letD ′ 2 = (L 2,R ′ 2,A 2, 2)be the reduct ofD 2 w.r.t.E 1 = E∩ A 1. Moreover, we adaptS + R ={a|S⊢ R a}and S⊕ R =S∪S + R from SETAFs. (1.) To prove the statement we need to show that there is noa∈E 1 ∪E 2 and andR∈ Rsuch thatE 1 ∪E 2 ⊢R a. To- wards c...

    work page 2024

  21. [21]

    IfE 1 ∈σ(D 1)andE 2 ∈σ(D ⋆ 2), thenE 1 ∪E 2 ∈σ(D)

    work page

  22. [22]

    Proof.In what follows, we prove 1

    IfE∈σ(D), thenE∩ A 1 ∈σ(D 1)andE∩ A 2 ∈ σ(D⋆ 2). Proof.In what follows, we prove 1. and 2. for each seman- tics. (stable). (1.) First notice that sinceE 1 ∈stb(D 1), we haveU E1 D1 =∅, and consequentlyA ′ 2 =A ⋆

    work page

  23. [23]

    Thus, for anya∈ A \E, we show thata∈E + R, i.e.E⊢ R a for someR⊆ R

    (1.) From Proposition 3 together with the hypotheses thatE 1 ∈ stb(D1)andE 2 ∈stb(D ⋆ 2), we know thatE 1 ∪E 2 ∈cf(D). Thus, for anya∈ A \E, we show thata∈E + R, i.e.E⊢ R a for someR⊆ R. We proceed by cases. Leta∈ A 1. From hypothesis we know thatE 1 ⊢R1 afor someR 1 ⊆ R 1 which immediately impliesa∈E + R1. Leta∈ A 2. From hypothesis, we know thatE 2 ⊢R2 ...

    work page

  24. [24]

    If (a) holds, we getR⊆ R 2 andE=E 2 ⊢R a whereE 2 ⊆ A ′ 2 anda∈ A ′

    Since E⊢ R ainD, we have two possibilities: (a)E 1 =∅or (b) E1 ̸=∅. If (a) holds, we getR⊆ R 2 andE=E 2 ⊢R a whereE 2 ⊆ A ′ 2 anda∈ A ′

    work page

  25. [25]

    Thus,E 2 ⊢R aholds for some R⊆ R ′

    work page

  26. [26]

    Therefore, each ruler∈R∩ R 2 has a corresponding ruler ′ ∈ R ′ 2 such that body(r′) =body(r)\T h D1 (E1)

    If (b) holds,E 1 ∪E 2 ⊢R ainD. Therefore, each ruler∈R∩ R 2 has a corresponding ruler ′ ∈ R ′ 2 such that body(r′) =body(r)\T h D1 (E1). SinceE 1 ∪E 2 ∈cf(D) by hypothesis, we know thatT h D1 (E1)∩ E2 =∅. Hence, (E\E 1)⊢ R′ 2 awhereR ′ 2 ⊆ R ′

    work page

  27. [27]

    (complete)

    In both cases we have E2 ∪(E 2)+ R′ 2 =A ′ 2, concludingE 2 ∈stb(D ′ 2). (complete). (1.) Given statement 1 of admissible seman- tics proven above, we only need to show thata∈E 1 ∪E 2 for alla∈ Adefended byE 1 ∪E 2 inD. Assume towards contradiction that there is ana∈(A 1 ∪ A 2)\(E 1 ∪E 2) defended byE 1 ∪E 2. FromE 1 ∈com(D 1), we know that a /∈ A1 \E 1. ...

    work page

  28. [28]

    2.13) and the hypothesis thatais defended byE 1 ∪E 2, we get thatE 1 ∪E 2 ∪ {a}is an admissible (and thus conflict-free) extension inD

    (Thm. 2.13) and the hypothesis thatais defended byE 1 ∪E 2, we get thatE 1 ∪E 2 ∪ {a}is an admissible (and thus conflict-free) extension inD. Sinceais a self- attacking argument, we derive a contradiction. IfT̸⊆ A 2, sinceE 1 ∪E 2 defendsa, we know that for some t∈T∩A 1,E 1 ⊢ tor for somet∈T∩A 2 andS⊆E 1∪E2, S⊢ R′ t. In the first case, every ruler∈ R 2 wh...

    work page

  29. [29]

    As before, we consider possible attack scenarios towardsa

    Again, assume that there is such ana∈ A 2 \E 2. As before, we consider possible attack scenarios towardsa. If adoes not receive any attack inD ⋆ 2, then for everyT⊆ A andR⊆ R 2 such thatT⊢ R ainD, then for somer∈R it holds thatbody(r)∩IS D1 (E1)̸=∅(rwas eliminated by the reduct and not reintroduced). Hence,E 1 defendsain D, in contradiction withE∈com(D). ...

    work page