In many formalisms extending Dung's Abstract Argumentation Frameworks (AFs), arguments are not always \present". In timed AFs, for instance, arguments are only available in precise intervals of time, as they can appear and disappear in an intermittent manner; in incomplete AFs, both attacks and arguments can be absent; in constellation probabilistic AFs (attacks and) arguments have a probability to be present or not, and possible worlds are generated for the computation of the semantics. We review current approaches and propose a four-state labelling semantics to take in account such absent/unknown state of an argument. The four labels we use can be traced to the states a belief can assume, allowing us to also de ne operations related to belief manipulation, like expansion contraction and revision. We also discuss how labels/states of arguments in an AFs can be modi ed by using belief revision operations.
A labelling for AFs has been proposed by Caminada [
In this paper, we provide a unifying representation for (temporarily) excluded
arguments or for arguments we want to ignore. We use a partial labelling with
four labels to identify the possible states of arguments, namely IN for accepted,
OUT for rejected, DK for arguments we don't know how to label, and DC for
arguments we don't care about (because not adopted in an AF or just ignored by
the user). The introduced four-state labelling can be mapped with belief states
in AGM Theory [
In this section we recall the formal de nition of AF and the related semantic [
Consider two arguments a; b belonging to an AF. We denote with (a; b) 2 R (or simply a ! b) an attack from a to b; we can also say that b is defeated by a. We de ne the sets of arguments that attack (and that are attacked by) another argument as follows.
De nition 2 (Attacks). Let hA; Ri be an AF, a 2 A and A A. We de ne the sets a+ = fb 2 A j a ! bg, a = fb 2 A j b ! ag, A+ = [fa+ j a 2 Ag and A = [fa j a 2 Ag.
In order for b to be acceptable, we require that every argument that defeats b is defeated in turn by some other argument of the AF. More formally, we have the following de nition.
De nition 3 (Acceptable argument). Given an AF hA; Ri, an argument a 2 A is acceptable with respect to D A if and only if 8b 2 A such that b 2 a (b is attacking a) 9d 2 D such that d 2 b (d is attacking b) and we say that a is defended by D.
Using the notion of defence as a criterion for distinguishing acceptable arguments in the framework, one can further re ne the set of selected \good" arguments through semantics.
De nition 4 (Extension-based semantics). Let hA; Ri be an AF. A set E A is con ict-free if and only if there are no a; b 2 E such that (a; b) 2 R. A con ict-free subset E is then { admissible, if each a 2 E is defended by E; { complete, if it is admissible and 8a 2 A defended by E, a 2 E; { stable, if E [ E+ = A; { preferred, if it is admissible and it is maximal (with respect to set inclusion); { grounded, if it is complete and it is minimal (with respect to set inclusion).
In Figure 1, we show a framework F for which we compute the set of extensions S (F ), where is a semantics among con ict-free, admissible, complete, stable, preferred and grounded semantics (abbreviated with cf, adm, com, stb, prf and gde). We have: Scf (F ) = ffg, fag, fbg, fcg, fdg, fa; cg, fa; dg, fb; dgg, Sadm(F ) = ffg, fag, fcg, f g
d , fa; cg, fa; dgg, Scom(F ) = ffag, fa; cg, fa; dgg, Sprf (F ) = ffa; cg, fa; dgg, Sstb(F ) = ffa; dgg, and Sgde(F ) = ffagg.
The work in [
De nition 5 (IN-OUT-UNDEC labelling for AFs [11, De nition 5]). Let F = hA; Ri. An IN-OUT-UNDEC labelling L of F is a total function L : A ! fIN, OUT, UNDECg satisfying the following rules 8a 2 A: { L(a) = IN { L(a) = OUT () 8b 2 A j (b; a) 2 R:L(b) = OUT and
() 9b 2 A j (b; a) 2 R ^ L(b) = IN
In other words, an argument a is labelled IN when all its attackers are labelled OUT, and it is labelled OUT when at least an IN argument attacks it. In all other cases, a is labelled UNDEC. In Figure 2 we show an example of IN-OUT-UNDEC labelling on an AF in which arguments a and c highlighted in green are IN, red ones (b and d) are OUT, and the the yellow argument e (that attacks itself) is UNDEC.
Given an IN-OUT-UNDEC labelling L, it is possible to identify a
correspondence between sets of IN arguments and extensions of the semantics given in
De nition 4. A labelling-based semantics [
The de nition for an admissible labelling given in [
Di erent de nitions of labellings, as for instance those given in [
The authors of [
De nition 7 (+- labelling for AFs [17, De nition 3]). Let F = hA; Ri. A +- labelling M of F is a total function M : A ! 2f+; g satisfying the following rules 8a 2 A: { 2 M (a) =) 9b 2 A j (b; a) 2 R ^ + 2 M (b) { + 2 M (a) =) 8b 2 A j (b; a) 2 R: 2 M (b) ^
8c 2 A j (a; c) 2 R: 2 M (c)
Arguments only detaining a + (or ) label are accepted (rejected, respectively), those with both labels are undecided, and those with no label are just ignored. In Figure 4, grey arguments have an empty label ;, while yellow ones have both + and .
Comparing this labelling with the IN-OUT-UNDEC one, we have that, for any argument a 2 A, M (a) = f+g =) L(a) = IN, M (a) = f g =) L(a) = OUT and M (a) = f+; g =) L(a) = UNDEC. Since the implications only hold for one direction, there is no correspondence between +- labelling and classical semantics: for instance, while arguments labelled f+g by M will always be labelled IN by L, the vice versa is not true, meaning an argument a can exist for which L(a) = IN and M (a) = fg. Note that, in both De nition 5 and 7, if an accepted argument a attacks another argument b, then b must be rejected.
To give the possibility of ignoring particular arguments without losing the
link with extension-based semantics, the authors of [
De nition 8 (Grounded IN-OUT-UNDEC-OFF labelling for AFs [18, Definition 2.16]). Let F = hA; Ri and G = hA0; R0i with A0 A and R0 R. A grounded IN-OUT-UNDEC-OFF labelling Ngde with respect to A0 is a total function Ngde : A ! fIN, OUT, UNDEC, OFFg such that: { 8a 2 A n A0:Ngde(a) = OFF { 8a 2 A0:Ngde(a) = Lgde(a)
A di erent split for UNDEC arguments is proposed in [
De nition 9 (IN-OUT-BOTH-NONE labelling for AFs [2, De nition 9]). Let F = hA; Ri and E A. An IN-OUT-BOTH-NONE labelling with respect to E is a total function OE : A ! fIN, OUT, BOTH, NONEg satisfying 8a 2 A: { OE (a) = IN { OE (a) = OUT { OE (a) = BOTH { OE (a) = NONE (= a 2 E ^ a 2= E+ (= a 2= E ^ a 2 E+ (= a 2 E ^ a 2 E+ (= a 2= E ^ a 2= E+ Moreover, we say that OE is BOTH-free when E \ E+ = ;.
Argument a in Figure 6 is labelled NONE, while e is labelled BOTH. De
nitions for p-admissible and p-complete labellings are also given in [
The labellings discussed in the previous section have both pros and cons that
vary according to the point of view. Four-state labellings [
On the other hand, an IN-OUT-UNDEC labelling can always be mapped into a set of accepted arguments, but it does not allow to leave unlabelled arguments that we do not want to consider in computing acceptability, and forces all arguments that are neither IN nor OUT to be labelled UNDEC. Consequently, when considering IN-OUT-UNDEC labellings to inspect AFs, the information brought by the UNDEC label can be misleading. Also, since any IN-OUT-UNDEC labelling corresponds to a complete extension, it cannot identify con ict-free sets. To overcome these inconveniences, we propose a four-state labelling which considers not only complete, but also admissible and con ict-free sets of arguments, and that provides a unifying representation for the various approaches proposed in the literature.
De nition 10 (Four-state labelling-based semantics). Let U be a universe of arguments and F = hA; Ri with A U . A four-state labelling LF of F is a partial4 function LF : U * fIN, OUT, DK, DCg such that 8a 2 U n A:L(a) =". Superscript F will be omitted when clear from the context. We say that: { L is a con ict-free labelling when
L(a) = IN =) 8b 2 a :L(b) 6= IN and
L(a) = OUT =) 9b 2 a j L(b) = IN { L is an admissible labelling when
L(a) = IN =) 8b 2 a :L(b) = OUT and
L(a) = OUT () 9b 2 a j L(b) = IN { L is a complete labelling when
L(a) = IN () 8b 2 a :L(b) 2 fOUT; DCg and
L(a) = OUT () 9b 2 a j L(b) = IN
{ L is a stable labelling when
L is a complete labelling and
A #DK= ; { L is a preferred labelling when
L is an admissible labelling and
A #IN is maximal among all the admissible labellings { L is a grounded labelling when
L is a complete labelling and
A #IN is minimal among all the complete labellings
We denote with L a labelling L satisfying the above conditions for a given semantics , with L the set of all possible labellings, and with L the set of all possible labellings satisfying conditions for . For any A A, R R and l fIN; OUT; DK; DCg, we use A #l= fa 2 A j L(a) 2 lg and R #l= f(a; b) 2 R j L(a) 2 l ^ L(b) 2 lg to restrict to arguments and relations only involving certain (sets of) labels.
The labelling of an AF contains information about the acceptability of the
arguments in the framework (according to the various Dung's semantics) and
can be used by intelligent agents to represent the state of their beliefs. Each
di erent label can be traced to a particular meaning. For instance, DC stands
for \don't care" [
Since arguments in U n A do not constitute an actual part of the AF, they
are not labelled, as we consider them not adopted. We, instead, label DC any
argument in A we don't care about. Notice that arguments we do not adopt and
arguments we do not care about are very di erent: not adopted arguments are
involved in no attack, as they do not even belong to the considered AF; don't
care arguments, instead, can be involved in attacks and we also consider them
for deciding the label of the attacked arguments. In particular, concerning the
complete four-state labelling, an argument a that is only attacked by ignored
arguments (labelled DC) is accepted and thus labelled IN, as happens in [
We now show the correspondence between four-state labellings satisfying restrictions given in the de nition above and the extensions of a certain semantics. tension of F 0 = hA #IN;OUT;DK; R #IN;OUT;DKi.
Theorem 1. A four-state labelling LF of F = hA; Ri is a con ict-free labelling if and only if A #IN is a con ict-free extension of F . Moreover, LF is an admissible (respectively complete, stable, preferred, grounded) labelling if and only if A #IN is an admissible (respectively complete, stable, preferred, grounded) ex5 A pessimistic interpretation labelling as OUT arguments attacked by DC could also be introduced.
The four-state labelling can also be mapped into the labellings presented in the previous section, hence providing a unifying representation for argument states.
Theorem 2. A four-state labelling L is an IN-OUT-UNDEC labelling (see De nition 5) if and only if L is complete, A #DC= ; and A = U , with the mapping among labels DK UNDEC.
Proof of Theorem 2 directly follows from De nitions 5 and 10. Moreover, by using the conditions of Table 1, four-state labellings can be traced to stable (respectively preferred, grounded) IN-OUT-UNDEC labellings.
Corollary 1. A four-state labelling L is a stable (preferred or grounded, respectively) IN-OUT-UNDEC labelling if and only if L is stable (preferred or grounded, respectively), A #DC= ;, A = U and A #DK= ; (A #IN is maximal or A #IN is minimal, respectively), with the mapping among labels DK UNDEC.
Corollary 1 can be proved considering that L is an IN-OUT-UNDEC labelling (according to Theorem 2) satisfying the restrictions of Table 1 for stable (preferred or grounded, respectively) labellings. Finally, we compare four-state and admissible IN-OUT-UNDEC labellings.
Theorem 3. A four-state labelling L is an admissible IN-OUT-UNDEC labelling (see De nition 6) if and only if L is admissible, A #DC= ; and A = U , with the mapping among labels DK UNDEC.
Proof of Theorem 3 directly follows from De nitions 6 and 10. When considering +- labelling, we have to keep in mind that none, one or two labels can be assigned to each argument.
Theorem 4. A four-state labelling L is a +- labelling (see De nition 7) if and only if L is admissible and A = U , with the mapping among labels IN +, OUT , DK f+; g and DC ;.
IN-OUT-UNDEC-OFF labellings, then, allow arguments to be excluded from the computation of the acceptability, similarly to how not adopted arguments can be ignored in a four-state labelling.
Theorem 5. A four-state labelling L is a grounded IN-OUT-UNDEC-OFF labelling with respect to A0 (see De nition 8) if and only if L is grounded, A #DC= ;, and A0 = U n A, with the mapping among labels " OFF and DK UNDEC.
Theorems 4 and 5 can be proved directly from De nitions 7, 8 and 10.
Notice that, in general, a direct mapping from IN-OUT-BOTH-NONE labelling to our four-state labelling does not exist. Assume NONE DC and BOTH DK, and consider the p-admissible labelling of Figure 7 (left) with respect to E = fa; b; dg. The OUT argument c is only attacked by argument b (labelled BOTH), and the represented labelling is not an admissible four-state labelling since, according to De nition 10, OUT arguments must be attacked by at least one IN. A four-state labelling, then, is not guaranteed to be an admissible INOUT-BOTH-NONE labelling. On the other side, the admissible four-state labelling of Figure 7 (right) is not p-admissible, since according to [2, De nition 11] NONE arguments cannot have an attacker labelled BOTH.
Consider now the labelling of Figure 8 (left). It is a complete four-state labelling, but not a p-complete labelling, since the IN argument b is not attacked by any OUT. Finally, Figure 8 (right) shows a p-complete labelling that is not a complete four-state labelling. Indeed, the OUT argument e is not attacked by any IN.
The four-state labelling introduced in the previous section share similarities with
the AGM framework [
The AGM framework [
An expansion basically brings new pieces of information to the base, allowing for undetermined belief to become either accepted or refused. A contraction, on the contrary, reduces the information an agent can rely on in making its deduction. A revision, then, makes acceptable belief refused and vice-versa. The AGM framework also de nes three sets of rationality postulates (one for each operation) that any good operator should satisfy.
AGM operators provide building blocks for realizing complex interaction processes between agents. As for knowledge basis in belief revision, AFs can undergo changes that modify the structure of the framework itself, either integrating new information (and so increasing the arguments and the attacks in the AF) or discarding previously available knowledge. Agents using AFs as the mean for exchanging and inferring information have to rely on operations able to modify such AFs. Besides considering the mere structural changes, also modi cations on the semantics level need to be addressed by the operations executed by the agents. In the following, we de ne an argument expansion operator for AFs, that complies with classical operators of AGM. Notice that changes to the knowledge base we are interested in modelling are restricted to a single argument at a time, miming the typical argument interaction in dynamic AFs. In this paper we only provide de nition and postulates for the expansion operator.
De nition 11 (Single labelling argument expansion). Let F = hA; Ri be
an AF on the universe U , a semantics, LF a given labelling function, and
a 2 U an argument. A single labelling argument expansion with respect to a
labelling LF consists of a function LF : AF U ! AF that computes a new
framework F 0 = F LF a such that LF 0 (a) <kb LF (a).
In devising our expansion operator, we reinterpret the AGM expansion
operator [
IN=OUT, then LF 0 (a) = DK 5
We de ned a four-state labelling semantics for AFs that allows for establishing
acceptability of arguments on a ner grain with respect to other approaches
presented in the literature. We use four labels: IN, OUT, DK and DC, the last one
denoting arguments we want to ignore. We showed the connection between our
labelling and the AGM framework, introducing operators for expansion,
contraction and revision of arguments states. AGM operators have already been studied
from the point of view of their implementation in work as [
In our setting, arguments only attacked by DC arguments are always labelled
IN. As future work, we want to consider a pessimistic interpretation for ignored
arguments: since a DC-labelled argument a could be (re)considered into the AF,
thus gaining an IN, OUT or DK label, arguments only attacked by a could be
labelled OUT in turn. We also plan to extend the four-state labelling to weighted
AFs [