Splitting Assumption-Based Argumentation Frameworks

Giovanni Buraglio, Wolfgang Dvořák, Stefan Woltran · 2026

Read Splitting Assumption-Based Argumentation Frameworks by Giovanni Buraglio, Wolfgang Dvořák, Stefan Woltran (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-27964.txt.

Introduction

Buraglio, Dvorak and Woltran bring the divide-and-conquer technique of splitting to assumption-based argumentation, a formalism for reasoning over debates. Earlier splitting worked on the graph form of a framework, but turning assumption frameworks into graphs can blow up exponentially and blunt the gain. Splitting the knowledge base itself, extended to a parametrised form, avoids that blow-up and keeps the method useful.

Catalog record

CREATORGiovanni Buraglio, Wolfgang Dvořák, Stefan Woltran
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE104182
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2604.27964

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Splitting Assumption-Based Argumentation Frameworks Giovanni Buraglio, Wolfgang Dvořák, Stefan Woltran 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. 1 Introduction Computational models of argumentation in AI [ 25 ] offer formal approaches to represent and reason over debates involving conflicting or uncertain information [ 13 , 17 , 23 , 26 , 28 , 43 ] . Assumption-Based Argumentation (ABA) [ 7 ] captures argumentative scenarios by means of so-called ABA frameworks (ABAFs), or ABA knowledge bases, consisting of a set of defeasible sentences (assumptions) and inference rules. Argumentative reasoning can be performed in ABA following two different approaches. The direct approach, typically employed by ABA solvers [ 33 , 34 ] , allows to reason over the ABA knowledge base itself through semantics defined at the level of assumptions. In contrast, the indirect approach [ 31 ] realises reasoning in a two-step process: first an argument graph comprising arguments and their relations is generated from the ABAF, by means of the so-called instantiation procedure; then, semantics from abstract argumentation are applied to the obtained graph in order to find acceptable sets of arguments, along with the assumptions supporting them. Although ABA is a well-established formalism for non-monotonic reasoning, with applications in medical decision-making, explainable AI, and causal discovery [ 22 , 24 , 41 ] , the high computational complexity of core reasoning tasks in ABA poses a significant challenge for its deployment in practice [ 15 ] . This issue is further aggravated when ABAFs are instantiated into argument graphs, such as Dung’s Argumentation Frameworks (AFs) [ 18 ] or Argumentation Frameworks with Collective Attacks (SETAFs) [ 38 ] , as the instantiation can be computationally expensive and may result in exponentially large graphs [ 32 ] . In the context of non-monotonic reasoning, one prominent 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 , originally developed for answer-set programming [ 36 ] and later adapted to other nonmonotonic formalisms, e.g. default theories [ 44 ] and recently Abstract Argumentation [ 4 , 2 , 37 , 3 , 35 , 1 ] . This approach focuses on incrementally computing the extensions of a given argumentation framework by means of the extension of its sub-frameworks, thereby avoiding to consider the entire solution-space of the original framework. Despite the successful application in graph-based argumentation [ 3 ] , splitting, so far, has been neglected for rule-based argumentation systems like Assumption-Based Argumentation. A straightforward attempt to apply splitting in ABA would be to first instantiate the ABAF to a corresponding Dung’s AF and then perform AF splitting. However, the exponential number of auxiliary arguments introduced during instantiation might invalidate the usefulness of splitting. To overcome this limitation, we instead consider the instantiation of ABAFs as SETAFs, which yield more concise graphical representations [ 30 ] . Thus, we first develop a splitting scheme for SETAFs, enabling incremental computation for the indirect approach of reasoning. This method has the advantage of being easily applicable to any formalism that can be instantiated as a SETAF. However, its drawback is that we have to instantiate the knowledge base, which comes with a computational cost, and we cannot even use the splitting to speed up the instantiation step. To address this issue, we present a splitting schema that operates directly on ABA knowledge bases. To this end, this paper makes the following contributions: • Towards ABA splitting, we generalise existing notions of splitting from AFs to SETAFs (Section 3 ) for complete, stable, preferred and grounded semantics. • We then introduce the notion of ABA splitting in Section 4 , along with the syntactic adjustments required to establish a splitting theorem, which we prove under complete, stable, preferred and grounded semantics. • In Section 5 we extend our results to the more general notion of parameterised splitting [ 2 ] , showing that a splitting theorem holds for ABAFs under stable semantics. • In Section 6 we address computing splittings for SETAFs and ABAFs, by reducing it to a graph splitting problem and reusing dedicated algorithms for AFs. • In Section 7 we take a closer look at the relationship between the splitting algorithm for ABAFs and the instantiation procedure into SETAFs. • Finally, after reviewing related work (Section 8 ), we conclude with a summary and outline directions for future research (Section 9 ). 2 Preliminaries Assumption-Based Argumentation We recall here the basic concepts of assumption-based argumentation (ABA) [ 14 ] . Debates are represented by means of so-called ABA Frameworks (ABAFs), which consist of a deductive system (\mathcal{L},\mathcal{R}) , where \mathcal{L} is a set of sentences, and \mathcal{R} is a set of rules over \mathcal{L} . A rule r\in\mathcal{R} has the form a_{0}\leftarrow a_{1},\dots,a_{n} with a_{i}\in\mathcal{L} , body(r)=\{a_{1},\dots,a_{n}\} and head(r)=a_{0} . Definition 1 . An ABAF is a tuple (\mathcal{L},\mathcal{R},\mathcal{A},\overline{\phantom{a}}) , where (\mathcal{L},\mathcal{R}) is a deductive system, \mathcal{A}\subseteq\mathcal{L} a set of assumptions, and \overline{\phantom{a}}:\mathcal{A}\to\mathcal{L} is a total mapping, called contrary function. For a set of assumptions, S\subseteq\mathcal{A} we use \overline{S} to indicate the set of contraries of S . Conversely, we define the partial function \alpha:\mathcal{L}\to\mathcal{A} assigning an assumption to its contrary b\in\overline{\mathcal{A}} such that \alpha(b)=a if b=\overline{a} . This generalises to sets of contraries as before. For a set of rules R , we fix head(R)=\{head(r)\mid r\in R\} , body(R)=\{body(r)\mid r\in R\} . Further, we use atom(S)=\{p\in\mathcal{L}\mid p\in S\lor\alpha(p)\in S\lor\overline{p}\in S\} . In what follows, we read atom(p) as atom(\{p\}) . For a rule r\in\mathcal{R} , we say that r is: a fact if body(r)=\emptyset ; a loop-rule if \overline{a}=head(r) and a\in body(r) . A sentence q\in\mathcal{L} is tree-derivable from S\subseteq\mathcal{A} and rules R\subseteq\mathcal{R} , denoted by S\vdash^{R}q , if there is a finite rooted labelled tree T where: the root of T is labelled with q ; the set of labels for the leaves of T is equal to S or S\cup\{\top\} ; and for every inner node v of T there is a rule r\in R such that v is labelled with head(r) , and every successor

Read the complete text