In the current paper, we evaluate the performance of di erent computational approaches for constructing a strongly admissible labelling for a particular argument. Unlike previous work, which examined di erent approaches for constructing a small strongly admissible labelling for a particular argument, in the current paper we are interested in constructing an arbitrary strongly admissible labelling for a particular argument, without any constraints regarding the size of such a labelling. A strongly admissible labelling relies on its associated min-max numbering to show that it is actually strongly admissible. As such, we also examine the additional computational costs of constructing such a min-max numbering. Overall, our analysis leads to a clear recommendation regarding which of the current computational approaches is best t for purpose.
In formal argumentation, one would sometimes like to show that a particular argument is (credulously) accepted according to a particular argumentation semantics, without having to construct the entire extension the argument is contained in. For instance, to show that an argument is in a preferred extension, it is not necessary to construct the entire preferred extension. Instead, it is su cient to construct a set of arguments that is admissible. Similarly, to show that an argument is in the grounded extension, it is not necessary to construct the entire grounded extension. Instead, it is su cient to construct a set of arguments that is strongly admissible.
The concept of strong admissibility was introduced by Baroni and Giacomin [
A strongly admissible set (or labelling) can be used to explain that a particular argument is in
the grounded extension (for instance, by using the discussion game of [
In previous work [
In the current paper, we examine two additional questions that were not examined in [
The current paper is structured as follows. First, in Section 2 we brie y reiterate some of
the theory regarding strongly admissible sets and strongly admissible labellings. In order to
make the paper self-contained, we also include the algorithms stated in [
In the current section, we brie y restate some of the basic concepts in formal argumentation theory, including strong admissibility. For current purposes, we restrict ourselves to nite argumentation frameworks.
De nition 1. An argumentation framework is a pair (Ar , att ) where Ar is a nite set of entities, called arguments, whose internal structure can be left unspeci ed, and att is a binary relation on Ar . For any x, y 2 Ar we say that x attacks y i (x, y) 2 att .
As for notation, we use lower case letters at the end of the alphabet (such as x, y and z) to denote variables containing arguments, upper case letters at the end of the alphabet (such as X, Y and Z) to denote program variables containing arguments, and upper case letters at the start of the alphabet (such as A, B and C) to denote concrete instances of arguments.
When it comes to de ning argumentation semantics, one can distinguish the extension
approach and the labelling approach [
De nition 3. Let (Ar , att ) be an argumentation framework. Args ✓ Ar is • an admissible set i Args is con ict-free and Args ✓ F (Args) • a complete extension i Args is con ict-free and Args = F (Args) • a grounded extension i Args is the smallest (w.r.t. ✓ ) complete extension
As mentioned in the introduction, the concept of strong admissibility was originally
introduced by Baroni and Giacomin [
De nition 4. Let (Ar , att ) be an argumentation framework. Args ✓ Ar is strongly admissible i every x 2 Args is defended by some Args0 ✓ Args \ {x} which in its turn is again strongly admissible.
It can be shown that each strongly admissible set is con ict-free and admissible [
The above de nitions essentially follow the extension based approach as described in [
De nition 5. Let (Ar , att ) be an argumentation framework. An argument labelling is a function Lab : Ar ! { in, out, undec}. An argument labelling is called an admissible labelling i for each x 2 Ar it holds that: • if Lab(x) = in then for each y that attacks x it holds that Lab(y) = out • if Lab(x) = out then there exists a y that attacks x such that Lab(y) = in Lab is called a complete labelling i it is an admissible labelling and for each x 2 Ar it also holds that: • if Lab(x) = undec then there is a y that attacks x such that Lab(y) = undec, and for each y that attacks x such that Lab(y) 6= undec it holds that Lab(y) = out
As a labelling is essentially a function, we sometimes write it as a set of pairs. Also, if Lab is
a labelling, we write in(Lab) for {x 2 Ar | Lab(x) = in}, out(Lab) for {x 2 Ar | Lab(x) =
out} and undec(Lab) for {x 2 Ar | Lab(x) = undec}. As a labelling is also a partition of
the arguments into sets of in-labelled arguments, out-labelled arguments and undec-labelled
arguments, we sometimes write it as a triplet (in(Lab), out(Lab), undec(Lab)).
De nition 6 ([
De nition 7. Let Lab be a complete labelling of argumentation framework (Ar , att ). Lab is said to be the grounded labelling i Lab is the (unique) smallest (w.r.t. v) complete labelling.
We refer to the size of a labelling Lab as |in(Lab)[ out(Lab)|. We observe that if Lab v Lab0 then the size of Lab is smaller or equal to the size of Lab0, but not necessarily vice versa. In the remainder of the current paper, we use the terms smaller, bigger, minimal and maximal in relation to the size of the respective labellings, unless stated otherwise.
The next step is to de ne a strongly admissible labelling. In order to do so, we need the
concept of a min-max numbering [
De nition 8. Let Lab be an admissible labelling of argumentation framework (Ar , att ). A min-max numbering is a total function MMLab : in(Lab) [ out(Lab) ! N [ {1} such that for each x 2 in(Lab) [ out(Lab) it holds that: • if Lab(x) = in then MMLab(x) = max({MMLab(y) | y attacks x and Lab(y) = out}) + 1 (with max(; ) de ned as 0) • if Lab(x) = out then MMLab(x) = min({MMLab(y) | y attacks x and Lab(y) = in}) + 1 (with min(; ) de ned as 1 )
It has been proved that every admissible labelling has a unique min-max numbering [
De nition 9. A strongly admissible labelling is an admissible labelling whose min-max numbering yields natural numbers only (so no argument is numbered 1 ).
It has been shown that the strongly admissible labellings form a lattice (w.r.t. v), of which
the all-undec labelling is the bottom element and the grounded labelling is the top element [
The relationship between extensions and labellings has been well-studied [
Now that the formal preliminaries have been stated, the next step is to include the algorithms
from [
Input: An argumentation framework AF = (Ar , att), an argument A 2 Ar that is in the grounded extension of AF .
Output: A strongly admissible labelling Lab where A 2 in(Lab), the associated min-max numbering MMLab. 1: Lab : Ar ! { in, out, undec} // We start with the type de nitions 2: MMLab : in(Lab) [ out(Lab) ! N [ {1} 3: undec_pre : Ar ! N 4: unproc_in : [X1, ...Xn] (Xi 2 Ar for each 1 i n) // list of arguments 5: unproc_in [] // We initialize and process the arguments that have no attackers 6: for each X 2 Ar do 7: Lab(X) undec 8: undec_pre(X) | X | 9: if undec_pre(X) = 0 then 10: add X to the rear of unproc_in 11: Lab(X) in 12: MMLab(X) 1 13: if X = A then return Lab and MMLab 14: end if 15: end for 16: while unproc_in is not empty do // We now process the arguments that do have attackers 17: let X be the argument at the front of unproc_in 18: remove X from unproc_in 19: for each Y 2 X+ with Lab(Y ) 6= out do 20: Lab(Y ) out 21: MMLab(Y ) MM Lab(X) + 1 22: for each Z 2 Y + with Lab(Z) = undec do 23: undec_pre(Z) undec_pre(Z) 1 24: if undec_pre(Z) = 0 then 25: add Z to the rear of unproc_in 26: Lab(Z) in 27: MMLab(Z) MM Lab(Y ) + 1 28: if Z = A then return Lab and MMLab 29: end if 30: end for 31: end for 32: end while 2) then takes the output of the rst algorithm and tries to prune it. That is, it tries to identify only those in and out labelled arguments that are actually needed in the strongly admissible labelling. The third algorithm (Algorithm 3) then combines Algorithm 1 (which is used as the construction phase) and Algorithm 2 (which is used as the pruning phase). Overall, we assume
Algorithm 2 Prune a strongly admissible labelling that labels A in and its associated min-max numbering.
Input: An argumentation framework AF = (Ar , att ), an argument A 2 Ar that is in the grounded extension of AF , A strongly admissible labelling LabI where A 2 in(LabI ), the associated min-max numbering MMLabI . Output: A strongly admissible labelling LabO v LabI where A 2 in(LabO), the associated min-max numbering MMLabO. 1: // We start with the type de nitions 2: LabO : Ar ! { in, out, undec} 3: MMLabO : in(LabO) [ out(LabO) ! N [ {1} 4: unproc_in : [X1, ...Xn] (Xi 2 Ar for each 1 i n) // list of arguments 5: // Initialize LabO and include the main argument 6: LabO (; , ; , Ar ) // LabO becomes the all-undec labelling 7: unproc_in [A] 8: LabO(A) in 9: MMLabO(A) MM LabI (A) 10: 11: // Next, process the other arguments in a top-down way 12: while unproc_in is not empty do 13: let X be the argument at the front of unproc_in 14: remove X from unproc_in 15: for each attacker Y of X do 16: LabO(Y ) out 17: 18:
if there is no minimal (w.r.t. MMLabI ) in labelled (w.r.t. LabI ) attacker of Y that is also labelled in by LabO then
Let Z be a minimal (w.r.t. MMLabI ) in labelled (w.r.t. LabI ) attacker of Y Add Z to the rear of unproc_in LabO(Z) in
MM LabI (Z) 19: 20: 21: 22: MMLabO(Z) 23: end if 24: end for 25: end while that it has already been established that the main argument is in the grounded extension and that the aim is merely to nd a (relatively small) strongly admissible labelling that shows this.
It has been proven that each of the above three algorithms terminates (in polynomial time)
and provides a strongly admissible labelling that labels the argument in (provided that such
a strongly admissible labelling exists, which requires the argument to be in the grounded
extension) together with the min-max numbering of this labelling [
Input: An argumentation framework AF = (Ar , att ), an argument A 2 Ar that is in the grounded extension of AF .
Output: A strongly admissible labelling Lab where A 2 in(Lab), the associated min-max numbering MMLab. 1: run Algorithm 1 2: LabI L ab
4: run Algorithm 2 5: Lab L abO 6: MMLab MM LabO
As an aside, although Algorithm 1 has been written with the aim of constructing a strongly
admissible labelling (and associated min-max numbering) for a particular argument, it can easily
be altered to yield the grounded labelling (and associated min-max numbering) instead. This
could be done by commenting out lines 13 and 28, and by adding the following line (line 33) at
the end of the algorithm:
return Lab and MMLab
We refer to the thus modi ed algorithm as Algorithm 10. It has been proven that Algorithm 10
indeed yields the grounded labelling and its associated min-max numbering [
In our previous work [
In order to maintain consistency and to allow for a like-for-like comparison, we examine
this question using the same set of benchmark examples as was used in [
Similar to what was done in [
In [
We are not aware of any dedicated third party algorithms or other computational approaches
that aim to construct an arbitrary strongly admissible labelling in the shortest possible time. We
are, however, aware of computational approaches that aim to either construct a minimal strongly
admissible labelling (the ASPARTIX approach of [
As for comparing the performance of Algorithm 1 with an algorithm for constructing the
grounded labelling, we have chosen Algorithm 3 of [
Algorithms 1, 2 and 3 construct not only a strongly admissible labelling but also its associated
min-max numbering. The relevance of min-max numberings goes beyond merely determining
(by the absence of 1 ) whether its associated admissible labelling is strongly admissible or not.
A min-max numbering also serves as the basis for playing the Grounded Discussion Game [
Although a min-max numbering does have its usefulness, the question is what are the computational resources needed to construct it. In particular, what is the additional runtime that is required for constructing the min-max numbering of a strongly admissible labelling?
In order to answer this question, we compare the runtime of Algorithm 1 with the runtime of
a modi ed version of Algorithm 1 which only constructs the strongly admissible labelling itself
(without also constructing its min-max numbering). This can be done by commenting out the
lines 12, 21 and 27, and by returning only Lab (instead of both Lab and MMLab in lines 13
and 28. We refer to the thus modi ed algorithm as Algorithm 100.
8This is despite the fact that Algorithm 3 of [
Figure 4 depicts the results of Algorithm 100 versus the runtime of Algorithm 1 (each dot represents one of the 277 benchmark examples that we tested for). On average, Algorithm 1 takes just 1.83% more time than Algorithm 100.
Similar to the way in which we modi ed Algorithm 1, one may wonder what would happen if the min-max numbering was no longer constructed by Algorithm 3. That is, what if we change Algorithm 3 (call it Algorithm 300) to include Algorithm 100 (instead of Algorithm 1) and Algorithm 200 (instead of Algorithm 2), where Algorithm 200 does not use or yield any min-max numbering? Unfortunately, this turns out not to be possible. The point is that Algorithm 2 (in lines 18 and 19) requires the min-max numbering that is produced by Algorithm 1.
To see the essence of the problem, consider the argumentation framework of Figure 5. Suppose the argument in question is E. Algorithm 1 would yield the strongly admissible labelling ({A, C, E}, {B, D}, ; ) and associated min-max numbering {(A : 1), (B : 2), (C : 3), (D : 4), (E : 5)}, which are subsequently fed into Algorithm 2. By the time Algorithm 2 reaches argument B, it will choose B’s attacker A instead of E, as A has the smallest min-max number, and the algorithm will terminate. However, without the min-max numbering provided by Algorithm 1, Algorithm 2 would not know whether to choose A or E, which means it might enter an in nitive loop if it chooses E consistently.9 As such, the fact that we can remove the concept of a min-max numbering from Algorithm 1 does not imply we can also remove the concept of a min-max numbering from Algorithm 2, at least not in any straightforward way.
A
B E
C D
There is, however, at least one additional way in which we can assess the computational costs of constructing the min-max labelling. Recall that Algorithm 1 can be modi ed in order to compute the grounded labelling by commenting out lines 13 and 28, and by adding the following line (line 33) at the end of the algorithm: return Lab and MMLab The thus modi ed algorithm is referred to as Algorithm 10.
Of course, we could compare the performance of Algorithm 10 with the performance of a
modi ed version of Algorithm 10 that constructs only the grounded labelling (without its
associated min-max numbering). However, it would be more interesting to compare the performance
of Algorithm 10 with an algorithm that was optimised for constructing the grounded labelling
9Apart from that, not having access to the min-max numbering of Algorithm 1 could also cause Algorithm 2 to yield
a bigger strongly admissible labelling than it would otherwise have yielded.
only. For this, we will use Algorithm 3 of [
Our empirical results indicate that when it comes to constructing an arbitrary strongly admissible
labelling (for a particular argument) Algorithm 1 provides a relatively e cient way (regarding
runtime) of doing so. In the examples we tested for, Algorithm 1 clearly outperformed some of
its alternatives (Algorithm 3 by a factor 2, the ASPARTIX approach of [
One of the things we did not do in our current work is to compare the performance of
Algorithm 1 with µ-toksia [
Our results indicate that the additional computational time required to construct the min-max
numbering (that is, the di erence in runtime between constructing both a strongly admissible
labelling and its min-max numbering, and constructing a strongly admissible labelling only)
is negligible.12 In particular, commenting out the code in Algorithm 1 that constructs the
min-max numbering (Algorithm 100) yields a performance increase of less than 2%. Moreover,
our approach to constructing the grounded labelling (Algorithm 10), which also constructs the
associated min-max numbering, even outperforms (by more than 3%) the fastest imperative
algorithm for constructing the grounded extension/labelling in the literature that we are aware
of (Algorithm 3 of [
Overall, our ndings indicate that Algorithm 1 is a good candidate for computing strong admissibility. As such, we would consider submitting it to ICCMA in case a track on strong admissibility is opened.
This work was supported by the BMK Endowed Professorship for Data-Driven Knowledge Generation: Climate Action (FFG project number 891607). 11ICCMA’19 was the last ICCMA that had a track on grounded semantics. 12This may be related to the fact that Algorithm 1 constructs the strongly admissible labelling and its associated minmax number concurrently, rather than rst constructing the strongly admissible labelling and then constructing its associated min-max numbering.