In this work we consider labelling-based algorithms for evaluating SETAFs. We propose labellings that label both arguments and attacks for labellingbased algorithms and systematically investigate label propagation rules for stable and complete-based semantics, i.e., under which circumstances we can determine the label of an argument or attack by the already fixed labels of the neighbours.
Formal models within the field of abstract argumentation provide the key machinery
underlying many state-of-the-art approaches in argumentation in AI [
Development and usability of formalizations of abstract arguments, such as SETAFs,
relies on studying computational approaches, witnessed, e.g., by the argumentation
competition [
Recently, reduction-based systems for SETAFs based on ASP [
This paper is organized as follows. We start with a brief recap of SETAFs and its semantics in Section 2 and then introduce our argument-attack labellings in Section 3. In Section 4 we then present a linear time labelling-based algorithm for grounded semantics and investigate possible label propagations for stable and complete-based semantics in Sections 5 & 6. We conclude the paper with pointers to future work.
We introduce formal definitions of argumentation frameworks with collective attacks
(SETAFs) following [
Definition 1. A SETAF is a pair F = (A; R) where A is finite, and R attack relation. (2A n 0/ )
A is the
Notice that SETAFs that only allow for binary attacks are equivalent to Dung
argumentation frameworks (AFs) as introduced in [
Definition 2. Given a SETAF F = (A; R), an argument a 2 A is defended (in F) by a set S A if for each B A, such that B 7!R a, also S 7!R B. A set T of arguments is defended (in F) by S if each a 2 T is defended by S (in F).
1https://bitbucket.org/andreasniskanen/joukko
Next, we introduce the semantics we study in this work. These are the stable, preferred, complete, and grounded semantics, which we will abbreviate by stb, pref, com, and grd, respectively. For a given semantics s , s (F) denotes the set of extensions of F under s .
Definition 3. Given a SETAF F = (A; R), a set S A is conflict-free (in F), if S0 [ fag 6 S for each (S0; a) 2 R. We denote the set of all conflict-free sets in F as cf(F). S 2 cf(F) is called admissible (in F) if S defends itself. We denote the set of admissible sets in F as adm(F). For a conflict-free set S 2 cf(F), we say that
S 2 stb(F), if S 7! a for all a 2 A n S, S 2 pref(F), if S 2 adm(F) and there is no T 2 adm(F) such that T S 2 com(F), if S 2 adm(F) and a 2 S for all a 2 A defended by S, and S 2 grd(F), if S = TT 2com(F) T .
S,
As shown in [
Semantics for SETAFs can be alternatively defined through argument labellings, as
proposed in [
Definition 4. An argument labelling for a SETAF F = (A; R) is a total function L : A ! fin; out; undecg. We define l(L ) = fa 2 A j L (a) = lg for l 2 fin; out; undecg.
We state the labelling-based formulations of the considered semantics. Definition 5. Let F = (A; R) be a SETAF. An argument labelling L of F is called complete if for all a 2 A,
L (a) = in , for all (S; a) 2 R; there is b 2 S with L (b) = out;
L (a) = out , there is (S; a) 2 R such that for all b 2 S; L (b) = in; preferred if L is complete and in(L ) is maximal with respect to set-inclusion among all complete argument labellings of F; stable if L is complete and undec(L ) = 0/ ; grounded if L is complete and in(L ) is minimal with respect to set-inclusion among all complete argument labellings of F.
In [
Theorem 1 ([
For computational purposes we will refer to the size of the SETAFs and use the following notations. For a set AF F = (A; R), we call jAj the number of arguments, jRj the number of attacks, and kRk = jRj + å(S;a)2R jSj the size of the attack relation. The input size kFk of an SETAF F is given by the number of arguments plus the size of the attack relation, i.e., kFk = jAj + kRk.
In this section, we introduce argument-attack labellings for SETAFs which generalize the
idea of labellings introduced in [
In contrast to binary attacks (a; b), where one can directly infer the acceptance status of b from the acceptance status of the single argument a, collective attacks (S; a) require to check the acceptance status of each argument b 2 S in order to derive conclusions about a. We will therefore introduce argument-attack labellings in order to store the status of attacks in SETAFs. Intuitively, an attack (S; a) is labeled in if S belongs to an extension; (S; a) is labeled out if S is attacked by an extension; and (S; a) is labeled undec if S does neither belong to an extension nor is attacked by an extension.
Definition 6. An argument-attack labelling of a SETAF F = (A; R) is a total function l : A [ R ! fin; out; undecg; we write l(l ) = fa 2 A j l (a) = lg for l 2 fin; out; undecg.
Definition 7. Let (A; R) be a SETAF. A labelling is a complete argument-attack labelling if it satisfies the following constraints:
For every attack (S; a) 2 R, For every argument a 2 A,
l ((S; a)) = in , for all b 2 S; l (b) = in; l ((S; a)) = out , there is b 2 S with l (b) = out: l (a) = in , for all (S; a) 2 R; l ((S; a)) = out; l (a) = out , there is (S; a) 2 R with l ((S; a)) = in: (1) (2) (3) (4)
The following constraints for undec-labels follow from (1) and (2) (or (3) and (4), respectively): For an attack (S; a) 2 R, l ((S; a)) = undec iff there is b 2 S which is labelled undec and no other argument b0 2 S is labelled out. For an argument a 2 A, l (a) = undec iff there is an attack (S; a) 2 R which is labelled undec and a is not attacked by an in-labelled attack.
Complete argument labellings and complete argument-attack labellings are closely related; in fact, it can be shown that each complete argument-attack labelling induces a complete argument labelling and vice versa. Proposition 1. For any SETAF F = (A; R), the following holds: (a) If l is a complete argument-attack labelling of F then L = l jA is a complete argument labelling of F. (b) If L is a complete argument labelling of F then l is a complete argument-attack labelling of F where l is defined as follows: (i) l (a) = L (a) for a 2 A; (ii) l ((S; a)) = in if for all b 2 S, L (b) = in; (iii) l ((S; a)) = out if there is b 2 S with L (b) = out; (iv) l ((S; a)) = undec else.
The following characterization of preferred, grounded and stable semantics in terms of argument-attack labellings is immediate by Proposition 1 and Theorem 1. Proposition 2. For any SETAF F = (A; R), for s 2 fcom; grd; pref; stbg, there is a oneto-one correspondence between extensions and argument-attack labellings such that for each S 2 s (F) there is a s argument-attack labelling l with in(l ) = S, out(l ) = S+ and undec(l ) = A n (S [ S+).
In the following, we will only consider argument-attack labellings and thus refer to them simply as labellings. In our algorithm we typically do not immediately label all the arguments but will consider partial labellings that will be completed during the algorithm. To this end we will sometimes also use additional labels to encode an intermediate state of an argument label.
Definition 8. A partial labelling is a partial function m : A [ R ! fin; out; undecg [ E , where E is a possibly empty set of additional labels.
Remark 1. An alternative approach towards labellings for SETAFs would be to label subsets of argument instead of attacks. Labelling all subsets of arguments can lead to labellings of exponential size and is thus not well suited for computational purposes. However, when inspecting the conditions for the labels of attacks in Definition 7 we observe that the label of an attack (S; a) is determined by the set S. Thus, for an arbitrary complete labelling and two attacks (S; a) and (S; b), i.e, the attacks have the same set of arguments but attack different arguments, we have that both attacks have the same label. That is, our argument-attack labellings can be equivalently interpreted as labellings of arguments and certain sets of arguments, i.e., those sets S such that there is an attack (S; a). If the representation of SETAFs in an implementation allows to identify attacks with the same set of arguments efficiently one can exploit this observation for more succinct representations of labellings.
The basic idea for a grounded algorithm is to start with the unattacked arguments and iteratively compute the defended arguments and add them to the extension until a fixed point is reached. When done in a naive way, in each iteration one would check for each argument not in the (partial) extension whether it is defended against all incoming attacks, via computing the status of such an attack. We avoid this repetitive computations by using our labellings that also label attacks and by that store the status of an attack.
In terms of our labellings the basic idea of our algorithm is to assign the label in to all unattacked arguments and then propagate labels to other arguments as follows. For an unlabelled argument a 2 A, 1. we set m(a) = in if for all attacks (S; a) 2 R, we have m((S; a)) = out, and 2. we set m(a) = out if there is (S; a) 2 R with m((S; a)) = in; and for an unlabelled attack (S; a) 2 R, 1. we set m((S; a)) = in if we have m(b) = in for all b 2 S, and 2. we set m((S; a)) = out if there is b 2 S with m(b) = out.
Finally, all arguments and attacks that remain unlabelled when the fixed-point of these propagations is reached are labelled undec.
In Algorithm 1 we efficiently implement these labelling propagation idea by: a)
(re)considering arguments (attacks) only if the label of an incident attack (argument)
has changed; b) use counters for arguments (attacks) to efficiently store the progress on
incident attacks (arguments) in order to avoid rechecking all the neighbors if the label
of one neighbor changes (similar counters have been used in linear time algorithms for
computing the grounded extension of a Dung AFs [
As a data structure we will use a partial labelling m that maps arguments and attacks to the labels fin; out; undecg and a function c that maps each argument and attack to an integer between 0 and max(jAj; jRj). For an argument a the value c(a) represents the number of attacks (S; a) that are not labeled out by m, while for an attack (S; b) the value c((S; b)) represents the number of arguments c 2 S that are not labeled in by m. That is, if the counter turns to 0 we know that we can label the argument, or attack respectively, in. The algorithm, whenever setting the label of an argument or attack, updates the c-values of all the neighbors and if a counter turns to 0 updates the label of the corresponding argument or attack.
In the Algorithm we use a data structure Args that stores a collection of the arguments that have been labelled but whose label has not yet been propagated to its neighbors. To implement Args we can use any data structure that implements the following operations in O(1) time: (i) test whether Args is empty, (ii) add one element to Args, and (iii) extract one element, i.e., return an element from Args and remove that element from Args. Standard implementations of queues and stacks provide these properties. Thus we can assume we have a method ExtractArg(Args) that, if Args is non-empty, returns an element and removes that element from Args. Also notice that our algorithm does not add duplicates to Args.
Using a standard queue data structure we obtain that the grounded extension can be computed in linear time w.r.t. size of the input SETAF.
Theorem 2. Algorithm 1 can be implemented to run in time O (kFk) for any SETAF F. Proof. Let F = (A; R) and assume Args is implemented via a standard queue data structure. That is, the initialization of Args and the operations Args 6= 0/ , extractArg(Args) and Args [ fbg are in constant time. First consider the initialization phase of the algorithm. To set the counter c(a) for argument a we iterate over all incoming attacks. Hence, we can set all the counters for the argument in O(jAj + jRj). To set the counter c((S; a)) for
attack (S; a) we iterate over all arguments in S and thus we can set all the counters for attacks in O(kRk). Finally, for each argument a 2 A it only requires constant time to check whether c(a) = 0, set m(a) = in, and add a to the queue in O(jAj). Hence, the initialization phase is in O (jAj + kRk). Now consider the while loop. Notice that each argument is only added once to the queue and thus processed only once in the loop and for each argument we process all the outgoing attacks. All the other operations are in constant time. Thus it follows that each attack (S; a) 2 R is processed O(jSj) many times and the overall running time of the while loop and the algorithm is in O(jAj + kRk) = O(kFk).
Next we consider an algorithm to compute stable labellings. In contrast to grounded semantics we now deal with potentially many extensions and thus follow the standard scheme of labelling based algorithms. The rough idea of labelling-based algorithms is to start with all arguments (and in our case also attacks) unlabelled, in each step pick an argument and then consider two branches: one where we add the argument to the extension, i.e., labelled the argument in; and one where we decide that the argument is excluded from the extension, i.e., the argument must be labelled out for stable semantics. When all arguments are labelled, one tests whether the labelling is valid w.r.t. the considered semantics and, if so, it is added to the set of extensions. By that procedure we would consider all possible candidates for valid labellings and thus also obtain all the extensions. In order to design an efficient algorithm one aims to cut off branches that do not lead to valid labellings as soon as possible. One approach are label propagation rules, i.e., one uses the already fixed labels of the arguments and attacks to determine labels of their neighboring arguments and attacks. By that, one avoids unnecessary branching in the algorithm. The general structure is given in Algorithm 2; key component is the function update(:) that a) sets an argument to a specific label, b) applies label propagation rules to determine labels of other arguments and attacks, and c) identifies local inconsistencies in the labelling which already determine that a partial labelling cannot be extended to a valid labelling. The update function returns the updated labelling and a Boolean variable that indicates whether it has identified any local inconsistencies.
Let us next discuss how we can propagate labels for stable semantics. We will first consider the case where we have a partial labelling m and an argument a 2 A. By systematically inspecting the definition of a stable labellings (i.e., complete labellings that have no undec label) we extract the following rules to obtain a label for a when considering its incident attacks.
m (c) = in. 1. a 2 A must be labelled in if either (a) for all attacks (S; a) 2 R, we have m ((S; a)) = out; or (b) there is (S; b) 2 R, a 2 S, with m ((S; b)) = in. 2. a 2 A must be labelled out if either (a) there is (S; a) 2 R with m ((S; a)) = in; or (b) there is (S; b) 2 R, a 2 S, we have m ((S; b)) = out and for all c 2 S n fag, One way to determine the acceptance status of an argument a is by considering attackers of a; e.g., rule 2.(a) states that if there is an attack (S; a) which is labelled in we have a is labelled out (otherwise the generated extension is not conflict-free). On the other hand, also outgoing attacks, i.e., attacks (S; b) where a 2 S, can be used to determine the acceptance status of a in case certain requirements are met. Rule 2.(b) states that a must be labelled out if there is some attack (S; b) where a 2 S is the last unlabelled argument and every other argument is labelled in; otherwise, the attack (S; b) would be labelled out and thus the labelling would be invalid.
Require: SETAF F = (A; R), m0/ initial/empty partial labelling Ensure: Labs corresponds to the set of stable labellings 3: while PartialLabs 6= 0/ do m while m has unlabelled arguments do a d out in a b c d out out
out in a b c (a) Partial labelling m. (b) Updated labelling m0.
Next consider an attack (S; a) 2 R. From the definition of a stable labelling we can extract the following rules to obtain a label for (S; a) when just considering the arguments involved in the attack.
1. (S; a) 2 R must be labelled in if either (a) m(a) = out and for all (S0; a) 2 R,
S0 6= S, we have m((S0; a)) = out; or (b) for all b 2 S, we have m(b) = in. 2. (S; a) 2 R must be labelled out if either (a) m(a) = in; or (b) there is b 2 S with m(b) = out.
The label of an attack (S; a) can be directly inferred in case a is labeled in. When a is labeled out and (S; a) is the only attack on a or all other attacks attacking a are labelled out we can infer that (S; a) must be labelled in. Alternatively, one can consider the attacking set S: A label for the attack can be determined either if there is some argument b 2 S which is labelled out or in case every argument in S is labelled in. Example 1. We consider the SETAF F = (A; R) depicted in Figure 1 and a partial label m where the attack (fa; dg; d) is initially labelled out since it is self-attacking and a is set to in. We can update argument d using the argument propagation rule 2.(b) and set m0(d) = out; moreover, we can label the attack (fcg; a) using the attack propagation rule 2.(a), that is, m0((fcg; a)) = out (cf. Figure 1b).
Next we consider rules for arguments and attacks that have the same labels in all
extensions and thus can be fixed in an initial phase. That is, instead of starting with an
empty labelling, we compute the initial labelling m0/ by identifying arguments and attacks
that can be labelled independently of their neighbors. Several initial rules can be defined
as recent studies on collective attacks suggest (cf. [
Each argument a with no incoming attacks must be labelled in.
Each attack (S; a) with a 2 S must be labelled out.
Having set the initial labels, the propagation rules are applied as follows: The function update(m; A; label) first updates m(A) to label. Then if A is an argument we consider all incident attacks and test whether one could infer the labels of these attacks by one of the given propagation rules. Otherwise if A is an attack (S; a) we consider all arguments in S [ fag and test whether one could infer the label of these attacks by one of the given propagation rules. For each argument or attack B where we have inferred new label label0 we apply the following: (a) If we have inferred different labels from different rules the labelling is inconsistent and update returns invalid. (b) If we have inferred a label that is incompatible with the current label in m the labelling is inconsistent and update returns invalid. (c) If neither of the above applies we apply update(m; B; label0) and use the resulting labelling to proceed and returns invalid if update(m; B; label0) returns invalid.
Notice that the propagation rules ensure that once all arguments are labelled then either the last update computed is invalid or the labelling m is a stable labelling. That is, first for each attack if all incident arguments are labeled then at least on of the rules applies and thus either we obtain that the labelling is invalid or that all attacks are labelled. Now for each argument if all the incident attacks are labeled then at least one of the rules applies and thus either we obtain an invalid labelling or that all arguments are labelled.
In this section we present an algorithm for computing the complete labellings of a SETAF. The algorithm follows the same line as our algorithm for stable semantics, with some notable differences (see Algorithm 3). First, we have that complete labellings make use of all three labels in; out; undec, and in our algorithm we sometimes learn that we can exclude one of the labels. In order to encode this information in our partial labelling we allow two additional labels, notin indicating that the argument or attack must be labelled either out or undec, and notout indicating that the argument or attack must be labelled either in or undec. 2 We now have that certain labels are compatible, e.g., if an argument is labelled notin and we learn that it must be labelled out we can simply label it out, and others that are not, e.g., if an argument is labelled undec and we learn that it must be labelled in then the labelling cannot be extended to a complete labelling.
Require: SETAF F = (A; R), m0/ initial/empty partial labelling Ensure: Labs corresponds to the set of complete labellings 3: while PartialLabs 6= 0/ do m 14: return Labs end while Labs
Labs [ fmg a
Let us now consider the propagation rules that we can obtain for complete semantics. As for stable semantics initially we can label each unattacked argument with in and each attack (S; a) with a 2 S with notin and propagate these labels.
Now we consider propagation rules given a partial labelling m . From the definition of complete labellings we can extract propagation rules for arguments and attacks to obtain new labels when just considering their incident attacks. Rules to infer in- and 2Notice that one could also introduce a label notundec, but such a label was of no additional value for our propagation rules. out-labels generalize the rules for stable labellings by incorporating the additional labels undec, notin, notout; rules for undec-labels can be extracted from combining the argument constraints (respectively attack constraints) for complete labellings as discussed after Definition 7; rules for the labellings notin (notout) capture scenarios where either out or undec (respectively in or undec) can be learned, that is, they relax and combine the aforementioned out (respectively in) and undec labelling rules.
We will first consider propagation rules for an argument a 2 A. 1. a 2 A must be labelled in if either (a) for all attacks (S; a) 2 R, we have m((S; a)) = out; or (b) there is (S; b) 2 R, a 2 S, with m((S; b)) = in. 2. a 2 A must be labelled out if either (a) there is (S; a) 2 R with m((S; a)) = in; or (b) there is (S; b) 2 R, a 2 S, with m((S; a)) = out and for all c 2 S n fag, m(c) 2 fin; undec; notoutg. 3. a 2 A must be labelled undec if either (a) for all (S; a) 2 R, m((S; a)) 2 fout; undec; noting and there is (S; a) 2 R with m((S; a)) = undec; or (b) there is (S; b) 2 R, a 2 S, with m((S; b)) = undec and for all c 2 S n fag, m(c) = in. 4. a 2 A must be labelled notin if either (a) there is (S; a) 2 R with m((S; a)) 2 fundec; notoutg; or (b) there is (S; b) 2 R, a 2 S, with m((S; b)) = notin and for all c 2 S n fag, m(c) = in. 5. a 2 A must be labelled notout if either (a) for all (S; a) 2 R, we have m((S; a)) 2 fout; noting; or (b) there is (S; b) 2 R, a 2 S, with m((S; b)) 2 fundec; notoutg. Similar to the rules for stable labellings, one can infer the status of an argument a by either considering attacks on a or by considering attacks (S; b) where a 2 S. We will briefly discuss rules which consider incoming attacks. Let us consider an argument a; in case there is some attack (S; a) which is labelled in or if all attacks (S; a) are labelled out, the propagation rules behave like those for stable labellings, that is, a is labelled out in the former case (cf. rule 2.(a)) and a is labelled in in the second case (cf. rule 1.(a)). In case we have that each attack (S; a) on a cannot be labelled in in the final label, i.e., each attack is either labelled out, undec or notin, then one can exclude the label out, that is, a must be labelled notout to avoid an invalid labelling. In case we furthermore know that there is some attack which is labelled undec, then we can conclude that a must be labelled undec (cf. rule 3.(a)). The former rule for notout-labellings is captured by rule 5.(a) where the last observation about undec-labellings is taken into account. Finally, a can be labelled notin if there is some incoming attack which is labelled out or undec in the final label (cf. rule 4.(a)).
Next we consider an attack (S; a) 2 R, and obtain the following propagation rules. 1. (S; a) 2 R must be labelled in if either (a) m(a) = out and for all (S0; a) 2 R, S0 6= S, we have m((S0; a)) 2 fout; undec; noting; or (b) for all b 2 S, we have m(b) = in. 2. (S; a) 2 R must be labelled out if either (a) m(a) = in; or (b) there is b 2 S with m(b) = out. 3. (S; a) 2 R must be labelled undec if either (a) m(a) = undec and for all (S0; a) 2 R, S0 6= S, we have m((S0; a)) = out; or (b) for all c 2 S, we have m(c) 2 fin; undec; notoutg and there is c 2 S with m(c) = undec. 4. (S; a) 2 R must be labelled notin if either (a) m(a) 2 fundec; notoutg; or (b) there is b 2 S with m(b) 2 fundec; noting. 5. (S; a) 2 R must be labelled notout if either (a) m(a) = notin and for all (S0; a) 2 R, S0 6= S, we have m((S0; a)) = out; or (b) for all b 2 S, m(b) 2 fin; notoutg. While for certain rules it suffice to consider either the label of argument a or the labels od the set S to determine new labels, in general we have that attack rules for complete labellings require additional information about further attacks (S0; a) to infer the label of (S; a) via the target a (cf. rules 1.(a), 3.(a), 5.(a)). As an example, assume that a is labelled out. Recall that for stable labellings, an attack (S; a) must be labeled in in case a is labelled out. The situation gets more complex for complete labellings since they allow for undec-labellings: Here, the label of the attack (S; a) also depends on other attacks (S0; a), S0 6= S, i.e., only if every (S0; a) is not labelled in in the final labelling (that is, each (S0; a) is labelled out, undec or notin in the partial labelling) we can conclude that (S; a) must be labelled in (cf. rule 1.(a)).
The function update(m; A; label) works as for stable semantics but applies the above propagation rules. Moreover, when inferring several labellings it only yields invalid if they are not compatible and otherwise returns the most specific label. That is, the in label is only compatible with notout (combining them results in); the out label is only compatible with notin (combining them results out); the undec label is compatible with both notin and notout (combining them results undec in both cases); the notin label is compatible with undec, out and notout (combining notout and notin results undec); and the notout label is compatible with in, out and notin. Again the propagation rules ensure that once all arguments are labelled also all attacks are labelled and either the last update computes invalid or the resulting labelling m is a complete labelling.
Finally, notice that the discussed propagation rules can be applied to all semantics that propose subsets of the complete extensions and Algorithm 3 can extended to compute preferred or semi-stable extensions in the same way as for Dung AFs.
In this work we introduced argument-attack labellings of SETAFs and show their
potential for computational purposes by provided a linear time algorithm for grounded
semantics, and a systematic analysis of labelling propagation rules for stable and
completebased semantics. As for Dung AFs our algorithms for stable and complete semantics
branch only on the arguments and not on attacks and thus the worst case running time is
exponentially in the number of arguments but only polynomially depends on the number
and size of the attacks. That is, we can bound the running time by O(2jAj poly(kFk))
where the actual polynomial will depend on the choice and implementation of the
propagation rules. Notice, that these exponential-time algorithms reflect the facts that (a) a
SETAF might have exponentially many stable, complete respectively, extensions and (b)
there are reasoning problems for stable and complete semantics which are NP or
coNPcomplete [
We identify several directions for future research: (a) tailored data-structures for
labelling propagation for stable and complete labellings, like the counters for grounded
and the mout [
This research has been funded by the Austrian Science Fund (FWF): P30168 and W1255-N23.