=Paper=
{{Paper
|id=Vol-3236/paper4
|storemode=property
|title=Computing the Labellings of Higher-Order Abstract Argumentation Frameworks
|pdfUrl=https://ceur-ws.org/Vol-3236/paper4.pdf
|volume=Vol-3236
|authors=Sylvie Doutre,Marie-Christine Lagasquie-Schiex
|dblpUrl=https://dblp.org/rec/conf/comma/DoutreL22
}}
==Computing the Labellings of Higher-Order Abstract Argumentation Frameworks==
https://ceur-ws.org/Vol-3236/paper4.pdf
Computing the Labellings of Higher-Order Abstract
Argumentation Frameworks
Sylvie Doutre1 , Marie-Christine Lagasquie-Schiex2,∗∗
1 IRIT, Toulouse 1 University, France
2 IRIT, Toulouse 3 University, France
Abstract
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.
Keywords
Abstract Argumentation, Higher-Order Interactions, Algorithms
1. Motivation
Argumentation, by considering arguments and their interactions, is a way of reasoning that has
proven successful in many contexts, multi-agent applications for instance (e.g. [1]). Considering
a formal representation of this reasoning model, argumentation frameworks with higher-order
attacks (e.g. [2, 3, 4, 5, 6]) are a rich extension of the classical Argumentation Framework
(AF) by [7]: not only they consider arguments and attacks between arguments, but also attacks
on attacks (see for instance [5, 6]). Among these frameworks, the Recursive Argumentation
Framework (RAF) by [8] proposes a direct approach regarding acceptability, which outputs sets of
arguments and/or attacks (defined under the notion of structure), keeping the full expressiveness
of higher-order attacks. A correspondence between Dung’s extension-based semantics for AFs
and structure-based semantics of RAFs without any attack on attacks has been shown in [8],
proving that RAFs are a conservative generalisation of AFs. This characteristic makes RAFs
particularly interesting to consider.
The computation of semantics of RAFs has not been addressed so far but a simple way
to do so can be to extend what is done for AFs: some of the most efficient algorithms for
computing AF semantics are based on a cutting of the AF and then on a distributed and parallel
SAFA’22: Fourth International Workshop on Systems and Algorithms for Formal Argumentation 2022, September 13,
2022, Cardiff, Wales, United Kingdom
∗∗ Corresponding author.
$ doutre@irit.fr (S. Doutre); lagasq@irit.fr (M. Lagasquie-Schiex)
© 2022 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
CEUR
Workshop
Proceedings
http://ceur-ws.org
ISSN 1613-0073
CEUR Workshop Proceedings (CEUR-WS.org)
45
Sylvie Doutre et al. CEUR Workshop Proceedings 45–58
computation (see [9, 10, 11, 12]) using the notion of AF labellings (e.g. [13, 14])1 and the
fact that such semantics are decomposable (see [16]). Indeed, RAF labellings already exist
and classical decision problems for AFs were also adapted to RAFs with an interesting result
(see [17]): even if the expressive power of the frameworks with higher-order attacks is higher,
the complexity of their decision problems remains the same as in an AF. Moreover, it has been
proven in [18] that RAF semantics, as AF semantics, are decomposable. Thus, following the line
of the AFDivider algorithm designed for AFs [12], all the mandatory elements are now present
for the definition of some efficient algorithms for computing RAF labellings using a distributed
and parallel method; this is the topic of the present paper.
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 [19].
2. Background on Recursive Argumentation Frameworks
Higher-order attacks (that is, possibly targeting attacks as well as arguments) have been introduced
in [2] then developed in several papers among which one can cite the AFRA (Argumentation
Framework with Recursive Attacks) approach described in [6] and the RAF (Recursive Argu-
mentation Framework) approach introduced in [8]. RAF and AFRA differ on the way in which
these attacks are handled despite the fact that there is no difference in the structure of the graph.
This paper is concerned with the RAF approach. This section recalls its main definitions: basics,
labellings and decomposability of the semantics.
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.
Figure 1 shows an example of a RAF. There are two different possibilities for defining the
semantics of a RAF: either by selecting some specific structures (a pair composed of a set of
arguments and a set of attacks) [8] or by using labellings [17].2 Here we only present the latter
approach.3
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 [15] for a survey).
2 Relations between labelling-based semantics and structure-based semantics have been exhibited in [17].
3 These labellings were called “structure labellings” in [17] and defined as a pair of sets (the labellings for arguments,
the labellings for attacks). Here the definition and the name are simplified.
46
Sylvie Doutre et al. CEUR Workshop Proceedings 45–58
η e a α b
ζ
g θ f ε δ β
h κ λ d γ c
ξ
ρ
m ι i k
o π
ψ l
Figure 1: Running example: a RAF with argument names given in a circle and attack names in a square
box
• (L(x) = out) ⇐⇒ (∃α ∈ K s.t. t(α) = x, L(α) = in and L(s(α)) = in)
• (L(x) = in) ⇐⇒ (∀α ∈ K s.t. t(α) = x, L(α) = out or L(s(α)) = out)
Let x ∈ A ∪ K be an element of RAF . x is said to be legally labelled in L iff L is a complete
labelling and x ∈ und(L) iff ((∄α ∈ K s.t. t(α) = x, L(α) = in and L(s(α)) = in) and (∃α ∈
K s.t. t(α) = x, L(α) ̸= out and L(s(α)) ̸= out)). L is said to be a valid RAF labelling if all
its elements are legally labelled. A preferred (resp. grounded) labelling is a complete labelling
that maximises (resp. minimises) the in elements. A stable labelling is a complete labelling for
which there are no und elements.
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 problem4 in the case of a RAF,
similarly to the one given for an AF (AFDivider [12]), we must be able to split a RAF. Based
on the notion introduced in [16], any AF can be split into several sub-frameworks by simply
ignoring some attacks (that are always valid). Nevertheless, it is not the case for RAFs. Attacks,
as arguments, can be labelled in, out or und. As a consequence, we cannot just ignore attacks to
split a RAF. So, if we do not suppress attacks while splitting RAFs, we will have attacks without
targets or without sources. Thus, the result of such a split does not produce a RAF but a partial
RAF.
4 The enumeration problem consists in enumerating all the solutions under a given semantics of a framework; see [20]
for more details on this problem.
47
Sylvie Doutre et al. CEUR Workshop Proceedings 45–58
⟨︁ ⟩︁
Definition 3. Let RAF = ⟨A, K, s,t⟩ be a RAF. A partial RAF RAF
˜︁ = Ã, K̃, s̃,t̃, s,t of RAF is a
tuple where à ⊆ A (resp. K̃ ⊆ K) is a set representing arguments (resp. attacks) and:
• s̃ : K̃ → {true, false} s.t. ∀α ∈ K̃, s̃(α) = true if s(α) ∈ Ã otherwise false
• t̃ : K̃ → {true, false} s.t. ∀α ∈ K̃,t̃(α) = true if t(α) ∈ Ã ∪ K̃ otherwise false
Then, using the notion of partial RAF, a partition of a RAF can be defined:
Definition 4. Let RAF = ⟨A, K, s,t⟩ be a RAF. Let Ω = {ω1 , ..., ωn } be a partition5 of
⟨︁ ∪ K). A RAF⟩︁ partition of RAF is a set of partial RAFs {RAF 1 , ..., RAF n } s.t.: ∀i, RAF i =
(A ˜︁ ˜︁ ˜︁
Ãi , K̃ i , s̃i ,t̃ i , s,t with Ãi = ωi ∩ A and K̃ i = ωi ∩ K.
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 RAF
˜︁ = ⟨Ã, K̃, s̃, t̃, s, t⟩ be a partial RAF of
RAF . The input I of RAF
⟨︁ inp inp ⟩︁
˜︁ is a tuple S , Q where: Sinp = {s(α)
⟨︂ ∈ (A \ Ã)|α ⟩︂ ∈ K and t(α) ∈
(Ã ∪ K̃)} and Q = {α ∈ (K \ K̃)|t(α) ∈ (Ã ∪ K̃)}. The tuple RAF , I, L
inp ˜︁ inp 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
⟨︂ Let σ be a semantics. A local function Fσra f assigns to any partial RAF with input
6. ⟩︂
RAF ˜︁ under σ , i.e. Fσra f (RAF
˜︁ , I, Linp a (possibly empty) set of labellings of RAF ˜︁ , I, Linp ) ∈
2{L|L being any labelling over RAF
˜︁ }
.
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 {RAF ˜︁ n } of RAF , the set of all possible
˜︁ 1 , ..., RAF
labellings under the semantics σ of RAF , denoted by Lσ (RAF ), satisfies: Lσ (RAF ) = {L1 ∪
... ∪ Ln |∀i ∈ {1, ..., n}, Li ∈ Fσra f (RAF
˜︁ i , Ii , Linp inp
i )} with Li = ( 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 (RAF
˜︁ i , Ii , Linp
i )}
In [18], a specific RAF partition selector has been defined that produces a partition respecting
the strongly connected components (SCC) of a RAF:7
n
5 So the following property holds for Ω: ∀(i, j) ∈ {1, ..., n} s.t. i ̸= j, ω ∩ ω = ∅ and ⋃︁ ω = A ∪ K.
i j i
i=1
6 ↓ is the classical generic operator of restriction that allows the selection of a sub-part of a given “object” wrt to a
given set of “elements”. Here for instance, it produces the sub-part of the labellings concerning only the elements
belonging to Ii .
7 See in [18] the details about the method for defining the SCC of a RAF.
48
Sylvie Doutre et al. CEUR Workshop Proceedings 45–58
Definition 8. Let RAF be a RAF. Let Sra f -USCC be the RAF partition selector s.t.:
Sra f -USCC (RAF ) = {Ω| Ω is a partition of RAF and ∀S ∈ SCCSra f (RAF ), ∃ωi ∈ Ω s.t. S ⊆ ωi }.
Let S ⊆ A ∪ K s.t. S ∈ Sra f -USCC (RAF ), S is called an “USCCra f ”.
Then, in [18], the following proposition has been proven:
Proposition 1. Let RAF = ⟨A, K, s,t⟩ be any RAF. The semantics properties in Table 1 hold.
RAF semantics
complete grounded preferred stable
Full decomposability × ×
Top-down decomposability
Bottom-up decomposability × ×
Full decomposability w.r.t. Sra f -USCC
(so Top-down and Bottom-up decomposability)
×”) means that the semantics on the column has (resp. does not have) the property on the
“ ” (resp. “×
row.
Table 1
RAF Semantics decomposability properties
3. Some Preliminary Definitions
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.
⟨︁ ⟩︁
˜︁ = Ã, K̃, s̃,t̃, s,t be a partial RAF and e1 , en ∈ (Ã ∪ K̃) be elements of
Definition 9. Let RAF
˜︁ . A non-directed partial-RAF-walk is a sequence (e1 , ..., en ) with n ∈ N∗ and ∀i, ei ∈ (A ∪ K)
RAF
s.t.:
• If n > 1, ∀i ∈ {1, ..., n − 1}, ei ∈ A =⇒ ei+1 ∈ K and (s̃(ei+1 ) = true and ei =
s(ei+1 ) or (t̃(ei+1 ) = true and ei = t(ei+1 )))
• 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 partial-
RAF-path.
49
Sylvie Doutre et al. CEUR Workshop Proceedings 45–58
⟨︁ ⟩︁
Definition 10. Let RAF
˜︁ = Ã, K̃, s̃,t̃, s,t be a partial RAF. RAF ˜︁ is a connected partial RAF if,
for all distinct elements xi ∈ Ã ∪ K̃ and x j ∈ Ã ∪ K̃, there exists a non-directed partial-RAF-path
p in RAF
˜︁ 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”:
⟨︁ ⟩︁
˜︁ = Ã, K̃, s̃,t̃, s,t be a partial RAF. Let S ⊆ Ã ∪ K̃ be a set of elements.
Definition 11. Let RAF
˜︁ ↓S is a connected component of RAF
The partial RAF RAF ˜︁ ↓S is connected and there
˜︁ iff: RAF
′ ′
exists no set S ⊆ Ã ∪ K̃ s.t. S ⊂ S and RAF
˜︁ ↓S′ is connected.
4. A Generic Algorithm for computing RAF semantics:
Presentation by Example
The RAFDivider algorithm we propose in this paper is an adaptation of the AFDivider algorithm
proposed in [12]. Similarly to AFDivider, it addresses the enumeration problem for the complete,
stable and preferred semantics (finding all the possible solutions of a given semantics for a given
RAF). It follows the same four major steps (see Figure 2):
1. A preprocessing on RAF removes “trivial” parts of it.
2. Clusters in RAF are identified.
3. The labellings under semantics σ in each cluster are computed in parallel.
4. The results of each cluster are reunified to get the labellings of RAF .
Partial Component Hard Initial
Components Cluster
Initial RAF Hard RAF pClustersp labellings RAF RAF
labellings
a α b a α b
labellings labellings
δ β δ β
d γ c d γ c
a α b
e a δ β
η α b
ζ
g d γ c
θ f ε δ β
h κ λ d γ c
ξ ?
ρ h κ λ
ρ
m ι i k
h κ λ m
o π ξ ι i
ρ
ψ l m ι i k ψ
o π
ψ
l
h κ λ
ξ
ρ
m ι i k
o π
ψ l
ξ
k
o π
l
Step 1 Step 2 Step 3 Step 4
Figure 2: RAFDivider operating diagram
Before giving the formal definition of the algorithm, we describe its desired behaviour on a
running example.
50
Sylvie Doutre et al. CEUR Workshop Proceedings 45–58
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 RAF hard , is defined as RAF hard =
˜︁ ˜︁
Ã, K̃, s̃,t̃, sh ,th with à = 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 RAF ˜︁ hard , I = ⟨S , Q ⟩, L
inp inp inp , where Sinp = {s(α) ∈
(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 RAF
˜︁ 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)}.
?
a α b
h κ λ
ξ
ρ
δ β
m ι i k
γ c o π
d ψ
l
Figure 3: Partial Hard RAF (the attacks λ and ξ have no source)
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
51
Sylvie Doutre et al. CEUR Workshop Proceedings 45–58
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
˜︁ hard the partial hard RAF of RAF , as well as RAF
to produce RAF ˜︁ hard input elements I with their
labelling issued from Lgr . Then, if possible, RAF hard is split into several connected components
˜︁
(see Definition 10), producing the set CCSet. CCSet is a set of partial hard RAFs (with input).
f
a α b h κ λ
ξ
ρ
δ β m ι i k
o π
d γ c ψ l
(a) Component 1: raf
˜︂
1 (b) Component 2: raf
˜︂
2
Figure 4: The connected components of RAF
˜︁ hard with their inputs (raf
˜︂ has no input; raf
1
˜︂ has one
2
input f )
Example 4. Figure 4 illustrates the two connected components of RAF
˜︁ 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 raf
˜︂ be the other component and let the following partition
2
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 raf ˜︂ ↓ω 8
˜︂ , that is raf
2 2 1
(also denoted by raf
˜︂ ) and raf˜︂ ↓ω (also denoted by raf ˜︂ ).
2.1 2 2 2.2
Note that, following this clustering, m and ψ also become inputs for raf ˜︂ . Note also that
2.2
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
8 raf
2 ↓ω1 produces a partial RAF built from raf 2 keeping only the elements of ω1 .
˜︂ ˜︂
52
Sylvie Doutre et al. CEUR Workshop Proceedings 45–58
f
h κ λ f
ρ
m ι i
ξ
m k
ψ
ψ o π
l
(a) Cluster 1: raf
˜︂ = raf˜︂ ↓ω (b) Cluster 2: raf
˜︂ = raf˜︂ ↓ω
2.1 2 1 2.2 2 2
Figure 5: Clusters of raf
˜︂ (the inputs m and ψ for raf
2
˜︂ are given in blue since their labellings are
2.2
unknown at this time; whereas f is in green since its labelling is known: following Lgr , f must be in)
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
˜︁ = Ã, K̃, s̃,t̃, s,t be a partial RAF and I = Sinp , Qinp be the input of
⟨︁ ⟩︁ ⟨︁ ⟩︁
Definition 14. Let RAF
˜︁ . A context µ of a partial RAF is a labelling of I.
RAF
Example 6. Following Figure 5, in the worst case, there exist 27 contexts of raf
˜︂ (3 inputs with
2.2
3
3 possible values, so 3 = 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 raf ˜︂ and a valid one in RAF and in RAF
2.2
˜︁ 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 [19] for more details).
9 Obviously, each context of a partial RAF will induce a specific set of labellings of this partial RAF.
53
Sylvie Doutre et al. CEUR Workshop Proceedings 45–58
Example 8. Applying the previous optimizations on the running example leads to 3 (resp. 3, 6)
complete labellings for raf
˜︂ (resp. raf
1
˜︂ , raf
2.1
˜︂ ) with 1 (resp. 1, 3) context. For instance, among
2.2
the 3 (resp. 6) labellings for raf
˜︂ (resp. raf˜︂ ), we have L2.1.1 = {(i, out), (h, out), (m, in),
2.1 2.2
(ι, in), (κ, in), (λ , in), (ρ, in), (ψ, in)} (resp. L2.2.1 = {(k, in), (l, out), (ξ , out), (o, in),
(π, in)}).
4.4. Reunifying the Results
The labelling reunifying process is made in two steps: first, the reunification of the component
labellings (i.e. the reunification of their cluster labellings together) and second, the reunification
of the whole RAF labellings (i.e. the reunification of its component labellings together).
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 [19] for details).
Example 9. The reunification of the 3 labellings of raf ˜︂ with the 6 labellings of raf
2.1
˜︂ produces
2.2
6 labellings for the component raf ˜︂ . And L2.1 = {(i, out), (h, out), (m, in), (k, in), (l, out),
2
(ι, in), (κ, in), (λ , in), (ρ, in), (ψ, in), (ξ , out), (o, in), (π, in)} is one of them (built from
the labellings given in Example 8: L2.1.1 for raf˜︂ and L2.2.1 for raf
2.1
˜︂ ).
2.2
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 [16]). A maximality check must be done in order
to keep only the wanted labellings. Moreover, when computing the stable semantics, the set of
labellings Lσ returned by the algorithm may be empty. It happens when one of the component
clusters has no stable labelling.
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
˜︂ and the two last lines are the labelling L2.1 given in Example 9 for raf
second one is for raf ˜︂ )
1 2
54
Sylvie Doutre et al. CEUR Workshop Proceedings 45–58
5. RAFDivider: Algorithms and Properties
Algorithms 1 and 2 give the formal definition of the RAFDivider algorithm. Similarly to AFDi-
vider, 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
1 Utriv , Lgr ← ComputeRAFTrivialPart(RAF )
˜︁ hard , I ← RemoveRAFTrivialPart(RAF , Utriv )
2 RAF
3 CCSet ← SplitPartialRAFConnectedComponents(RAF ˜︁ hard )
4 for all raf i ∈ CCSet do in parallel
˜︂
5 PartRAFSet ← ComputePartRAFs(raf ˜︂ )
i // clustering
6 Lσ (raf i ) ← ComputeRAFCompLabs(σ , PartRAFSet, I, Lgr )
˜︂
7 Lσ ← {Lgr ↓Utriv } × ∏ ˜︂ L (raf
˜︂ )
raf ∈CCSet σ
i
i
8 return Lσ
Algorithm 2: ComputeRAFCompLabs algorithm.
Input: Let σ be a semantics, PartRAFSet be a set of clusters (partial RAFs) for a
component raf˜︂ , I be the input of the partial hard RAF and Lgr be the grounded
i
labelling of the initial RAF
Result: Lσ ∈ 2L (raf i ) : the set of the σ -labellings of raf
˜︂ ˜︂
i
˜︂ ∈ PartRAFSet do in parallel
1 for all raf i. j
raf
Lσ i. j ← ComputePartRAFLabs(σ , raf
˜︂ , I, Lgr )
˜︂
2 i. j // external solver call
raf
3 Lσ ← ReunifyComp({Lσ
˜︂
i. j ˜︂
|raf i. j ∈ PartRAFSet}) // using a CSP solver
4 if σ = pr then Lσ ← {L|L ∈ Lσ s.t. ∄L ∈ Lσ s.t. in(L) ⊏ in(L′ )}
′
5 return Lσ
Before giving the properties of these algorithms, let us focus on two key elements of Algo-
rithm 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 [18] then (2) computation
of the labellings of this AF using any solver defined for AF (as the ones used for the
ICCMA competition [21]) and finally (3) computation of the RAF labellings from these
AF labellings using the properties that give the links between these AF labellings and
the labellings of the initial RAF (see [18]). Another kind of solver could be built in two
steps: (1) direct translation of a RAF into a logical base then (2) computation of the RAF
semantics using the logical models of this base (see [22, 23]).
55
Sylvie Doutre et al. CEUR Workshop Proceedings 45–58
• ReunifyComp: this function is in charge of aggregating the labellings obtained for each
cluster in order to obtain the labellings of the component containing these clusters (see
Section 4.4). This aggregation, called reunification, must respect the compatibility of the
resulting labellings; this is done in two steps: (1) creation of a CSP, then (2) resolution of
this CSP using any CSP solver. The precise definition of this CSP is given in [19].10
The RAFDivider algorithm gives all the expected labellings (so it is complete) and only good
labellings (it is sound) for the complete, stable and preferred semantics. The proof of the following
proposition is given in [19]. It is very similar to the proofs given for AFDivider in [18].
Proposition 2. Algorithms 2 and 1 are complete and sound for the stable, complete and preferred
semantics.
6. A Clustering Method
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 [12, 18] for testing the AFDivider algorithms. Given a RAF, the so-called
“USCC-clustering” forms clusters as follows (each cluster being an USCCra f , see Definition 8).
First, the set of SCC is computed. Then neighbour SCC singletons are joined together in order to
form a cluster using the following definition of neighbourhood:
Definition 15. Let RAF = ⟨A, K, s,t⟩. Let x and y be two elements of RAF . x and y are considered
as neighbour iff: either [x ∈ K and (y = s(x) or y = t(x))] or [x ∈ A and y ∈ K and (s(y) = x or
t(y) = x)].
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 USCCra f be a cluster. Let x be a singleton SCC that is a neighbour of USCCra f .
x will be joined with USCCra f if either x ∈ K and s(x) ∈ USCCra f or x ∈ A and ∃y ∈ USCCra 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
raf 2 (two clusters: {λ , i, ι, m, ρ, h, κ, ψ} and {k, π, l, o, ξ }, see Figure 5).
˜︂
10 Note 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.
11 See in [18] the details about the definition of the SCCs for a RAF.
56
Sylvie Doutre et al. CEUR Workshop Proceedings 45–58
7. Conclusion and Future Works
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 [24] for an overview of such enrichments).
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) [21]. It would be the
opportunity to define some benchmarks adapted to the higher-order frameworks that could be
taken into account in the experimental evaluation previously mentioned.
Acknowledgments
The authors wish to thank Mickaël Lafages, the work of this article being mostly based on his
PhD Thesis.
References
[1] Á. Carrera, C. A. Iglesias, A systematic review of argumentation techniques for multi-agent
systems research, Artificial Intelligence Review 44 (2015) 509–535.
[2] H. Barringer, D. Gabbay, J. Woods, Temporal dynamics of support and attack networks:
From argumentation to zoology, in: Mechanizing Mathematical Reasoning, Essays in Honor
of Jörg H. Siekmann on the Occasion of His 60th Birthday. LNAI 2605, Springer Verlag,
2005, pp. 59–98.
[3] S. Modgil, An abstract theory of argumentation that accommodates defeasible reasoning
about preferences, in: Proc. of ECSQARU, 2007, pp. 648–659.
[4] S. Modgil, Reasoning about preferences in argumentation frameworks, Artificial Intelligence
173 (2009) 901–934.
[5] P. Baroni, F. Cerutti, P. E. Dunne, M. Giacomin, Computing with infinite argumentation
frameworks: The case of AFRAs, in: Proc. of TAFA, Revised Selected Papers, 2011, pp.
197–214.
[6] P. Baroni, F. Cerutti, M. Giacomin, G. Guida, AFRA: Argumentation framework with
recursive attacks, Intl. Journal of Approximate Reasoning 52 (2011) 19–37.
[7] P. Dung, On the acceptability of arguments and its fundamental role in nonmonotonic
reasoning, logic programming and n-person games, Artificial Intelligence 77 (1995) 321–
357.
57
Sylvie Doutre et al. CEUR Workshop Proceedings 45–58
[8] C. Cayrol, J. Fandinno, L. Fariñas del Cerro, M.-C. Lagasquie-Schiex, Valid attacks in
argumentation frameworks with recursive attacks, AMAI Journal 89 (2020) 53–101.
[9] F. Cerutti, M. Giacomin, M. Vallati, M. Zanella, An SCC recursive meta-algorithm for
computing preferred labellings in abstract argumentation, in: Proc. of KR, AAAI Press,
2014, pp. 42–51.
[10] W. Dvořák, R. Pichler, S. Woltran, Towards fixed-parameter tractable algorithms for abstract
argumentation, Artificial Intelligence 186 (2012) 1–37.
[11] B. Liao, Toward incremental computation of argumentation semantics: A decomposition-
based approach, Annals of Mathematics and Artificial Intelligence 67 (2013) 319–358.
[12] S. Doutre, M. Lafages, M.-C. Lagasquie-Schiex, A distributed and clustering-based algo-
rithm for the enumeration problem in abstract argumentation, in: Proc. of PRIMA, Springer,
2019, pp. 87–105.
[13] M. Caminada, On the issue of reinstatement in argumentation, in: JELIA, 2006, pp.
111–123.
[14] P. Baroni, M. Caminada, M. Giacomin, An introduction to argumentation semantics,
Knowledge Eng. Review 26 (2011) 365–410.
[15] G. Charwat, W. Dvořák, S. A. Gaggl, J. P. Wallner, S. Woltran, Methods for solving
reasoning problems in abstract argumentation — A survey, Artificial Intelligence 220
(2015) 28–63.
[16] P. Baroni, G. Boella, F. Cerutti, M. Giacomin, L. Van Der Torre, S. Villata, On the
input/output behavior of argumentation frameworks, Artificial Intelligence 217 (2014)
144–197.
[17] S. Doutre, M. Lafages, M.-C. Lagasquie-Schiex, Argumentation Frameworks with Higher-
Order Attacks: Labellings and Complexity, in: M. Alamaniotis, S. Pan (Eds.), Proc. of
ICTAI, IEEE, 2020, pp. 1210–1217.
[18] M. Lafages, Algorithms for Enriched Abstract Argumentation Frameworks for Large-
scale Cases, Phd thesis, Toulouse University, Toulouse, France, 2021. URL: https://tel.
archives-ouvertes.fr/tel-03664752.
[19] S. Doutre, M.-C. Lagasquie-Schiex, RAFDivider, Research Report IRIT/RR–2022–07–FR,
IRIT - Institut de recherche en informatique de Toulouse, 2022.
[20] W. Dvorak, P. E. Dunne, Computational problems in formal argumentation and their
complexity, in: Handbook of formal argumentation, College publication, 2018, pp. 631–
688.
[21] ICCMA, International Competition on Computational Models of Argumentation, 2021.
URL: http://argumentationcompetition.org.
[22] P. Besnard, C. Cayrol, M.-C. Lagasquie-Schiex, Logical theories and abstract argumentation:
A survey of existing works, Argument and Computation 11 (2020) 41–102.
[23] C. Cayrol, M.-C. Lagasquie-Schiex, Logical Encoding of Argumentation Frameworks
with Higher-order Attacks and Evidential Supports, International Journal on Artificial
Intelligence Tools 29 (2020) 2060003. URL: https://hal.archives-ouvertes.fr/hal-02874146.
[24] C. Cayrol, A. Cohen, M. Lagasquie-Schiex, Higher-order interactions (bipolar or not) in
abstract argumentation: A state of the art, in: Handbook of Formal Argumentation, Volume
2, College Publications, 2021, pp. 3–118.
58