The topic of this work is related to a computational issue concerning an enriched abstract argumentation framework called RAF (“Recursive Argumentation Framework”). A RAF is composed of a set of arguments and a binary relation modelling the attacks as in Dung's framework. The main difference between Dung's framework and a RAF is the fact that a RAF is able to take into account higher-order interactions (i.e. an attack can target an attack and not only an argument). Since this kind of framework is relatively recent, the efficient computation of the main semantics remains an open question. In this paper, we propose one of the first algorithms dedicated to this issue. We prove the soundness and completeness of this algorithm.
computation (see [
The paper is organised as follows: Recursive Argumentation Frameworks (RAFs) and their
semantics are recalled in Section 2. Section 3 gives some additional definitions mandatory before
the presentation of the algorithm itself in Sections 4 and 5. An example of a clustering method is
provided in Section 6. Section 7 draws conclusions and opens future perspectives. The proofs of
the soundness and completeness of the approach can be found in [
Higher-order attacks (that is, possibly targeting attacks as well as arguments) have been introduced
in [
Definition 1. A Recursive Argumentation Framework (RAF) RAF = ⟨A, K, s, t⟩ is a quadruple where A and K are (possibly infinite) disjoint sets respectively representing arguments and attack names, and where s : K → A and t : K → A ∪ K are functions respectively mapping each attack name to its source and to its target. Definition 2. Let RAF = ⟨A, K, s, t⟩ be a recursive argumentation framework. A RAF labelling is a total function L : A ∪ K → {in, out, und}. We define in(L) (resp. out(L), und(L)) as the set {x ∈ A ∪ K|L(x) = in (resp. out, und)}.
L is a complete RAF labelling iff it satisfies:
∀x ∈ (A ∪ K),
1Whereas an extension assigns to its elements an accepted or a rejected status, a labelling considers a third status,
undecided, which applies to arguments which are neither accepted, nor rejected. This enrichment has proven useful
for the computation of acceptance statuses in AFs (see [
Regarding the RAF of Figure 1, Example 1 shows its grounded labelling.
Example 1. The grounded labelling of the RAF illustrated in Figure 1 is:
(a, und), (b, und), (c, und), (d, und), (e, in), ( f , in), (g, out), (h, und), (i, und), Lgr = (k, und), (l, und), (m, und)(α, in), (β , in), (γ, in), (δ , in), (ε, out), (ζ , in), (η, in), (θ , in), (ι, in), (κ, in), (λ , und), (ξ , und), (o, und), (π, in), (ρ, in), (ψ, in) ⎫ ⎪ ⎪ ⎪ ⎬ ⎪ ⎪ ⎪ ⎭
In order to define an algorithm able to answer the enumeration problem 4 in the case of a RAF,
similarly to the one given for an AF (AFDivider [
Considering a partial RAF implies to consider also its “inputs” (the elements that do not belong to the partial RAF but that can impact its labellings) and their labellings: Definition 5. Let RAF = ⟨A, K, s, t⟩ be a RAF and R˜A︁F = ⟨A˜ , K˜ , s˜, t˜, s, t⟩ be a partial RAF of RAF . The input I of R˜A︁F is a tuple ⟨︁ Sinp, Qinp⟩︁ where: Sinp = {s(α ) ∈ (A \ A˜ )|α ∈ K and t(α ) ∈ (A˜ ∪ K˜ )} and Qinp = {α ∈ (K \ K˜ )|t(α ) ∈ (A˜ ∪ K˜ )}. The tuple ⟨︂R˜A︁F , I, Linp⟩︂ is called a partial RAF with input, where Linp is a labelling of I.
Note that several partial RAFs with input can be built from a given partial RAF since several labellings can exist for its inputs.
The local function associates any partial RAF with input with a set of labellings: Definition 6. Let σ be a semantics. A local function Fσra f assigns to any partial RAF with input ⟨︂R˜A︁F , I, Linp⟩︂ a (possibly empty) set of labellings of R˜A︁F under σ , i.e. Fσra f (R˜A︁F , I, Linp) ∈ 2{L|L being any labelling over R˜A︁F }.
The notion of semantics decomposability is thus as follows: Definition 7. A semantics σ is full decomposable iff there is a local function Fσra f s.t., for any RAF RAF = ⟨A, K, s, t⟩ and any partition {R˜A︁F 1, ..., R˜A︁F n} of RAF , the set of all possible labellings under the semantics σ of RAF , denoted by Lσ (RAF ), satisfies: Lσ (RAF ) = {L1 ∪ ... ∪ Ln|∀i ∈ {1, ..., n}, Li ∈ Fσra f (R˜A︁F i, Ii, Liinp)} with Liinp = ( ⋃︁ L j) ↓Ii .6 j∈{1,...,n} s.t. j̸=i A semantics σ is said to be top-down (resp. bottom-up) decomposable iff:
Lσ (RAF ) ⊆ (resp. ⊇ ){L1 ∪ ... ∪ Ln|∀i ∈ {1, ..., n}, Li ∈ Fσra f (R˜A︁F i, Ii, Liinp)}
In [
Then, in [
Full decomposability w.r.t. Sra f -USCC (so Top-down and Bottom-up decomposability)
RAF semantics complete grounded preferred
stable × × × × “ ” (resp. “× ”) means that the semantics on the column has (resp. does not have) the property on the row.
Before explaining our algorithm, some additional definitions are needed. First, Definition 9 gives an adaptation of the notion of walk and path to the case of partial RAF, then Definition 10 defines the notion of connected elements in a partial RAF.
Definition 9. Let R˜A︁F = ⟨︁ A˜, K˜ , s˜, t˜, s, t⟩︁ be a partial RAF and e1, en ∈ ( A˜ ∪ K˜ ) be elements of R˜A︁F . A non-directed partial-RAF-walk is a sequence (e1, ..., en) with n ∈ N∗ and ∀i, ei ∈ (A ∪ K) s.t.: • If n > 1, ∀i ∈ {1, ..., n − 1}, ei ∈ A =⇒ s(ei+1) or (t˜(ei+1) = true and ei = t(ei+1))) ei+1 ∈ K and (s˜(ei+1) = true and ei = • If n > 1, ∀i ∈ {1, ..., n − 1}, ei ∈ K =⇒ (ei+1 ∈ A and ((s˜(ei) = true and s(ei) = ei+1) or (t˜(ei) = true and t(ei) = ei+1))) or (ei+1 ∈ K and ((t˜(ei+1) = true and ei = t(ei+1)) or (t˜(ei) = true and t(ei) = ei+1)))
A non-directed partial-RAF-path is a non-directed partial-RAF-walk in which all the elements are distinct.
Considering the RAF given in Figure 1, ( f , ε , δ , d) is an example of a non-directed partialRAF-path. Definition 10. Let R˜A︁F = ⟨︁ A˜, K˜ , s˜, t˜, s, t⟩︁ be a partial RAF. R˜A︁F is a connected partial RAF if, ˜ ˜ for all distinct elements xi ∈ A ∪ K˜ and x j ∈ A ∪ K˜ , there exists a non-directed partial-RAF-path p in R˜A︁F s.t. xi is the first element of p and x j is the last element of p. Otherwise the partial RAF is disconnected.
Considering the partial RAF obtained from the RAF given in Figure 1 by the removal of ξ , this partial RAF is disconnected since, for instance, none non-directed partial-RAF-path exists between f and k.
The very classical operator of restriction, denoted by ↓, can also be applied to partial RAF giving the partial RAF that is the restriction of a given partial RAF to a given set of elements (arguments and/or attacks). Then, using this operator, we can define the notion of “Partial RAF Connected Component”: Definition 11. Let R˜A︁F = ⟨︁ A˜, K˜ , s˜, t˜, s, t⟩︁ be a partial RAF. Let S ⊆ A˜ ∪ K˜ be a set of elements. The partial RAF R˜A︁F ↓S is a connected component of R˜A︁F iff: R˜A︁F ↓S is connected and there exists no set S′ ⊆ A˜ ∪ K˜ s.t. S ⊂ S′ and R˜A︁F ↓S′ is connected.
The RAFDivider algorithm we propose in this paper is an adaptation of the AFDivider algorithm
proposed in [
labellings labellings RAF RAF labellings labellings Initial RAF η g θe ζf ε δa α βb ρ mh κι λi ξ d γ c ψ o kl π
Partial Hard RAF a α b δd γ βc ? ρ mh κι ψ λi ξ o kl π
a α b δd γ βc ρ mh κι ψλi ξ o kl π
Before giving the formal definition of the algorithm, we describe its desired behaviour on a running example.
a α b δd γ βc ρ mh κι ψλi ξ o kl π 4.1. Preprocessing: Removing the Trivial Part The first step is to identify the trivial part to remove. Similarly to an AF, it is built using the in and out elements produced by the grounded semantics. In the case of an AF, these elements are all removed. However, for a RAF, this complete removal is not possible. Consider for instance the grounded labelling given in Example 1. If we remove all elements that are not labelled und as it was done in the case of an AF, the resultant partial RAF would not capture the initial relations between the elements (for instance, the relation between the arguments a and b is expressed by the attack α labelled in, so the removal of α is not possible). This leads to the following definition of the RAF trivial part: Definition 12. Let RAF = ⟨A, K, s, t⟩ be a RAF and let Lgr be the grounded labelling of RAF . The “trivial part” of RAF is the structure of RAF , denoted by Utriv = ⟨Striv, Qtriv⟩, with Striv = {a ∈ A|a ∈/ und(Lgr)} and Qtriv = {α ∈ K|α ∈ out(Lgr) or (α ∈ in(Lgr) and s(α ) ∈/ und(Lgr))} Example 2. Following Example 1, the trivial part of RAF is: Utriv = ⟨{e, f , g} , {ε , ζ , η , θ }⟩.
Then the partial hard RAF and partial hard RAF with input are defined as follows: Definition 13. Let RAF = ⟨A, K, s, t⟩ be a RAF and let Utriv = ⟨Striv, Qtriv⟩ be the RAF trivial part of RAF . The partial hard RAF of RAF , denoted by R˜A︁F hard , is defined as R˜A︁F hard = ︁⟨ A˜ , K˜ , s˜, t˜, sh, th⟩︁ with A˜ = A \ Striv, K˜ = K \ Qtriv, sh : K˜ → A s.t. ∀α ∈ K˜ , sh(α ) = s(α ) and th : K˜ → (A ∪ K) s.t. ∀α ∈ K˜ , th(α ) = t(α ) (s˜ and t˜ are defined as in Definition 3). The partial hard RAF with input is ⟨︂R˜A︁F hard , I = ⟨Sinp, Qinp⟩, Linp⟩︂, where Sinp = {s(α ) ∈ (A \ A˜)|α ∈ K˜ }, Qinp = ∅ and Linp is the grounded labelling of the elements in I.
Although a partial hard RAF is a partial RAF, we only consider the input labelling that coincides with the grounded labelling of the initial RAF. So the corresponding partial hard RAF with input is trivially unique, the labelling of its inputs being unique.
Example 3. Figure 3 illustrates R˜A︁F hard , the partial hard RAF corresponding to the RAF shown in Figure 1. In this partial hard RAF, two attacks have no source (λ and ξ ). This partial hard RAF has one input; so I = ⟨{ f }, ∅⟩ and Linp = {( f , in)}.
For each input element, several cases have to be considered and this can be very time consuming. In order to avoid this cost for elements that are in the “trivial part”, we simply cut that part from the a δ d α γ b β c ρ h m ξ o
π k l ι ψ ? λ i RAF and, only after that, look for clusters. So, given a RAF RAF = ⟨A, K, s, t⟩, the RAFDivider algorithm starts by computing Lgr, the grounded labelling of RAF and Utriv the trivial part corresponding to it. Once the trivial part has been computed, the algorithm removes it from RAF to produce R˜A︁F hard the partial hard RAF of RAF , as well as R˜A︁F hard input elements I with their labelling issued from Lgr. Then, if possible, R˜A︁F hard is split into several connected components (see Definition 10), producing the set CCSet. CCSet is a set of partial hard RAFs (with input). a δ d α γ b β c ρ h m κ ι
ξ f λ i ψ o
π k l (a) Component 1: r˜a︂f 1 (b) Component 2: r˜a︂f 2 Example 4. Figure 4 illustrates the two connected components of R˜A︁F hard , the partial hard RAF illustrated in Figure 3. The CCSet will then contain these two partial RAFs. 4.2. Identifying Clusters For each connected component, a clustering can be performed using any clustering method partitioning the partial RAF (even a random partition method). See in Section 6 such a method that returns the set of clusters identified, that is, a set of partial RAFs.
Example 5. Following Example 4, let us consider that the chosen clustering method produces only one cluster for component 1. Let r˜a︂f 2 be the other component and let the following partition be the one produced by the chosen clustering method:
Ω = {ω1 = {h, i, m, ι , κ , λ , ρ , ψ } , ω2 = {k, l, ξ , o, π }}
Figure 5 illustrates the partial RAFs corresponding to the partitioning of r˜a︂f 2, that is r˜a︂f 2 ↓ω1 8 (also denoted by r˜a︂f 2.1) and r˜a︂f 2 ↓ω2 (also denoted by r˜a︂f 2.2).
Note that, following this clustering, m and ψ also become inputs for r˜a︂f 2.2. Note also that this clustering must also take into account attacks and not only arguments (as it is the case for AFDivider). See in Section 6 an example of such a clustering. 4.3. Computing the Labellings The next step is the computation of the component labellings in a distributed way relying on the clustering made. The σ -labellings of each cluster are computed simultaneously. Unlike the case 8r˜a︂f 2 ↓ω1 produces a partial RAF built from r˜a︂f 2 keeping only the elements of ω1. (a) Cluster 1: r˜a︂f 2.1 = r˜a︂f 2 ↓ω1 (b) Cluster 2: r˜a︂f 2.2 = r˜a︂f 2 ↓ω2 of connected components, the partial RAF corresponding to the computed clusters may admit several input labellings. In order to compute all the possible σ -labellings of a given cluster, every possible case concerning its input elements has to be considered. We call “context” a particular input labelling of a partial RAF:9 Definition 14. Let R˜A︁F = ⟨︁ A˜ , K˜ , s˜, t˜, s, t⟩︁ be a partial RAF and I = ⟨︁ Sinp, Qinp⟩︁ be the input of R˜A︁F . A context µ of a partial RAF is a labelling of I.
Example 6. Following Figure 5, in the worst case, there exist 27 contexts of r˜a︂f 2.2 (3 inputs with 3 possible values, so 33 = 27 ). Nevertheless, some of these 27 contexts are not compatible with the labelling Lgr ( f must be labelled in). So only 9 contexts are compatible.
As one can notice from Example 6, it may be useless to consider some cluster contexts. So three optimizations can enhance the computation time: • First optimization: Given a cluster, if one of its input elements is also an input element of the partial hard RAF then this element should only be labelled as in the grounded labelling Lgr (see Example 6). • Second optimization: If an input attack is unattacked (a so-called valid attack) in the initial RAF, then this attack will always be labelled in following all semantics we are interested in.
Example 7. The attack ψ is an input of r˜a︂f 2.2 and a valid one in RAF and in R˜A︁F hard .
Hence, it is useless to consider contexts where ψ is not labelled in.
• Third optimization: Some contexts can lead to the same labellings. For instance, let us
consider an inward attack y, the context putting y to out, or the context putting s(y) to
outgive exactly the same labellings for t(y). This can be used in order to decrease the
number of contexts to consider (see [
For the component labelling reunification, a CSP (Constraint Satisfaction Problem) is created.
The aim is to identify the compatibility between the labellings of the elements that are in the
“interface” of clusters in the same component (see our technical report [
A special step has to be carried out for the preferred semantics as this reunifying process does
not ensure the maximality (w.r.t. ⊑) of the set of in-labelled elements. Indeed, the preferred
semantics is not bottom-up decomposable (see [
Now that all the component labellings are built, we can reunify the labellings of the whole RAF. Indeed, given that the trivial part is a fixed part of all σ -labellings of RAF and that each connected component has a unique context (these contexts being compatible with each other), the σ -labellings of the whole RAF are built by performing a simple cartesian product between the labellings of all the components and the trivial part labelling. If one of the components has no labelling then the whole RAF has no labelling (so Lσ = ∅).
Example 10. The complete semantics produces 18 labellings for the running example, with for instance the following labelling: ⎧ ⎫ ⎪⎪⎪⎪ (e, in), ( f , in), (g, out), (ε, out), (ζ , in), (η, in), (θ , in), ⎪⎪⎪⎪ ⎪⎨⎪ (a, in), (b, out), (c, in), (d, out), (α, in), (β , in), (γ, in), (δ , in), ⎪⎬⎪ ⎪⎪⎪⎪⎪ (i, out), (h, out), (m, in), (k, in), (l, out), ⎪⎪⎪⎪⎪ ⎩⎪ (ι, in), (κ, in), (λ , in), (ρ, in), (ψ, in), (ξ , out), (o, in), (π, in) ⎭⎪ (in this labelling, the first line corresponds to the grounded labelling for the trivial part, the second one is for r˜a︂f 1 and the two last lines are the labelling L2.1 given in Example 9 for r˜a︂f 2)
1 Utriv, Lgr ← Algorithms 1 and 2 give the formal definition of the RAFDivider algorithm. Similarly to AFDivider, they are said to be generic algorithms in the sense that any clustering method can be used to split the framework and any sound and complete procedure that computes the semantics σ , can be used to compute the labellings of the different clusters.
Algorithm 1: RAFDivider algorithm.
Input: Let RAF = ⟨A, K, s,t⟩ be a RAF and σ be a semantics Result: Lσ ∈ 2L (RAF ): the set of the σ -labellings of RAF
ComputeRAFTrivialPart(RAF ) 2 R˜A︁F hard, I ← RemoveRAFTrivialPart(RAF , Utriv) 3 CCSet ← SplitPartialRAFConnectedComponents(R˜A︁F hard) 4 for all r˜a︂f i ∈ CCSet do in parallel 5 PartRAFSet ← ComputePartRAFs(r˜a︂f i) // clustering 6 Lσ (r˜a︂f i) ← ComputeRAFCompLabs(σ , PartRAFSet, I, Lgr) 7 Lσ ← { Lgr ↓Utriv} × ∏r˜a︂f i∈CCSet Lσ (r˜a︂f i) 8 return Lσ Algorithm 2: ComputeRAFCompLabs algorithm.
Input: Let σ be a semantics, PartRAFSet be a set of clusters (partial RAFs) for a component r˜a︂f i, I be the input of the partial hard RAF and Lgr be the grounded labelling of the initial RAF
Result: Lσ ∈ 2L (r˜a︂f i): the set of the σ -labellings of r˜a︂f i 1 for all r˜a︂f i. j ∈ PartRAFSet do in parallel 2
Lσr˜a︂f i.j ← ComputePartRAFLabs(σ , r˜a︂f i. j, I, Lgr) 4 if σ = pr then Lσ ← { 5 return Lσ 3 Lσ ← ReunifyComp({Lσr˜a︂f i.j |r˜a︂f i. j ∈ PartRAFSet})
L|L ∈ Lσ s.t. ∄L′ ∈ Lσ s.t. in(L) ⊏ in(L′)} // using a CSP solver // external solver call
Before giving the properties of these algorithms, let us focus on two key elements of
Algorithm 2:
• ComputePartRAFLabs: this function contains the call to an external solver able to compute
the labellings of a given RAF. Such a trivial solver could be defined in three steps: (1)
translation of any RAF into an AF using the flattening proposed in [
The main idea of the clustering presented in this section is to ensure that the Strongly Connected
Components (SCC)11 are not split into different clusters. The following method is inspired by
those proposed in [
In the third step, each SCC that is not a singleton is joined with its neighbour SCC singletons (those that are neighbours with at least an element in the non-singleton SCC) producing a cluster. This merging must respect the following constraint (the idea is to put the attacks and their source in the same cluster in order to have all the necessary elements for identifying the status of the target): Definition 16. Let U SCCra f be a cluster. Let x be a singleton SCC that is a neighbour of U SCCra f . x will be joined with U SCCra f if either x ∈ K and s(x) ∈ U SCCra f or x ∈ A and ∃y ∈ U SCCra f s.t. s(y) = x.
The last step is to join clusters together so that there are not too many clusters of little size. This is done in an iterative way. The smallest group is merged to its smallest neighbour group, and that continues until there is no group of less than a certain number of arguments. Some experiments would be necessary in order to identify this threshold wrt the RAF that we take into account.
Using this method, we can retrieve the clustering proposed in Section 4.2 for the component
r˜a︂f 2 (two clusters: {λ , i, ι , m, ρ , h, κ , ψ } and {k, π , l, o, ξ }, see Figure 5).
10Note that this CSP contains two types of variables: one variable for each cluster and one variable for each input of
these clusters. The domains of these variables correspond to their possible labellings. The constraints express the
links between the labellings of the clusters and the labellings of their inputs.
11See in [
This paper presents RAFDivider, one of the first algorithms for the enumeration of acceptable sets in a Recursive Argumentation Framework (RAF), an argumentation framework enriched with higher-order attacks. This algorithm, proven sound and complete, is based on a cutting of the framework which allows a distributed and parallel computation, technique successfully used for the enumeration of acceptable sets in an AF by AFDivider. An example of a clustering method, USCC-clustering, which can be used with this algorithm, is provided. An implementation of RAFDivider is to come with an experimental evaluation of such algorithms.
The extension of the algorithmic approach to other kinds of enriched argumentation frameworks
may be investigated: argumentation frameworks which consider support interactions in addition
to attacks, notably (see [
To go further, such algorithms for argumentation frameworks with higher-order attacks may
encourage the extension to RAFs of the reasoning tasks proposed for AFs at the International
Competition on Computational Models of Argumentation (ICCMA) [
The authors wish to thank Mickaël Lafages, the work of this article being mostly based on his PhD Thesis.