a d b not d not a not a r3 : r4 : r5 : c A3
Example 1. Consider the logic program P from Figure 1, we will construct a CAF CF = (A; R; claim) by
instantiating the AF (A; R) following [
Although the CAF CF in Example 1 yields the same results as the original problem with respect to most
of the semantics, certain irregularities may arise when it comes to so-called range-based semantics, which take
arguments (atoms) into account that are defeated (set to false) in the particular extension (model): Semi-stable
semantics [
While it has been shown that inherited semantics for CAFs are adequate for standard Dung semantics, the example above reveals that for range-based semantics, results may deviate from the expected outcome of the original problem. A crucial observation is that semantics for LPs operate on conclusion (claim) level while extensions in AFs as well as in CAFs are evaluated on argument level. We are thus interested in developing adequate variants of range-based semantics for CAFs which mimic the behavior of semantics performing maximization on conclusion-level of the original problem (e.g. L-stable model semantics for LPs).
The discrepancy concerning range-based semantics has been already observed by Caminada et al. [
We introduce semantics based on maximization on claim-level and investigate their relation to inherited
semantics in the spirit of [
We propose two variants of stable semantics, based on con ict-free, respectively, admissible sets. We show that for well-formed CAFs, both variants of stable semantics as well as inherited stable semantics coincide. We compare inherited semantics with cl-semantics. We show that they exhibit similar behaviour concerning incomparability: For general CAFs, incomparability of claim-sets is not guaranteed, whereas for well-formed CAFs, every semantics under consideration yields incomparable claim-sets; moreover, we show that even for well-formed CAFs, both variants of semi-stable and stage semantics potentially yield di erent claim-sets. 2
We introduce argumentation frameworks [
1A set S is stable i it is con ict-free and attacks every argument in A n S.
2A set S is admissible in an AF F i it is con ict-free and attacks all attackers of S.
De nition 1. An argumentation framework (AF) is a pair F = (A; R) where A U is a nite set of arguments and R A A is the attack relation. We say that S A attacks b if (a; b) 2 R for some a 2 S. Moreover, an argument a 2 A is defended (in F ) by S A if each b with (b; a) 2 R is attacked by S in F .
Furthermore we denote by S+ = f arises, we drop the subscript F .FWe cabll2SA[ jS(F+a;tbh)e 2raRnggetohfe SseitnoFf .attacked arguments of S. If no ambiguity
Semantics for AFs are de ned as functions which assign to each AF F = (A; R) a set (F ) 2A of extensions. We consider for the functions cf , adm, stb, sem and stg which stand for con ict-free, admissible, stable, semi-stable and stage extensions, respectively.
De nition 2. Let F = (A; R) be an AF. A set S A is con ict-free (in F ), if there are no a; b 2 S, such that (a; b) 2 R. cf (F ) denotes the collection of sets being con ict-free in F . For a con ict-free set S 2 cf (F ), we say S 2 adm(F ), if each a 2 S is defended by S in F ; S 2 stb(F ), if eachT a[2TF+A; nSS2isstagt(tFac)k,eidf bthyeSre iins Fno; S 2 sem(F ), if S 2 adm(F ) and there is no T 2 adm(F ) with S [ SF+ T 2 cf (F ), with S [ SF+ T [ TF+.
We recall that for each AF F , stb(F ) stg (F ) cf (F ) and stb(F ) sem(F ) adm(F ); also stb(F ) = sem(F ) = stg (F ) in case stb(F ) 6= ;. Moreover, semantics 2 fstg ; stb; semg deliver incomparable sets, i.e. for all S; T 2 (F ), S T implies S = T ; the property is also referred to as I-maximal.
Next we de ne claim-augmented argumentation frameworks according to [
De nition 3. A claim-augmented argumentation framework (CAF) is a triple (A; R; claim) where (A; R) is an AF and claim : A ! C is a function which assigns a claim to each argument in A; C is a set of possible claims. The claim-function is extended to sets in the following way: For a set E A, claim(E) = fclaim(a) j a 2 Eg.
A CAF (A; R; claim) is called well-formed if fag(+A;R) = fbg(+A;R) for all a; b 2 A such that claim(a) = claim(b).
In [
Basic relations between di erent semantics carry over from standard AFs, i.e. for any CAF CF , stbc(CF ) semc(CF ) admc(CF ) and stbc(CF ) stgc(CF ) cfc(CF ); moreover, if stb(CF ) 6= ; then stbc(CF ) = semc(CF ) = stgc(CF ). However, the next example shows that we lose fundamental properties of semantics like I-maximality of stable, semi-stable and stage semantics.
Example 2. Let CF = (A; R; claim) with (A; R) = (fx1; x2; yg; f(x1; x2); (x2; x1); (x2; y)g) and claim(xi) = x, i 2, claim(y) = y. Then stbc(CF ) = semc(CF ) = stgc(CF ) = ffxg; fx; ygg. Note that CF is not well-formed. 3
For standard argumentation frameworks, the range of a set E of arguments is de ned as the union of E together with all arguments it attacks; hence a claim-centered variant of range-based semantics requires explicit concepts for the defeat of claims. In the current section, we will discuss defeat on claim-level and the range of a claim-set which both exhibit certain di erences to its argument-based counter-parts. In Sections 3.1, 3.2 and 3.3, we will discuss claim-centered variants of stable, semi-stable and stage semantics, respectively.
We will introduce the range of a claim-set S claim(A) in a CAF CF = (A; R; claim), that is, we will de ne, for any claim-set S, the set of all claims it defeats. Since each claim-set depends on a particular realization in the underlying AF (A; R), we will rst introduce claim-defeat on argument-level.
De nition 5. Let CF = (A; R; claim), E A and c 2 claim(A). We say that E defeats c i E attacks every a 2 A with claim(a) = c. We de ne dis CF (E) = fc 2 claim(A) j 8x 2 A; claim(x) = c 9y 2 E s.t. (y; x) 2 Rg. If no ambiguity arises, we drop the subscript CF .
Observe that disCF : A ! claim(A) is monotone, i.e. if E E0 then disCF (E) disCF (E0) for any E; E0 A.
Next we will consider claim-defeat with respect to a claim-set S independently of a particular realization. The general idea is to consider, for each realization E of S, the set of defeated claims disCF (E) as potential candidate to identify the range of S. Observe that, in contrast to the range of a set of arguments, the range of a set of claims S is in general not unique since S can possess multiple realizations; moreover, we restrict ourselves to -realizations of S for some semantics in order to exclude for example con icting realizations. De nition 6. Let CF = (A; R; claim), S claim(A) and consider a semantics . Then D ;CF (S) = fdisCF (E) j E 2 ((A; R)); claim(E) = Sg; moreover, R ;CF (S) = fS [ S0 j S0 2 D ;CF (S)g represents every possible range of S with respect to . If no ambiguity arises, we drop the subscript CF .
Observe that for every claim-set S and two semantics ; 0 with ((A; R)) 0((A; R)) it holds that D ;CF (S) D 0;CF (S). Indeed, if disCF (E) 2 D ;CF (S) for some E A, then E 2 ((A; R)) 0((A; R)), and thus disCF (E) 2 D 0;CF (S). Moreover notice that, in general, jRCF (S)j 1, that is, the range of a claim-set potentially consists of multiple alternatives. However, for well-formed CAFs CF , it holds that for every two sets E; E0 A with claim(E) = claim(E0), E+ = E0+, thus disCF (E) = disCF (E0). It follows that the range of a claim-set S is unique if the CAF is well-formed. This also implies that, for well-formed CAFs, the range is independent of the particular realization with respect to a semantics .
Lemma 1. Let CF = (A; R; claim) be well-formed and let S claim(A). Then jR ;CF (S)j = 1. 3.1
We will introduce two variants of stable semantics based on maximization on claim-level. The rst variant requires the underlying realization of a claim-set S to be con ict-free, while the second variant requires admissibility. We clarify the relation between both variants as well as the relation to i-stable semantics and compare them also with regard to I-maximality of their extensions.
De nition 7. Let CF = (A; R; claim) and S claim(A). S is a cf -cl-stable claim-set, in symbols S 2 cl -stbcf (CF ), i there exists S0 2 Dcf ;CF (S) such that S [ S0 = claim(A).
The proposed variant of claim-based stable semantics relaxes the de nition of inherited stable semantics in the way that it is no longer required that a stb-realization of a cf -cl-stable claim-set exists. Consider the CAF CF = (A; R; claim) from Figure 3 with claim(a1) = claim(a2) = a, claim(b) = b. Here, stbc(CF ) = ; but cl -stbcf (CF ) = ffagg: The cf -realization E = fa1g satis es disCF (E) = fbg and therefore, claim(E) [ disCF (E) = claim(A). Observe that CF is not well-formed. Furthermore notice that the cf -cl-stable claimset fag is in fact not adm-realizable in (A; R). Thus in contrast to standard AF semantics where each stable extension satis es admissibility, a cl -stbcf -realization in the underlying AF is not necessarily admissible. Thus we consider also a stronger notion of stable semantics which requires adm-realizability in the underlying AF. De nition 8. Let CF = (A; R; claim) and S claim(A). S is an adm-cl-stable set, in symbols S 2 cl -stbadm (CF ), if there exists S0 2 Dadm;CF (S) such that S [ S0 = claim(A).
Proposition 1. For any CF = (A; R; claim), stbc(CF ) cl -stbadm (CF ) cl -stbcf (CF ).
Proof. Let S 2 stbc(CF ) and consider a stb-realization E A. Observe that E 2 adm((A; R)). Let c 2 claim(A) n S, then for all x 2 A with claim(x) = c, x 2 A n E. Since E is stable in (A; R) we have that E attacks each argument x 2 A n E, therefore c 2 disCF (E). Thus disCF (E) = claim(A) n S and therefore we have found a set T = disCF (E) 2 Dadm;CF (S) with S [ T = claim(A), i.e. S 2 cl -stbadm (CF ). Moreover, cl -stbadm (CF ) cl -stbcf (CF ) follows from the fact that each admissible set is also con ict-free.
In the CAF CF = (A; R; claim) from Figure 3 we have cl -stbadm (CF ) 6= cl -stbcf (CF ) since cl -stbadm (CF ) = ; but cl -stbcf (CF ) = ffagg. A small modi cation of the CAF CF also shows that cl -stbadm (CF ) 6= stbc(CF ): Let CF 1 = (A; R n f(a2; a1)g; claim), then cl -stbadm (CF 1) = ffagg (witnessed by the adm-realization fa1g in (A; R)) but stbc(CF 1) = ;. Observe that both CF and CF 1 are not well-formed. We will show next that for well-formed CAFs, all considered variants of stable semantics are in fact equal.
Proposition 2. For any well-formed CAF CF = (A; R; claim), cl -stbadm (CF ) = cl -stbcf (CF ) = stbc(CF ). Proof. We will show that cl -stbcf (CF ) stbc(CF ), the other direction is due to Proposition 1.
Let S 2 cl -stbcf (CF ), then there is some set S0 2 Dcf ;CF (S) such that S [ S0 = claim(A) (recall that jDcf ;CF (S)j = 1 by Lemma 1). We consider a maximal cf -realization E A of S, that is, E 2 cf ((A; R)) with E = claim(S) and for every set E0 2 cf ((A; R)) with E0 = claim(S), E0 E. We show that ER+ = A n E. Let a b1
d c x 2 A n E and let claim(x) = c. If c 2= S, then c 2 S0 by de nition of cf -cl-stable semantics, thus E attacks x. Consider now the case c 2 S, i.e. there is an argument y 2 E such that claim(y) = c and observe that E [ fxg is not con ict-free by maximality of E; thus either (a) (x; x) 2 R or there is z 2 E such that either (b) (z; x) 2 R or (c) (x; z) 2 R. In case (a) then also (y; x) 2 R by well-formedness; in case (b) we are done; in case (c) we have (y; z) 2 R by well-formedness and therefore E is not con ict-free, contradiction.
Recall that i-stable claim-sets are not necessarily I-maximal (c.f. Example 2). As a consequence of
Proposition 1 we deduce that cf -cl-stable claim-sets are not I-maximal for arbitrary CAFs. In [
Proposition 3. For any well-formed CAF CF , both cl -stbcf (CF ) and cl -stbadm (CF ) are I-maximal. 3.2
We consider the following claim-based variant of semi-stable semantics which relaxes adm-cl-stable semantics by dropping the requirement that the range of a claim-set must consist of all claims in the framework. Instead, we consider claim-sets with maximal range.
De nition 9. Let CF = (A; R; claim), S claim(A) is a cl-semi-stable claim-set, in symbols S 2 cl -sem(CF ), i there exists S0 2 Dadm;CF (S) such that there is no T claim(A), T 0 2 Dadm;CF (T ) with S [ S0 T [ T 0.
As an example, consider the CAF CF = (A; R; claim) from Figure 4 with claim(b1) = claim(b2) = b and claim(x) = x for x 2 A n fb1; b2g. First notice that stbc(CF ) = cl -stbcf (CF ) = cl -stbadm (CF ) = ; since b1 and c are mutually attacking, thus either a or d are not attacked. Admissible claim-sets are S1 = fbg, S2 = fcg and S3 = fb; cg; then Dadm (S1) = ff;; fa; cgg and Dadm (S2) = Dadm (S3) = ffdgg. Observe that S2 is not cl-semi-stable, since S2 [ fdg S3 [ fdg; moreover, S1 is cl-semi-stable, since S1 [ fa; cg = fa; b; cg * S3 [ fdg S3 is cl-semi-stable, since S3 [ fdg = fb; c; dg * S1 [ fa; cg. It follows that cl-semi-stable claim-sets are not necessarily I-maximal. Notice that CF is not well-formed.
Since for well-formed CAFs, the range is unique and moreover, the function disCF is monotone, we conclude that cl-semi-stable semantics yields I-maximal claim-sets if well-formedness is satis ed.
This observation accords with the analysis of i-semi-stable claim-sets: I-maximality of i-semi-stable claim-sets is not guaranteed in the general case but for well-formed CAFs, as we show next.
Proof. Towards a contradiction, assume that there are two semi-stable claim-sets S; S0 2 semc(CF ) such that S S0. We consider sem-realizations E, E0 for S, S0 respectively and recall that semi-stable extensions are I-maximal on argument level, i.e. there is E E0 6= ;. Observe that E+ E0+ holds by well-formedness: Let x 2 E+, then there is y 2 E such that (y; x) 2 R. By assumption S S0, there exists z 2 E0 such that claim(y) = claim(z), thus (z; x) 2 R by well-formedness. It follows that every argument x 2 E n E0 is defended by E0 and thus E0 [ fxg [ (E0 [ fxg)+ E0 [ E0+, contradiction to E0 being semi-stable.
However, a closer comparison of cl-semi-stable and i-semi-stable semantics reveals the inherent di erence between maximization on claim- vs. argument-level. As already discussed in the introduction, the well-formed CAF CF from Example 1 yields semc(CF ) = ffagg while cl -sem(CF ) = ffag; fd; bgg, thus cl -sem(CF ) * semc(CF ). The following example extends Example 1 in order to show semc(CF ) * cl -sem(CF ). Example 3. We extend the CAF CF = (A; R; claim) from Example 1: Let CF = (A [ fb; f g; R0; claim0) with R0 = R [ f(f; f ); (f; b); (A3; f ); (A3; b); (b; A3)g and claim(x) = x for x 2 fb; f g. Then fag is the only i-semistable claim-set. For cl-semi-stable claim-sets, consider admc(CF ) = ffdg; fb; dg; fagg; inspecting the range yields fd; ag, fb; d; a; cg and fa; c; dg and thus cl -sem(CF ) = ffb; dgg. Observe that CF is indeed well-formed. a b c1 c2 a b c1 d1 (a) CAF CF 1 from Example 4.
(b) CAF CF 2 from Example 5. and, furthermore, (a; a) 2= R since a 2 E1; and (ii) E+ 2 claim(a) 2 claim(E2)). Therefore there is a con ict-free set E to the subset-maximality of E2 [ E2+.
Proof. Towards a contradiction, assume that there are S1; S2 2 stgc(CF ) such that S1 S2. Consider stg realizations E1; E2 of S1 and S2. So E1 [ E1+, E2 [ E2+ are incomparable and both subset-maximal. By well-formedness, E1+ E2+. Indeed, let x 2 A be attacked by E1, i.e. there is a 2 E1 such that (a; x) 2 R. Since claim(E1) claim(E2), there is b 2 E2 such that claim(b) = claim(a). By de nition of well-formedness, (b; x) 2 R. Since E+ E2 [ E2+, it must be the case that E1 6 E2 [ E2+, i.e. there exists a 2 E1 such that a 2= E2 and a 2= E+ 1 otherwise, then th2e.reLeist sEom=eEb22[ fEa2g,suthchenth(ia)tEb i2s cEon1+, icbtu-tfretheesninacelsoa 2b= 2E2+E2+ansdinacedoEes+not attack E2 (assume 1 E2+, contradiction) E+ by de nition of E (actually, E+ = E2+ since
A such that E [ E+ E2 [ E2+, contradiction
The following examples show that even for well-formed CAFs, i-stage and cl-stage semantics potentially yield di erent claim-sets.
Example 4. Let CF 1 = (A; R; claim) with (A; R) given in Figure 5a, claim(c1) = claim(c2) = c, claim(a) = a and claim(b) = b. Then fbg is the only i-stage claim-set. Observe that CF 1 is indeed well-formed. Consider now the cl-stage claim-sets. The con ict-free sets are fag and fbg. Inspecting the range yields fa; bg in both cases and therefore cl -stg (CF 1) = ffag; fbgg, i.e. cl -stg (CF 1) 6 stgc(CF 1).
Example 5. Let CF 2 = (A; R; claim) with (A; R) as in Figure 5b, claim(di) = d, claim(ci) = c, claim(a) = a, claim(b) = b. Then stgc(CF 2) = ffa; dg; fbgg but cl -stg (CF 1) = ffa; dgg, that is, stgc(CF 2) 6 cl -stg (CF 2). 3.4
We start with a general observation which clari es the relation between inherited and claim-level semantics for CAFs where every argument posses a unique claim. In that case, both variants coincide with the standard AF semantics interpreted in terms of the claims since the claims in the CAF can be identi ed with the arguments in the underlying AF. It follows that negative results concerning the relations between the semantics carry over from standard AFs, i.e. counter-examples showing that two AF semantics , are not in a subset-relation can be adapted to CAFs.
Proposition 8. For two semantics , , if there exists an AF F such that (F ) * (well-formed) CAF CF such that (CF ) * (CF ) for 2 fcl - ; cg, 2 fcl - ; cg. (F ) then there exists a semc admc cl -sem cfc cl -stg cl -stbadm
stbc (a) Relations for arbitrary CAFs.
cl -stbcf stgc
admc semc cl -sem cfc cl -stg
stgc stbc = cl -stbadm = cl -stbcf (b) Relations for well-formed CAFs.
Proof. The relations between inherited semantics have been already discussed in Section 2; moreover, stbc(CF ) cl -stbadm (CF ) cl -stbcf (CF ) for arbitrary CAFs by Proposition 1 and stbc(CF ) = cl -stbadm (CF ) = cl -stbcf (CF ) for each well-formed CAF CF by Proposition 2. Moreover, for any CAF CF , for every S 2 cl -stbadm (CF ) exists S0 2 Dadm;CF (S) such that S [ S0 = A and thus S 2 cl -sem(CF ); furthermore, since each S 2 cl -sem(CF ) is i-admissible by de nition, it follows that cl -stbadm (CF ) cl -sem(CF ) admc(CF ). A similar reasoning applies for the cf -based counter-parts, i.e. for every S 2 cl -stbcf (CF ) exists S0 2 Dcf ;CF (S) such that S [ S0 = A and thus S 2 cl -stg (CF ); moreover, every S 2 cl -stg (CF ) is con ict-free, thus cl -stbcf (CF ) cl -stg (CF ) cfc(CF ).
We present counter-examples for the remaining cases: By Corollary 8, there is a well-formed CAF CF such that (CF ) * (CF ) for (a) = cfc, 2 fadmc; cl -sem; semc; cl -stg ; stgc; cl -stbcf ; cl -stbadm ; stbcg; (b) = admc, 2 fcl -sem; semc; cl -stg ; stgc; cl -stbcf ; cl -stbadm ; stbcg; (c) 2 fcl -sem; semcg, 2 fcl -stg ; stgc; cl -stbcf ; cl -stbadm ; stbcg and (d) 2 fcl -stg ; stgcg, 2 fadmc; cl -sem; semc; cl -stbcf ; cl -stbadm ; stbcg. Example 3 shows that cl -sem(CF ) 6= semc(CF ) where CF is well-formed; moreover, cl -stg (CF ) 6= stgc(CF ) using (well-formed) CAFs from Example 4 and Example 5. Counter-examples for general CAFs and stable semantics have been discussed in Section 3.1.
Recall that for inherited semantics, stbc(CF ) = semc(CF ) = stgc(CF ) in case stbc(CF ) 6= ;. One can show that this does not extend to cl-stable semantics. However, we can obtain the following weaker version. Lemma 2. For any CAF CF = (A; R; claim), (a) cl -stbcf (CF ) 6= ; implies cl -stbcf (CF ) = cl -stg (CF ) and (b) cl -stbadm (CF ) 6= ; implies cl -stbadm (CF ) = cl -sem(CF ). 4
In this work, we investigated range-based semantics for claim-augmented argumentation frameworks. We
introduced inherited semi-stable and stage semantics in the spirit of [
For future work, we plan to extend our investigations to other semantics involving maximization, in particular
to preferred and naive semantics. Moreover, we want to connect our ndings with studies in [