You are viewing a javascript disabled version of the site. Please enable Javascript for this site to function properly.
Go to headerGo to navigationGo to searchGo to contentsGo to footer
In content section. Select this link to jump to navigation

On the expressive power of collective attacks

Abstract

In this paper, we consider argumentation frameworks with sets of attacking arguments (SETAFs) due to Nielsen and Parsons, an extension of Dung’s abstract argumentation frameworks that allow for collective attacks. We first provide a comprehensive analysis of the expressiveness of SETAFs under conflict-free, naive, stable, complete, admissible, preferred, semi-stable, and stage semantics. Our analysis shows that SETAFs are strictly more expressive than Dung AFs. Towards a uniform characterization of SETAFs and Dung AFs we provide general results on expressiveness which take the maximum degree of the collective attacks into account. Our results show that, for each k>0, SETAFs that allow for collective attacks of k+1 arguments are more expressive than SETAFs that only allow for collective attacks of at most k arguments.

1.Introduction

Abstract argumentation frameworks (AFs) as introduced by Dung in his seminal paper [6] are a core formalism in formal argumentation and have been extensively studied in the literature. A popular line of research investigates extensions of Dung AFs that allow for a richer syntax (see, e.g. [3]). In this work we consider frameworks with sets of attacking arguments (SETAFs) as introduced by Nielsen and Parsons [16] which generalize the binary attacks in Dung AFs to collective attacks such that a set of arguments B attacks another argument a but no proper subset of B attacks a. Figure 1 shows an example SETAF with three arguments a, b, and c. Each argument is jointly attacked by the two remaining arguments; in other words, the set {a,b} attacks c, {a,c} attacks b and {b,c} attacks a. Having only these three attacks indicates that a alone (and likewise b alone) is too weak to attack c, etc.

Standard semantics (i.e., admissible, complete, grounded, stable, preferred) for SETAFs have been defined in [16]. The crucial step towards these definitions is to fix the notion of conflict for SETAFs. In our example, S={a,b} is a conflict-free set since b – although being attacked by {a,c} – is not attacked by a alone (or by {a,b}), and likewise b is not attacked by a or {a,b}. {a,b,c}, on the other hand, is conflicting in this example. The definition of the actual semantics is then quite straight forward. For instance, stable semantics are defined according to the standard definition by Dung, i.e. are given by conflict-free sets that attack all remaining arguments. In our example, we have that the conflict-free sets {a,b}, {a,c}, and {b,c} satisfy this requirement and these three sets are indeed the stable extensions of this example SETAF. Building on the work of [16], Dvořák et al. [11] recently introduced semi-stable and stage semantics for SETAFs. The semantics as proposed in [11,16] make SETAFs a conservative generalization of Dung AFs in the sense that a SETAF that has only simple attacks is evaluated the same way as the corresponding Dung AF.

Fig. 1.

An example SETAF.

An example SETAF.

As illustrated in [16], there are several scenarios where arguments interact and can constitute an attack on another argument only if these arguments are jointly taken into account. Representing such a situation in Dung AFs often requires additional artificial arguments to “encode” the conjunction of arguments. This is also observed in a recent comprehensive investigation on translations between different abstract argumentation formalisms [17]. There, it is shown that SETAFs allow for more straightforward and compact encodings of support between arguments than AFs do. Also a recent paper [27] observes that for particular instantiations, SETAFs provide a more convenient target formalism than Dung AFs. However, to the best of our knowledge, there has not been a thorough investigation to which extent the concept of collective attacks increases the expressiveness of SETAFs compared to Dung AFs.

Characterizations and comparisons of the expressiveness of argumentation formalisms (and non-monotonic formalisms in general) have been identified as a fundamental basis in order to understand the different capabilities of formalisms [7,8,15,19,20]. A successful notion to compare the expressiveness of argumentation formalisms is the notion of the signature [7] of a formalism w.r.t. a semantics σ, that is the collection of all sets of σ-extensions that can be expressed with at least one argumentation framework. There exist exact characterizations for most of the semantics for Dung AFs [7] and Abstract Dialectical Frameworks (ADFs) [1820]. As already observed by Polberg [17] collective attacks allow to enforce certain sets of extensions that cannot be obtained with Dung AFs. This is easily illustrated by our example SETAF from Fig. 1 for which we already reported its stable extensions being {a,b}, {a,c} and {b,c}. However, there is no Dung AF that exactly has these three sets as its stable extensions; in other words, the collection {{a,b},{a,c},{b,c}} is not contained in the signature of stable semantics for Dung AFs. The reason is the limitation of attacks. In order to make {a,b} stable in a Dung AF, we need to attack the remaining argument c either via attack (a,c) or via attack (b,c). However, with the former attack {a,c} cannot be stable and with the latter {b,c} cannot be stable in such an AF.

Besides such basic observations, no general characterizations of the signatures for SETAFs have been presented so far, and thus the precise differences in expressiveness to Dung AFs and ADFs are still unclear. In particular, we are interested in questions like this: given an arbitrary set S of extensions that is incomparable (i.e. for each S,SS, SS implies S=S), does there exist a SETAF such that its preferred (naive, stable, semi-stable, stage) extensions are exactly given by S?

In this work we answer such questions by investigating the signatures of SETAFs for conflict-free, naive, stable, complete, admissible, preferred, semi-stable and stage semantics. Moreover, we investigate whether the maximum degree of joint attacks (throughout the paper, we refer to the cardinality of the set of arguments attacking another argument as the degree of the attack) affects the expressiveness of SETAFs. For this purpose, we also study the classes of k-SETAFs (k1) where attacks are restricted to degree at most k (the example SETAF in Fig. 1 is thus a 2-SETAF but not a 1-SETAF; 1-SETAFs in fact coincide with Dung AFs).

The main contributions of our work are as follows.

  • In Section 3 we provide full characterizations of the extension-based signatures of SETAFs for the semantics under consideration (cf. Main Theorem 1). By that we characterize the exact difference in expressiveness between Dung AFs and SETAFs when considering extension-based semantics.

  • In Section 4 we provide characterizations of signatures for k-SETAFs (cf. Main Theorem 2). Our results show that the degree of the allowed attacks is crucial for the expressiveness. That is, k-SETAFs form a strict hierarchy of expressiveness when considering different values for k, with k=1 covering the case for Dung AFs and unbounded k the case for general SETAFs.

Our results confirm that the notion of collective attacks is indeed quite powerful. In particular, the question mentioned above can be positively answered: each incomparable set can be realized by preferred, naive, stable, semi-stable, and stage semantics, thus showing that the signatures of these five semantics coincide for SETAFs. However, this only holds if we do not bound the maximum degree of collective attacks. Another interesting finding is that – in contrast to Dung AFs – the signature of conflict-free sets is not included in the signature of admissible sets; in other words there exists a set S of extensions for which we can find a SETAF that has S as its conflict-free sets, but there is no SETAF that has S as its admissible sets. This observation is already true for 2-SETAFs. These main results are illustrated in Fig. 2 where the relation between signatures Σσk is highlighted, thus comparing the landscape for AFs (Σσ1), k-SETAFs for given k2 (Σσk), and unbounded SETAFs (Σσ).

From a more general perspective, our results clarify the impact of generalizing the concept of attack in terms of the extensions such formalisms can jointly deliver. We also conclude that the concept of collective attack already yields a maximal impact in this sense: preferred and other semantics already are capable of realizing any incomparable set. We believe that results of this kind yield further insight in the inherent nature of argumentation semantics studied and thus contribute to the fundamentals of abstract argumentation.

Fig. 2.

Summary of results: the Venn diagrams illustrate the relations between the signatures of the different semantics in AFs (Σσ1), SETAFs (Σσ), and SETAFs with attacks of degree at most k (Σσk).

Summary of results: the Venn diagrams illustrate the relations between the signatures of the different semantics in AFs (Σσ1), SETAFs (Σσ∞), and SETAFs with attacks of degree at most k (Σσk).

A preliminary version of this paper was presented at COMMA 2018 [10]. Beside giving full proofs, detailed discussions and examples, the present paper extends the conference version by extending the results to semi-stable and stage semantics and also incorporates fundamental results on these semantics that where presented in a workshop paper [11]. Another addition concerns results for the signature for k-SETAF under complete semantics.

2.Preliminaries

We first introduce formal definitions of argumentation frameworks following [6,16] and then recall the relevant work on signatures.

2.1.Argumentation frameworks with collective attacks

Throughout the paper, we assume a countably infinite domain A of possible arguments.

Definition 1.

A SETAF is a pair F=(A,R) where AA is finite, and R(2A{})×A is the attack relation. For an integer k1, a k-SETAF is a SETAF (A,R) where for all (S,a)R, we have |S|k. The collection of all SETAFs (resp. k-SETAFs) over A is given as AFA (resp. AFAk).

We shall call 1-SETAFs, i.e. SETAFs that only allow for binary attacks, Dung argumentation frameworks (AFs) as they are equivalent to the AFs introduced in [6].

Definition 2.

Given a SETAF (A,R), we write SRb if there is a set SS with (S,b)R. Moreover, we write SRS if SRb for some bS.1 We drop subscript R in R if there is no ambiguity. For SA, we use SR+ to denote the set {bSRb} of argument attacked by S (in R), and define the range of S (w.r.t. R), denoted SR, as the set SSR+.

Example 1.

Recall the framework from the introduction, with arguments a,b,c where each pair of arguments jointly attacks the remaining argument. This is modeled by the SETAF (A,R) with arguments A={a,b,c} and attacks R={({a,b},c),({a,c},b),({b,c},a)}. In fact, this SETAF has been already presented in Fig. 1. Note that we have that {a,b}Rc but neither {a}Rc nor {b}Rc for this SETAF. On the other hand {a,b,c}Rc indeed holds.

The notions of conflict and defense naturally generalize to SETAFs.

Definition 3.

Given a SETAF F=(A,R), a set SA is conflicting in F if SRa for some aS. A set SA is conflict-free in F, if S is not conflicting in F, i.e. if S{a}S for each (S,a)R.

Definition 4.

Given a SETAF F=(A,R), an argument aA is defended (in F) by a set SA if for each BA, such that BRa, also SRB. A set T of arguments is defended (in F) by S if each aT is defended by S (in F).

The notion of defense can be equivalently characterized as follows: an argument aA is defended by a set SA if for each (B,a)R we have SRB.

Next, we introduce the semantics we study in this work. Besides conflict-free and admissible sets, these are the naive, stable, preferred, complete, grounded, stage, and semi-stable semantics, which we will abbreviate by naive, stb, pref, com, grd, stage, and sem, respectively. All semantics except semi-stable and stage are defined according to [16], while semi-stable and stage are straight forward generalizations of the according semantics for Dung AFs [4,21], which have been independently proposed in [11,13]. For a given semantics σ, σ(F) denotes the set of extensions of F under σ.

Definition 5.

Given a SETAF F=(A,R), we denote the set of all conflict-free sets in F as cf(F). Scf(F) is called admissible in F if S defends itself in F. We denote the set of admissible sets in F as adm(F). For a conflict-free set Scf(F), we say that

  • Snaive(F), if there is no Tcf(F) with TS,

  • Sstb(F), if Sa for all aAS,

  • Spref(F), if Sadm(F) and there is no Tadm(F) s.t. TS,

  • Scom(F), if Sadm(F) and aS for all aA defended by S,

  • Sgrd(F), if S=Tcom(F)T,

  • Sstage(F), if Tcf(F) with TRSR, and

  • Ssem(F), if Sadm(F) and Tadm(F) s.t. TRSR.

As shown in [16], most of the fundamental properties of Dung AFs extend to SETAFs. In particular, Dung’s fundamental lemma generalizes to SETAFs in the following way.

Lemma 1

Lemma 1([16]).

Given a SETAF F=(A,R), a set BA, and arguments a,bA that are defended by B in F. Then (a) B{a} is admissible in F and (b) B{a} defends b in F.

The following result is in the spirit of Dung’s fundamental lemma and is used later.

Lemma 2.

Given a SETAF F=(A,R) and two sets S,TA. If both S and T defend itself in F, then ST defends itself in F.

Proof.

Towards a contradiction assume that ST does not defend itself, i.e. there exists a set BA with B(ST) such that (ST)̸↦B. Consider BS. Since (ST)̸↦B also S̸↦B and thus S does not defend itself in F which is a contradiction to the assumption. The case where BT behaves symmetrically. □

The relationship between stable, preferred, complete, admissible, conflict-free and naive semantics has already been clarified in [16] and matches with the relations between the semantics for Dung AFs, i.e. for any SETAF F,

stb(F)pref(F)com(F)adm(F)cf(F)
and
stb(F)naive(F)cf(F).
Moreover, the grounded extension is the unique minimal complete extension for any SETAF F.

We quickly clarify the relation of semi-stable and stage semantics to the other semantics; all the proofs are straightforward adaptations of the corresponding proofs in Dung AFs.

Lemma 3.

stb(F)sem(F), for any SETAF F.

Proof.

Consider a SETAF F=(A,R). By the above we have that each stable extension E of F is also preferred and thus admissible in F. As E is stable we have that ER=A and thus there cannot be another admissible set D of F with ERDR. Hence Esem(F). □

Lemma 4.

stb(F)stage(F), for any SETAF F.

Proof.

Consider a SETAF F=(A,R). By definition, we have that each stable extension E is conflict-free. As Estb(F) we have that ER=A and thus there cannot be another conflict-free set D of F with ERDR. Hence Estage(F). □

Lemma 5.

sem(F)pref(F), for any SETAF F.

Proof.

Consider a SETAF F=(A,R). Towards a contradiction assume there is a semi-stable extension E of F that is not preferred. Then there is a preferred extension D of F with ED. Let xD such that xE and E̸↦Rx (otherwise there would be a conflict in D). As the range operator is monotone by definition, we have ERDR and as xER we obtain that ERDR. Hence, Esem(F), a contradiction to our initial assumption. □

Lemma 6.

stage(F)naive(F), for any SETAF F.

Proof.

Consider a SETAF F=(A,R). Towards a contradiction assume there is a stage extension E of F that is not naive. Then there is a naive extension D with ED. Let xD such that xE and E̸↦Rx. As the range operator is monotone by definition we have ERDR and as xER we obtain that ERDR. Hence, Estage(F), a contradiction to our initial assumption. □

We are thus able to complete the picture on the relationship between the semantics as follows. For every SETAF F, we have

(1)stb(F)sem(F)pref(F)com(F)adm(F)cf(F)
and
(2)stb(F)stage(F)naive(F)cf(F).

Moreover, the following property carries over from Dung AFs.

Lemma 7.

For any SETAF F=(A,R), if stb(F) then stb(F)=sem(F)=stage(F).

Proof.

Consider a SETAF F=(A,R) with stb(F). First consider stage semantics. As each stable extension is stage as well (cf. Lemma 4), we have that the range of each stage extension must be A (by the range maximality condition) and thus each stage extension is a stable extension. Hence, stb(F)=stage(F). Now consider semi-stable semantics. As each stable extension is semi-stable as well (cf. Lemma 3), we have that the range of each semi-stable extension must be A (by the range maximality condition) and thus each semi-stable extension is a stable extension. Hence, stb(F)=sem(F). □

2.2.Signatures

The concept of signatures of argumentation semantics was introduced in [7] to characterize the expressiveness of Dung AFs and has been extended to other argumentation frameworks [19,20]. Signatures characterize all possible sets of extensions, argumentation frameworks can provide for a given semantics.

Definition 6.

Let k1 be an integer. The signature Σσk of a semantics σ for k-SETAFs is defined as

Σσk={σ(F)FAFAk}.
For unrestricted SETAFs we use Σσ={σ(F)FAFA}. For SΣσk (resp. SΣσ) we say that S can be realized by k-SETAFs (resp. by SETAFs) under σ.

We require some further technical notions.

Definition 7.

Given S2A,

  • we use ArgsS to denote SSS, and

  • call S an extension-set (over A) if ArgsS is finite.

As only extension-sets can appear in the signature of a semantics we will tacitly assume that all sets S in our characterizations are extension-sets. Further, the arguments in ArgsS must be part of any SETAF realizing the extension set S.

For characterizing the signatures we make frequent use of the following concepts.

Definition 8.

Given S2A and EArgsS, we define

  • (a) the downward-closure of S as dcl(S)={SSSS};

  • (b) the set of potential conflicts in S as PAttS={SArgsSSdcl(S)};

  • (c) the completion-sets of E in S as CS(E)={SSES,SS,ESS}.

The downward-closure considers all subsets of sets in the extension-set. The set PAttS list all attacks between arguments in ArgsS that do not add a conflicts within sets SS. As all the semantics under our considerations are based on conflict-freeness this provides an upper bound on the attacks between arguments in PAttS we can use in our constructions. Finally, the completion sets for E are the subset minimal sets SS that contain E. In particular, if ES then E itself is the only completion set of E.

Example 2.

Let S={{a,b},{a,c},{b,c}}. We have ArgsS={a,b,c} and dcl(S)=S{{a},{b},{c},}. Furthermore, we have PAttS={{a,b,c}}, for E={a}, CS(E)={{a,b},{a,c}}, and for E={a,b,c}, CS(E)=.

Definition 9.

Let S2A. We call S

  • downward-closed if S=dcl(S);

  • incomparable if all elements SS are pairwise incomparable, i.e. for each S,SS, SS implies S=S;

  • tight if for all SS and aArgsS it holds that if S{a}S then there exists an sS such that {a,s}PAttS;

  • conflict-sensitive if for each A,BS such that ABS it holds that a,bAB:{a,b}PAttS;

  • com-closed if for each TS: if {a,b}PAttS for each a,bArgsT, then ArgsT has a unique completion-set in S, i.e. |CS(ArgsT)|=1.

Example 3.

Let S={{a,b},{b,c}}. Hence, PAttS={{a,c},{a,b,c}}. We observe that S is incomparable; moreover, S is tight: for S={a,b} and argument c, we have aS and {a,c}PAttS; for T={b,c} and argument a, we have cT and again {a,c}PAttS. Likewise, it can be checked that S is conflict-sensitive since aS, cT and {a,c}PAttS.

If we extend S to S={{a,b},{a,c},{b,c}}, one can check via the properties listed in Example 2 that S is neither tight nor conflict-sensitive. In anticipating the forthcoming result, this shows that S is not part of the signature of stable semantics for Dung AFs (the same is true for preferred and other incomparable semantics); an observation we already sketched in the introduction.

The main results for Dung AFs are summarized in the following theorem.

Theorem 1

Theorem 1([7]).

Characterizations of the signatures for Dung AFs are as follows:

Σcf1={SS is downward-closed and tight}Σnaive1={SS is incomparable and dcl(S) is tight}Σstb1={SS is incomparable and tight}Σstage1={SS is incomparable and tight}Σadm1={SS is conflict-sensitive and contains }Σpref1={SS is incomparable and conflict-sensitive}Σsem={SS is incomparable and conflict-sensitive}Σgrd1={S|S|=1}Σcom1{SS is com-closed and SS}

Note that the result for complete semantics does not yield an exact characterization. We will provide the exact characterization (which is not relevant for the upcoming section) later in Section 4.

Fig. 3.

Relations between signatures in Dung AFs (cf. Theorems 1 & 2).

Relations between signatures in Dung AFs (cf. Theorems 1 & 2).

The characterizations of Theorem 1 also allow to investigate the relations between signatures of different semantics. The relations between these signatures are also illustrated in Fig. 3.

Theorem 2

Theorem 2([7]).

The following relations hold

Σnaive1Σstage1Σpref1,Σcf1Σadm1Σcom1{dcl(S)SΣnaive1}=Σcf1,Σadm1{S{}SΣpref1}Σadm1Σpref1={{}}Σcom1Σpref1={{S}SA,|S|<}

3.Signatures of SETAFs with unrestricted collective attacks

In this section we give full characterizations of the SETAF signatures for the semantics under consideration. First, we consider grounded semantics. Grounded semantics, in SETAFs as well as in AFs, is a unique status semantics, i.e. it always yields a unique extension. Consequently, grounded semantics can only realize extension-sets that contain exactly one extension.

Proposition 1.

Σgrd=Σgrdk={S|S|=1}, for any integer k1.

Proof.

The grounded semantics always proposes a unique extension. An extension-set S={S} can be realized by the SETAF with arguments S and no attacks, i.e. by the SETAF (S,). □

That is for grounded semantics the signatures for AFs and (k-)SETAFs coincide. We continue with the signatures of stable and preferred semantics.

3.1.Signatures of stable and preferred semantics

For both semantics we have that an extension cannot be a subset of another extension and thus the extension-sets of these semantics are incomparable. With the following construction we show that, in turn, each incomparable extension-set S can be realized under stable and preferred semantics.

Definition 10.

Given an incomparable extension-set S containing at least one non-empty set we define the SETAF FSstb=(ArgsS,RSstb) with RSstb={(S,a)SS,aArgsSS}.

We first prove the desired result for stable semantics.

Proposition 2.

Σstb={SS is incomparable}.

Proof.

First, as stb(F)pref(F) and the latter is incomparable by definition we have that also stb(F) is incomparable for any SETAF F.

For S= we can use the SETAF F=({a},{({a},a)}) with stb(F)=, and for S={} we can use the empty SETAF F{}=({},{}) with stb(F{})={}. Given an incomparable set S containing at least one non-empty set, we make use of the SETAF FSstb, cf. Definition 10, and show that stb(FSstb)=S.

stb(FSstb)S: Consider SS. For each aArgsSS, we have (S,a)RSstb by construction. Moreover, as S is incomparable, we cannot have (S,a)RSstb with SS and aS. Hence, S is conflict-free in FSstb and thus Sstb(FSstb).

stb(FSstb)S: Consider SArgsS, such that SS. First, if there is an ES such that ES then for each argument aSE we have (E,a)RSstb and thus S attacks itself in FSstb. Hence, such an S is not stable. Alternatively, if there is no ES such that ES then (a) S does not attack any argument and (b) there is an argument aE that is not contained in S. Hence, S is not stable in FSstb either. □

We continue with preferred semantics. By definition the set of preferred extensions is incomparable. We show that being incomparable is also sufficient for an extension-set S to be realizable under preferred semantics.

Proposition 3.

Σpref={SS is incomparable}.

Proof.

First, pref(F) is incomparable and non-empty by definition (for any SETAF F).

For realizing S={}, consider the SETAF F{}=({a},{({a}),a}). We have pref(F{})={} as required. For realizing an incomparable set S containing at least one non-empty set, we again consider the SETAF FSstb (cf. Definition 10). We show that pref(FSstb)=S.

pref(FSstb)S: Consider SS. As shown in the proof of Proposition 2, Sstb(FSstb). By Relation (1), Spref(FSstb) follows.

pref(FSstb)S: Consider SArgsS, such that SS. First, if there is an ES such that ES, then there is an argument aSE such that (E,a)RSstb and thus S attacks itself in FSstb. Hence, Spref(FSstb). Thus let us consider the case where there is no ES such that ES. Then S does not attack any argument. Notice that by construction all arguments, except those arguments contained in all sets SS (we call them skeptically accepted arguments), are attacked by at least one set SS. If S contains an argument that is not skeptically accepted, S cannot be admissible in FSstb as it is attacked and has no outgoing attacks. On the other hand side if S only contains skeptically accepted arguments then it is a strict subset of some set in S and thus cannot be ⊆-maximal among the admissible sets of FSstb. That is, Spref(FSstb). □

The following theorem summarizes the results we have obtained so far.

Theorem 3.

We have Σstb={SS is incomparable} and Σpref=Σstb{}.

This characterization shows that SETAFs are strictly more expressible than AFs for stable and preferred semantics. While for AFs we require the extension-set S to be tight in order to be realizable under stb and conflict-sensitive to be realizable under pref, we can realize with SETAFs any extension-set S that is just incomparable. We already have illustrated this fact in Example 3. Note that for S={{a,b},{a,c},{b,c}}, the SETAF FSstb yields exactly the framework in our previous examples.

Remark 1.

Interestingly Σstb coincides with the stable signature for bipolar abstract dialectical frameworks (BADF) [19, Thm. 22]. That is, although BADFs allow for strictly more notions of attacks and even allows for support it does not provide more expressiveness than SETAFs when using stable semantics. It is worth to mention that when realizing an extension-set with the construction of [19, Thm. 22] one obtains a BADF whose acceptance conditions are all anti-monotonic, i.e., when the condition holds for a model SA then it holds for each model SS as well, and one can show that such an BADF can always be transformed into an equivalent SETAF (a similar observation is made in [26]).

3.2.Signatures of conflict-free and naive semantics

We next consider conflict-free and naive semantics. The characteristics of conflict-free sets is that each subset is again conflict-free. We will show that this property which is captured by the notion of downward-closure is also sufficient to realize an extension-set with a SETAF via its conflict-free sets. We again start by defining a SETAF construction, which is a slight refinement of the one from Definition 10.2

Definition 11.

Given a non-empty extension-set S, let FScf=(ArgsS,RScf) be the SETAF with RScf={(S,a)SS,aArgsS,S{a}PAttS}.

The conflict-free sets of FScf enjoy the following property which we will exploit for the characterizations of the signatures of conflict-free and naive semantics.

Lemma 8.

For each extension-set S, it holds that cf(FScf)=dcl(S).

Proof.

Let us show first that cf(FScf)dcl(S). Pick any Sdcl(S) and any attack (S,a)RScf. By construction, we have that (S{a})PAttS, and thus, (S{a})S. That is, S is conflict-free in FScf and therefore cf(FScf)dcl(S).

Let us show now that cf(FScf)dcl(S) also holds. Pick Sdcl(S), i.e., SPAttS, a subset maximal set S{ESES}, and some argument aSS. Then, by construction (S,a)R and, thus, S is not conflict-free in FScf. □

Proposition 4.

Σcf={SS is downward-closed}.

Proof.

By definition, if a set is conflict-free then all its subsets are conflict-free as well. Thus, we have that cf(F) is downward closed for all SETAFs F. This shows the ⊆-relation of the claim. For the ⊇-relation, let S be a non-empty and downward-closed extension-set. By Lemma 8 we have cf(FScf)=dcl(S) and thus also cf(FScf)=S. □

Proposition 5.

Σnaive={SS is incomparable}.

Proof.

For the ⊆-relation of the assertion, recall that, by definition, a set is naive if it is maximal conflict-free. Thus, we have that naive(F) is incomparable for all SETAFs F.

For the ⊇-relation, given an incomparable extension-set S, we consider the SETAF FScf (see Definition 11). We show that naive(FScf)=S. By Lemma 8 we have cf(FScf)=dcl(S). As S contains exactly the ⊆-maximal elements of dcl(S) and the naive extension of FScf are the ⊆-maximal elements of cf(FScf) we obtain naive(FScf)=S. □

The following theorem summarizes the characterizations of this subsection.

Theorem 4.

We have

  • Σcf={SS is downward-closed} and

  • Σnaive={SS is incomparable}.

In contrast, for realization with AFs and cf we require S to be tight and downward-closed and for naive we require that S is incomparable and that dcl(S) is tight.

Example 4.

Consider the downward-closed extension-set S={,{a},{b},{c},{a,b},{b,c},{a,c}}. As S is not tight there is no AF F with cf(F)=S, cf. Theorem 1. It can be checked that the SETAF ({a,b,c},(({a,b},c),({a,c},b),({b,c},a)) of our running example matches FScf as specified in Definition 11, and we have cf(FScf)=S. Also note that for S={{a,b},{b,c},{a,c}}, we have dcl(S)=S and naive(FScf)=S.

3.3.Signatures of semi-stable and stage semantics

Semi-stable and stage semantics are both based on the maximality of the range of their extensions. It thus turns out that we can reuse the construction from Definition 10.

Proposition 6.

Σsem={SS is incomparable}.

Proof.

By Lemma 5, sem(F)pref(F) holds for each SETAF F, we have that each SΣsem is incomparable. Now consider a non-empty incomparable extension-set S. By Proposition 2 there is a SETAF F with stb(F)=S and as S is non-empty, by Lemma 7, we also have sem(F)=S. □

Proposition 7.

Σstage={SS is incomparable}.

Proof.

By Lemma 6, for each SETAF F, stage(F)naive(F). We thus have that each SΣstage is incomparable. Now consider a non-empty incomparable extension-set S. By Proposition 2 there is a SETAF F with stb(F)=S and as S is non-empty, by Lemma 7, we also have stage(F)=S. □

The following theorem summarizes these easy results.

Theorem 5.

We have Σstage=Σsem={SS is incomparable}.

Together with the previous results, it turns out that for SETAFs the expressibility of naive, preferred, semi-stable, and stage semantics coincides. Moreover, stable semantics only differs w.r.t. the empty set of extensions. Hence, for all these semantics SETAFs are strictly more expressible than AFs. In fact, they are all maximal expressible if we require incomparability of extensions.

It remains to provide the SETAF signatures for admissible and complete semantics. As we will see, in contrast to AF signatures (where we have Σcf1Σadm1) Σadm is not a superset of Σcf. Moreover, for complete semantics, we can find a concise characterization by generalizing the notion of com-closed.

3.4.Signature of admissible semantics

In order the characterize the signature of admissible semantics in SETAFs we first generalize the notion of an extension-set being conflict-sensitive (cf. Definition 9) to SETAFs. That is, instead of requiring that if two sets A,B in the extension-set S whose union AB does not appear in S allow for a binary conflict, we now only require that they allow for conflicts (A,b), (B,a) with aA,bB.

Definition 12.

A set S2A is called set-conflict-sensitive if for each T,US such that TUS it holds that uU:T{u}PAttS.

Recall that all extension-sets realizable with the admissible semantics with Dung AFs are conflict-sensitive (and contain the empty extensions). The next result generalizes this property to SETAFs.

Lemma 9.

For any SETAF F, adm(F) is set-conflict-sensitive and contains ∅.

Proof.

Let F=(A,R) be a SETAF. First, notice that the empty set is always admissible in F. Next assume there are two sets T, U admissible in F such that the set C=TU is not admissible in F. By Lemma 2 the set C defends itself against all attackers in F and thus C must be conflicting in F, i.e. there exists an attack (B,a)R with SC and aC.

  • If aT then, as T is conflict-free in F, BU. Moreover, as T is admissible in F it has to defend itself against (B,a), i.e. there is an attack (T,u)R with TT and uBU. Hence, we have T{u}PAttadm(F) and thus T{u}PAttadm(F).

  • If aU then, as U is conflict-free in F, BT. Moreover, as U is admissible in F it has to defend itself against (B,a), i.e. there is an attack (U,t)R with UU and tBT. Now, as T is admissible in F as well, there is also an attack (T,u)R with TT and uUU. Hence, we have T{u}PAttadm(F) and thus T{u}PAttadm(F).

We obtain that adm(F) is set-conflict-sensitive. □

Furthermore, it turns out that S being set-conflict-sensitive (and containing the empty set) is also sufficient for being realizable in SETAFs under admissible semantics. The forthcoming two propositions give us some hint how to prove this claim: we reuse the conflict-free framework of Definition 11 and combine it with a framework that realizes the union-closure of the extension-set, as defined next.

Definition 13.

A set S2A is said to be union-closed if S and each pair A,BS satisfies ABS. Let us denote by ucl(S) the ⊆-minimal union-closed extension-set such that Sucl(S).

Proposition 8.

Let S be a set-conflict-sensitive extension-set that contains ∅. Then, we have that S=dcl(S)ucl(S).

Proof.

Pick any set-conflict-sensitive S and let S=dcl(S) and S=ucl(S). By construction, we have that S is downward-closed, that S is union-closed, that SS and that SSS. Hence, it only remains to be shown that SSS also holds. Suppose for the sake of contradiction that there is some set C(SS)S. Since CSS, by construction, C must be of the form C=T for some TS. W.l.o.g. we can assume that |T|=2, i.e., C=ST with S,TS. Moreover, since S is set-conflict-sensitive, CS implies that there is some bT such that S{b}PAttS. Furthermore, since CS, there is also some SS such that CS and, thus, we have S{b}STS which is a contradiction. Hence, it must be that SSS and SS=S hold. □

Proposition 9.

Let F1=(A1,R1) and F2=(A2,R2) be two SETAFs and let S(A1A2) be a set of arguments. Then,

  • (1) S is conflict-free in F1F2=(A1A2,R1R2) iff S is conflict-free in both F1 and F2; and

  • (2) if S is admissible in both F1 and F2, then S is admissible in F1F2=(A1A2,R1R2).

Proof.

(1) Consider some Scf(F1F2), i.e., there is an attack (A,b)(R1R2) with A{b}S. Hence, (A,b)Ri for some i{1,2} and thus Scf(Fi). For the reverse direction consider some Scf(Fi) for some i{1,2}, i.e., there is an attack (A,b)(Ri) with A{b}S. Then (A,b)R1R2 and thus Scf(F1F2).

(2) First, note that if S is admissible in both F1 and F2, it is also conflict-free in both F1 and F2 and, by (1) this implies that S is conflict-free in F1F2. Let us show us that S also defends itself in F1F2. Pick any bS and (A,b)(R1R2). Hence, (A,b)Ri for some i{1,2} and, since S is admissible in both F1 and F2, it follows that there is a CS and aA such that (C,a)Ri. That is, for every argument bS and attack (A,b)(R1R2), there is some CS and aA such that (C,a)(R1R2). Hence, S is admissible in F1F2. □

The next two lemmas analyze the SETAF FScf from Definition 11 w.r.t. admissible semantics.

Lemma 10.

Let S be a set-conflict-sensitive extension-set that contains ∅ and SArgsS be some set of arguments such that S=T for some subset TS. Then, we have that Scf(FScf) implies SS.

Proof.

Consider such a set S=T with Scf(FScf) and pick AT such that AS and there is no AT such that AA and AS. Note that such A always exists because =S. We also define A=A. Towards a contradiction assume that AT and pick any BTA. Then, by construction, we have that A,BS and that (AB)S. Furthermore, since S is set-conflict-sensitive, it follows that there is bB such that (A{b})PAttS. This implies that there is an attack (A,b)RScf and, thus, (A{b})cf(FScf). Finally, since (A{b})(AB)S and cf(FScf) is downward-closed, this implies Scf(FScf) which is a contradiction with the assumption that Scf(FScf). Hence, it must be that A=T and, thus, that A=S holds. Since AS by construction, this implies SS. □

Lemma 11.

Let S be a set-conflict-sensitive extension-set that contains ∅. Then, we have that Sadm(FScf).

Proof.

Pick any set SS, any argument aS and any attack (S,a)RScf. Then, (SS)S and, since S,SS and S is conflict-sensitive, it follows that there is some bS such that (S{b})PAttS. This implies that (S,b)RScf and, thus, that S defends a against (S,a) in FScf. Hence, S defends itself against all attacks in RScf. □

Finally, we expand FScf by additional arguments and attacks that ensure that only sets SS are admissible in the resulting SETAF FSadm. In particular, for each argument a we add an argument xa that attacks a and itself, and is only attacked by sets SS that contain a.

Definition 14.

Given an extension S set we define FSucl=(ASucl,RSucl) with

ASucl=ArgsS{xaaArgsS}andRSucl={({xa},a)aArgsS}{({xa},xa)aArgsS}{(S,xa)SS and aS}.
We then define FSadm=(ASadm,RSadm)=(FScfFSucl).

We next illustrate the construction on an example

Example 5.

Consider the extension-set S={,{a,b},{a,c}}. We have ArgsS={a,b,c} and we add three additional arguments {xa,xb,xc}, one for each of the existing arguments. That is, ASadm={a,b,c,xa,xb,xc}. Now we add attacks between arguments a,b,c following the construction for conflict-free semantics from Definition 11. That is we add the attacks RScf={({a,b},c),({a,c},b)}. Now we have adm(ArgsS,RScf)={,{a},{a,b},{a,c}}, that is we still have the unwanted extension {a}. We now use the additional arguments {xa,xb,xc} to avoid such extensions. The arguments xi are self-attacking, i.e. we have attacks {({xa},xa),({xb},xb),({xc},xc)} in RSucl, and attack their corresponding argument i, i.e. we have attacks {({xa},a),({xb},b),({xc},c)} in RSucl, and are only attacked by those sets SS that contain i, i.e. we have attacks {({a,b},xa),({a,b},xb),({a,c},xa),({a,c},xc)} in RSucl. That is, RSadm={({xa},xa),({xb},xb),({xc},xc),({xa},a),({xb},b),({xc},c),({a,b},c),({a,b},xa), ({a,b},xb),({a,c},b),{a,c},xa),({a,c},xc) and we have adm(ASadm,RSadm)={,{a,b},{a,c}} as now {a} does not defend it self against the attack ({xa},a).

With the following lemma we show that FSucl can realize ucl(S).

Lemma 12.

For every extension-set S that is set-conflict-sensitive and contains ∅, we have that ucl(S)adm(FSucl).

Proof.

Let us first show that Sadm(Fucl). Pick any AS, aA and (S,a)RSucl. Then, by construction, we have that S={xa} and, since aA, that (A,xa)RSucl, so A also defends itself against all attacks in RSucl. Hence, we have that Sadm(FSucl). Pick now A,BS. We already know that A,Badm(FSucl) and, moreover, AB defends itself in FSucl (Lemma 2). Furthermore, by construction, there are no attacks between elements of AB and thus ABadm(FSucl). □

It remains to combine the results for the SETAFs FScf, FSucl with Proposition 8 to arrive at the desired characterization result.

Lemma 13.

For every extension-set S that is set-conflict-sensitive and contains ∅, we have that adm(FSadm)=S.

Proof.

From Proposition 8, we have that S=dcl(S)ucl(S). Then, from Lemmas 11 and 12, we get that Sadm(FScf)adm(FSucl). Furthermore, from Proposition 9, this implies that Sadm(FSadm).

Let us show that adm(FSadm)S also holds. Pick any Aadm(FSadm). Then, for every argument aA, there is an attack ({xa},a)RSadm by construction, and so there must be an attack (Ta,{xa})RSadm with TaA. Furthermore, by construction, we also have that TaS and aTa. Let T={TaAaA}S and C=T. Then, we have that C=A and, from Lemma 10 and the fact that Aadm(FSadm)cf(FSadm)cf(FScf), it follows that, AS. □

Now we can give an exact characterization of Σadm.

Theorem 6.

Σadm={SS is set-conflict-sensitive and contains }.

Dung AFs require that an extension-set S is conflict-sensitive in order to be realizable under admissible semantics. Being set-conflict-sensitive is a strictly weaker condition as illustrated in the following example.

Example 6.

Consider the extension-set S={,{a,b},{b,c},{a,c}}. As {a,b,c}S but {a,b},{b,c}S (and thus neither {a,c}PAttS nor {b,c}PAttS), the set S is not conflict-sensitive. Thus, there is no Dung AF F with adm(F)=S. On the other hand, S is set-conflict-sensitive thanks to {a,b,c}PAttS. Indeed, one can verify that our running example SETAF F satisfies adm(F)=S.

On the other hand, the set S={,{a},{b},{c},{a,b},{b,c},{a,c}}Σcf from Example 4 is not set-conflict-sensitive. Take A={a} and B={b,c}. Then ABS but neither {a,b}PAttS nor {a,c}PAttS. Hence, by Theorem 6, there is no SETAF F with adm(F)=S. This example also shows that the converse of Proposition 8 does not hold and that satisfying S=dcl(S)ucl(S) is a necessary, but not a sufficient condition. Indeed, in our example we have dcl(S)=S, ucl(S)=S{{a,b,c}} and S=dcl(S)ucl(S).

3.5.Signature of complete semantics

Finally, we consider the signature of complete semantics. First, recall that the completion-sets CS(E) of a set EArgsS in S are the ⊆-minimal sets SS with ES. Next we introduce the notion of an extension-set to be set-com-closed which generalizes the concept of being com-closed from Definition 8 and allows for an exact characterization of the signature of complete semantics. The intuition is that if we pick some elements from S then either the union of these sets has a unique completion or we can draw an attack within this set.

Definition 15.

A set S2A is called set-com-closed iff, for each T,US with T=ArgsT, U=ArgsU,

  • (1) |CS(TU)|1, and

  • (2) if T,Udcl(S) and |CS(TU)|=0, then there is an argument uU such that T{u}PAttS.

Intuitively the set of complete extensions is set-com-closed because whenever the union of some complete extensions has no conflict, by Lemma 2, then this union is admissible and there is a unique minimal complete extensions containing this admissible set. Moreover, the grounded extensions is the intersection of all complete extensions and complete as well.

Lemma 14.

For every SETAF F we have that (a) the extension-set com(F) is set-com-closed and (b) com(F)com(F).

Proof.

First, notice that com(F)=grd(F) and as the grounded extension is complete we obtain (b). In order to show (a) consider extension-sets T,Ucom(F) and sets T=T, U=U such that T,Udcl(com(F)). From T,Udcl(com(F)), it follows that T,Ucf(F) and from T=T, U=U with T,Ucom(F) it follows that T and U defend themselves. Hence, we get T,Uadm(F). If in addition we have TUcf(F), then by Lemma 2 we have that TUadm(F) and thus by Lemma 1 there is a unique ⊆-minimal complete extension Ecom(F) with TUE, i.e. |Ccom(F)(TU)|=1. If TUcf(F) then there exists an attack (S,a)R with STU and aTU.

  • If aT, as T is admissible, there is an attack (T,u) with TT and uSTU. Thus, T{u}PAttcom(F).

  • If aU, as U is admissible, there is an attack (U,s) with UU and sSUT. Now, as T is admissible, there is an attack (T,u) with TT and uUU. Thus T{u}PAttcom(F).

In both cases we have an uU such that T{u}PAttcom(F) and thus com(F) is set-com-closed. □

Our realization for complete semantics is based on the construction for the admissible semantics given in Definition 14. First, given an extension-set S, by reduced(S)={SSSS}, we denote a reduced extension-set whose corresponding ground extension is empty. Let S=reduced(S). We then realize S=dcl(S)ucl(S)={TTS,Tdcl(S)} and add further attacks such that each set ES defends all arguments of the unique set in CS(E). In the following we use CS(E) to denote the unique element of CS(E) iff |CS(E)|=1 and the empty set otherwise.

Definition 16.

Given an extension-set S, let S=reduced(S) and S=dcl(S)ucl(S). Then, by FScom=(ArgsSASadm,RScom) we denote a SETAF with RScom=RSadmR and where R={(AB,xa)A,BS{},aCS(AB)}.

We next illustrate the above construction on an example.

Example 7.

Consider the extensions set S={{d},{a,d},{b,d},{a,b,c,d}}. First we extract the minimal extension {d} from S and obtain S=reduced(S)={,{a},{b},{a,b,c}} as well as S={,{a},{b},{a,b},{a,b,c}}, i.e., S differs from S only by the extension {a,b}. In the next step we build an SETAF that realizes S under admissible semantics. Following the construction of Definition 14 we get arguments ASadm={a,b,c,xa,xb,xc} and attacks RSadm={({xa},xa),({xa},a),({xb},xb),({xb},b),({xc},xc),({xc},c)}{({a},xa),({b},xb),({a,b},xa), ({a,b},xb),({a,b,c},xa),({a,b,c},xb),({a,b,c},xc)}. We now have that adm(ASadm,RSadm)=S. The only attack added by R is ({a,b},xc), which ensures that {a,b} is not complete as it defends c. Thus we have com(ASadm,RSadmR)=S. Finally we also add the argument d to the SETAF (without any attacks) and obtain that FScom=({a,b,c,d,xa,xb,xc},{({xa},xa),({xa},a),({xb},xb),({xb},b),({xc},xc), ({xc},c),({a},xa),({b},xb), ({a,b},xa),({a,b},xb),({a,b,c},xa),({a,b,c},xb), ({a,b,c},xc)},({a,b},xc))} and com(FScom)=S. Finally, by removing redundant attacks, i.e. attacks (S,a) such that there is an attack (S,a) with SS, the attack relation of FScom simplifies to {({xa},xa),({xa},a),({xb},xb),({xb},b),({xc},xc),({xc},c), ({a},xa),({b},xb),({a,b},xc))}.

One can show that this construction realizes extension-sets with complete semantics whenever possible.

Lemma 15.

For every extension-set S that is set-com-closed and satisfies SS, we have that com(FScom)=S.

Proof.

Consider the SETAF FScom from Definition 16. Let S=reduced(S), S=dcl(S)ucl(S) and let us show first that com(FScom)=S. Notice that S is still set-com-closed and S.

In order to apply the construction for admissible semantics on S we next show that S is set-conflict-sensitive. Consider T,US such that TUS. Then, by construction of S, we have that TUdcl(S) and thus Ccom(F)(TU)=. Now as S is set-com-closed there is an argument uU such that T{u}PAttS. That is, for T,US such that TUS there is an argument uU such that T{u}PAttS. Hence, the extension-set S is set-conflict-sensitive and, from Lemma 13, it follows that adm(FSadm)=S.

Now consider the new attacks in R and how they affect the admissibility of sets. Notice that only auxiliary arguments xa are attacked and thus each set that is admissible in FSadm is admissible in FScom as well (Proposition 9, condition (2)). That is, we have adm(FSadm)adm(FScom). Let us show Scom(FScom). Consider SSS. By the above, we have that Sadm(FSadm) and it remains to be shown that S does not defend any aArgsSS, i.e., does not attack any xa for aArgsSS. By construction of FScom the set S only attacks arguments xa with aS and thus Scom(FScom) follows. The other way around, let us show Scom(FScom). Consider Sadm(FScom). We next show that if SS then Scom(FScom). To this end we consider two cases.

  • Sadm(FScom)S: Notice that S=adm(FSadm). Consider a set S that is admissible in FScom but not in FSadm. This can only be because of the attacks introduced with R. That is, there is some xs with sS that prevents that S is admissible in FSadm and an attack (AB,xs)R with which S defends itself against xs in FScom. That is A,BS and, by the definition of R, we have that there is a unique completion C=CS(AB) and sC (recall that in R we only draw attacks for AB with a unique completion). As CSS and sC, by construction, there is an attack (C,xs) in FSadm That is, if CS then S attacks xs in FSadm, a contradiction to our initial assumption. Hence we have CS. Now we can argue that in FScom, S defends all arguments in C and thus S is not complete. To this end let cCS. By construction AB (and thus S) attacks all xa with aC. Now consider a set DS that attacks c. As C is admissible in FSadm, we have that there is a dD such that (C,d)RSadm. By construction we have C{d}PAtt(S) and thus also AB{d}PAtt(S). As ABS, we then by construction have (AB,d)RSadm. That is AB defends c against both possible kinds of attackers and thus defends c.

  • SSS: Then, there is a set TS such that T=S and Sdcl(S). As S is set-com-closed for each A,BS with A,BS, we have a unique completion set CS(AB) (as ABdcl(S) we cannot have a conflict in AB. Towards a contradiction assume that for all A,BS such that A,BS we have CS(AB)S. Then we can iteratively replace A,BT by CS(AB) and we end up with a single set in T. But then SS, a contradiction. Thus there are two sets A,BS such that A,BS and ABS, and there is also a unique set CCS(AB) with CS. Let cCS, we next argue the S defends c and thus is not complete. By construction AB (and thus S) attacks all xa with aC. Now consider a set DS that attacks c. As C is admissible in FSadm we have that there is a dD such that (C,d)RSadm. By construction we have C{d}PAtt(S) and thus also AB{d}PAtt(S). As ABS, by construction we have (AB,d)RSadm. That is AB defends c against both possible kinds of attackers and thus defends c.

Combining both cases we obtain that if SS then Scom(FScom). Finally, just note that FScom just adds to FScom the arguments in S as unattacked. Hence, Scom(FScom) iff (SS)com(FScom) and, thus, com(FScom)=S. □

This now gives a complete characterization of the signature for complete semantics.

Theorem 7.

Σcom={SS is set-com-closed and SS}.

Notice that when considering AFs not all extension-sets that are com-closed and satisfy SS are realizable with the complete semantics and a full characterization of complete semantics has been left open in [7] and has been resolved only recently [14]. Compared to this rather involved characterization, which we will review in Section 4.4, the above result provides a natural and easy-to-check characterization.

Example 8.

Consider the extension-set S={,{a},{b},{c},{a,b,c},{a,d,e},{b,d,f}, {x,c}, {x,d}} which cannot be realized with AFs [7, Example 8]. We next show that S set-com-closed. To this end we consider set the unions TU of sets with T=ArgsT and U=ArgsU with T,US. The first condition of S being set-com-closed is verified as follows.

  • (1) Whenever TUS we have |CS(TU)|=1 by the definition of CS.

  • (2) Whenever TUdclS then |CS(TU)|=0 by the definition of CS.

  • (3) It only remains to consider T,U{{a},{b},{c}} with TU we have that CS({a,b})=CS({a,c})=CS({b,c})={{a,b,c}}, i.e. |CS(TU)|=1.

For the second condition we are interested in the choices of T,U where T,Udcl(S), i.e. we have T,US{{a,b},{a,c},{b,c}}. We have to show that whenever TUdcl(S) then T{u}PAttS for some uU.
  • Consider T={a}, then for U={b,d,f} we have {a,f}PAttS, and for U{{x,c},{x,d}} we have {a,x}PAttS.

  • Consider T={b}, then for U={a,d,e} we have {b,e}PAttS, for U{{x,c},{x,d}} we have {b,x}PAttS.

  • Consider T={c}, then for U{{a,d,e},{b,d,f}} we have {c,d}PAttS, and for U={x,d} we have {c,d}PAttS.

  • Consider T={a,b}, then for U={a,d,e} we have {a,b,e}PAttS for U={b,d,f} we have {a,b,f}PAttS,and for U{{x,c},{x,d}} we have {a,b,x}PAttS.

  • Consider T={a,c}, then for U={a,d,e} we have {a,c,d}PAttS, for U={b,d,f} we have {a,c,f}PAttS, and for U{{x,c},{x,d}} we have {a,c,x}PAttS.

  • Consider T={b,c}, then for U={a,d,e} we have {b,c,e}PAttS, for U={b,d,f} we have {b,c,d}PAttS, for U{{x,c},{x,d}} we have {b,c,x}PAttS.

  • Consider T={a,b,c}, then for U={a,d,e} we have {a,b,c,e}PAttS, for U={b,d,f} we have {a,b,c,d}PAttS, for U{{x,c},{x,d}} we have {a,b,c,x}PAttS.

  • Consider T={a,d,e}, then for U{{b},{a,b},{b,c},{a,b,c},{b,d,f}} we have {a,d,e,b}PAttS, for U{{c},{a,c},{x,c}} we have {a,d,e,c}PAttS, and for U={x,d} we have {a,d,e,x}PAttS.

  • Consider T={b,d,f}, then for U{{a},{a,b},{a,c},{a,b,c},{a,d,e}} we have {b,d,f,a}PAttS, for U{{c},{b,c},{x,c}} we have {b,d,f,c}PAttS, and for U={x,d} we have {b,d,f,x}PAttS.

  • Consider T={x,c}, then for U{{a},{a,b},{a,c},{a,b,c},{a,d,e}} we have {x,c,a}PAttS, for U{{b},{b,c},{b,d,f}} we have {x,c,b}PAttS, and for U={x,d} we have {x,c,d}PAttS.

  • Consider T={x,d}, then for U{{a},{a,b},{a,c},{a,b,c},{a,d,e}} we have {x,d,a}PAttS, for U{{b},{b,c},{b,d,f}} we have {x,d,b}PAttS, and for U{{c},{x,c}} we have {x,d,c}PAttS.

This shows that S is set-com-closed and thus com(FScom)=S.

3.6.Discussion of results

Our characterizations of the signatures of different semantics in SETAFs (cf. Theorems 37) are summarized in the following theorem.

Main Theorem 1.

Characterizations of the signatures for general SETAFs are as follows:

Σcf={SS is downward-closed}Σnaive={SS is incomparable}Σstb={SS is incomparable}Σadm={SS is set-conflict-sensitive and contains }Σpref={SS is incomparable}Σcom={SS is set-com-closed and SS}Σsem={SS is incomparable}Σstage={SS is incomparable}

Let us now consider the relations between the signatures of the different semantics. First for the semantics possessing incomparable extension-sets we have

Σnaive=Σstb{}=Σpref=Σsem=Σstage.
Hence, compared to Dung AFs, we observe that all I-maximal semantics are equally powerful in terms of SETAFs (modulo the empty extensions-set).

It remains to investigate the relations between admissible, complete, and conflict-free semantics. First we show that, as for Dung AFs, every extension-set that is set-conflict-sensitive is also set-com-closed and thus ΣadmΣcom.

Proposition 10.

Every extension-set S that is set-conflict-sensitive is also set-com-closed.

Proof.

Towards a contradiction assume S is not set-com-closed. Consider T,US, T=ArgsT and U=ArgsU such that one of the two conditions for S being set-com-closed is violated. Let us first assume condition (1) is violated, i.e. |CS(TU)|2. Then we have that TUdcl(S) and thus, as S is set-conflict-sensitive, TUS. The latter implies that CS(TU)={TU} which is in contradiction to |CS(TU)|2. Let us now assume that condition (2) is violated, i.e. T,Udcl(S), |CS(TU)|=0, and there is no argument uU such that T{u}PAttS. As T,Udcl(S) and S is set-conflict-sensitive, we have that T,US. Moreover, as |CS(TU)|=0 we have TUS, and thus, as S is set-conflict-sensitive, there is a bU:T{b}PAttS, a contradiction to our initial assumption. □

Next, we give an example of an extension-set SΣcom but SΣadm and thus show ΣadmΣcom.

Example 9.

Consider the extension-set S={,{a},{b},{a,b,c}}. The set is not set-conflict sensitive as the set {a} cannot attack any argument from {b} and {a,b}S. However, S can be easily verified to be set-com-closed (as |CS({a,b})|=1) and thus SΣcom.

In contrast to Dung AFs we have that ΣcfΣadm as we have already seen in Example 6. We next continue this example to show that also ΣcfΣcom.

Example 10.

Reconsider the extension-set S={,{a},{b},{c},{a,b},{b,c},{a,c}}Σcf from Example 6, which is not set-com-closed. Take T={a} and U={b,c}. Then TUdcl(S) and thus |CS(TU)|=0, but neither {a,b}PAttS nor {a,c}PAttS. Hence, by Theorem 7, there is no SETAF F with com(F)=S.

Likewise, ΣcfΣadm is easy to see. In Example 6, we have argued that S={,{a,b},{a,c},{b,c}}Σadm, but since S is not downward-closed, SΣcf. By Proposition 10, ΣcfΣcom follows, as well.

Finally, we show that whatever can be realized with cf and com semantics can be also realized with adm semantics.

Proposition 11.

ΣcfΣcomΣadm.

Proof.

Consider SΣcfΣcom, i.e., a downward-closed and set-com-closed extension-set. Towards a contradiction assume S is not set-conflict-sensitive. That is, there are A,BS such that ABS and there is no bB such that A{b}PAttS. As S is downward-closed there is no CS with ABC and thus |CS({a,b})|=0. Now as S is set-com-closed there is an argument bB such that A{b}PAttS, a contradiction to the above. □

The relations between the signatures of the different semantics in SETAFs are illustrated in Fig. 4.

Fig. 4.

Relations between signatures in SETAFs (cf. Main Theorem 1).

Relations between signatures in SETAFs (cf. Main Theorem 1).

4.Signatures of SETAFs with collective attacks of bounded degree

We now investigate how the degree of collective attacks affects the expressiveness, i.e. we study the signatures of k-SETAFs. Notice that in all the constructions of the last section we used attacks of unbounded degree, since the actual degree typically depended on the size of the extensions.

We first generalize the properties used in our signatures by adding a parameter k.

Definition 17.

The possible conflicts in a k-SETAF w.r.t. an extension-set S are defined as

PAttSk={SArgsS|S|k+1 and Sdcl(S)}.

Example 11.

Let S={{a,b},{a,c},{b,c}} and S={{a},{b},{c}}. Then, we have PAttS1= while PAttS1={{a,b},{a,c},{b,c}}. Note that elements of PAttS1 has cardinality 2, because a conflict of size two can be expressed by an attack of degree 1. For instance, the conflict {a,b} can be expressed by the degree-1 attacks ({a},b) or ({b},a). Note also that conflict can be expressed by the degree 2 attacks ({a,b},b) or ({a,b},a), but we will only be interested in attacks (S,a) satisfying |S|=1. Similarly, for k2, we have PAttSk={{a,b,c}}, and PAttSk={{a,b},{a,c},{b,c},{a,b,c}}. The conflict {a,b,c} can be expressed by the degree 2 attacks ({a,b},c) or ({a,c},b) or ({b,c},a).

Definition 18.

Given an integer k1, an extension-set S2A is k-tight if for all SS and aArgsS it holds that if S{a}S then there exists a set SS, such that S{a}PAttSk.

Indeed, for k=1 the notion of k-tight corresponds to the notion of tight on Dung AFs (see Definition 9) while for kArgsS the notion of k-tight simplifies to: for all SS and aArgsS either S{a}S or there is no SS with S{a}S. Thus, S being -tight is implied by both S being incomparable or S being downward-closed.

4.1.Signatures for conflict-free and naive semantics

We start with presenting our results for the signatures for conflict-free and naive semantics. We already know that conflict-free extension-sets must be downward-closed. In k-SETAFs we additionally have that they must be k-tight which reflects that if S{a} is not conflict-free there must be an attack in the set of degree at most k. The following construction allows us to also realize such extension-sets.

Definition 19.

Let FScf,k=(ArgsS,RScf,k) be the k-SETAF with RScf,k={(S,a)|S|k,aArgsS,S{a}PAttSk}.

Note that, for given k1, FScf,k is a k-SETAF since we only have attacks (S,a) with |S|k. One can show that for each S that is downward-closed and k-tight we have that cf(FScf,k)=S.

Proposition 12.

Σcfk={SS is downward-closed and k-tight}.

Proof.

First we show the ⊆-relation, i.e. that cf(F) is downward-closed and k-tight for every k-SETAF F=(A,R). If Scf(F) then no subset of S can contain a conflict as then S would contain that conflict as well, i.e. all subsets are conflict-free as well and thus cf(F) is downward-closed. Now consider an argument a such that S{a}cf(F). Then S{a} attacks S{a}, that is either there is a set SS{a} with (S,a)R or there is a set ES{a} with aE and (E,b)R for some bS. In the former case S{a} is of size k+1 and S{a}dcl(cf(F)). In the latter case consider S=(E{a}){b} which is of size k (since (E,b)R) and S{a}=E{b}dcl(cf(F)). In both cases we have S{a}PAttcf(F)k and thus the condition for cf(F) being k-tight is satisfied.

For the ⊇-relation, let S be downward-closed and k-tight and consider FScf,k from Definition 19. We prove that cf(FScf,k)=S.

1) Let us show first that cf(FScf,k)S. Pick any SS and any attack (S,a)R with SS. By construction, we have that (S{a})dcl(S) and, thus, that (S{a})S. Hence, since SS, it follows that aS and that S is conflict-free. Hence, we have that cf(FScf,k)S.

2) To show cf(FScf,k)S, pick SArgsS with SS. As S is downward-closed we have that there is an SS such that SS, and w.l.o.g. assume that S is a maximal such set. Pick aSS. As S is k-tight there is an attack (B,a)R for some BS and thus Scf(FScf,k). □

Next we show that for each S that is incomparable and whose downward-closure is k-tight we have that naive(FScf,k)=S.

Proposition 13.

Σnaivek={SS is incomparable and dcl(S) is k-tight}.

Proof.

For any k-SETAF F, naive(F) is incomparable by definition and dcl(naive(F))=cf(F) holds. Thus, by Proposition 12, dcl(naive(F)) is k-tight.

To realize a set S that is incomparable and such that dcl(S) is k-tight consider S=dcl(S) and realize S by the construction of Proposition 12. Let F be the resulting SETAF. Then we have that cf(F)=S and by construction S contains exactly the ⊆-maximal elements of S. Hence, naive(F)=S. □

The following theorem summarizes the characterizations of this subsection.

Theorem 8.

We have that

  • Σcfk={SS is downward-closed and k-tight} and

  • Σnaivek={SS is incomparable and dcl(S) is k-tight}.

The following example shows that the expressiveness of conflict-free and naive semantics strictly increases with the degree k of the attacks.

Example 12.

Consider the argument set A={a1,a2,,ak+1,ak+2} and the extension-sets S={SA|S|k+1} and T={SA|S|=k+1}. We have that S is not k-tight, as AS, but for S={a1,a2,,ak+1} we have that every S{a1,a2,,ak+1} satisfies S{ak+2}S and thus S{ak+2}PAttSk. Note that S{ak+2}PAttSk because |S{ak+2}|>k+1. Hence, S cannot be realized as conflict-free sets of any k-SETAF. However, one can easily verify that S is (k+1)-tight and thus can be realized as conflict-free sets of some (k+1)-SETAF. Moreover, as dcl(T)=S we have that dcl(T) is not k-tight, i.e. T cannot be realized as naive sets of a k-SETAF. But dcl(T) is (k+1)-tight; hence T can be realized as naive sets of a (k+1)-SETAF.

4.2.Signatures for stable semantics

Next we consider the stable signature for k-SETAFs. Again, the set of stable extensions of a k-SETAF must be k-tight reflecting the fact that each argument which is not in an extension S must be attacked by S via a degree k attack. The following construction expands FScf,k from Definition 19 by arguments xs that eliminate unwanted naive extensions of FScf,k.

Definition 20.

Given an extension-set S that is incomparable and k-tight, we construct the k-SETAF FSstb,k=(A,R) based on FScf,k=(ArgsS,RScf,k) as follows:

A=ArgsS{xSSnaive(FScf,k)S}R=RScf,kSnaive(FScf,k)S{({a},xS),({xS},xS)aArgsSS}

One can show that for each S that is incomparable and k-tight we have that stb(FSstb,k)=S by building on Theorem 8 and using similar arguments as in [7, Prop. 7].

Theorem 9.

Σstbk={SS is incomparable and k-tight}.

Proof.

To prove the ⊆-relation, let F=(A,R) be a k-SETAF. We show that stb(F) is incomparable and k-tight. As stb(F)pref(F), it is clear that stb(F) is incomparable. Now consider Estb(F). By definition for each argument aE there is an attack (B,a) with |B|k. That is there is no Estb(F) with B{a}E and thus B{a}PAttstb(F)k. Hence, stb(F) is also k-tight.

To prove the ⊇-relation of the assertion, let S be an extension-set that is incomparable and k-tight, and consider the SETAF FSstb,k=(A,R) from Definition 20. We show that stb(FSstb,k)=S.

1) Let us show first that stb(FSstb,k)S. Pick any SS and any attack (S,a)R with SS. By construction, we have that (S{a})PAttSk and, thus, that (S{a})S. Now consider aArgsSS. As S is k-tight there exists BS,|B|k such that B{a}PAttSk and thus (B,a)R. Finally, consider xE{xSSS and S -maximal in dcl(S)}. We have that S and E are incomparable and thus there is an argument aE such that ({a},xE)R. That is, Sstb(FSstb,k).

2) It remains to show stb(FSstb,k)S. Let SArgsS with SS. If Snaive(FSstb,k) then it is not stable in FSstb,k. Thus assume Snaive(FSstb,k). Observe that naive(FSstb,k)=naive(FScf,k). By construction, there is an argument xSA with xSS and S not attacking xS. Thus, Sstb(FSstb,k). □

The above theorem gives a strict hierarchy of signatures Σstbk which is illustrated in the following example.

Example 13.

Consider the argument set A={a1,a2,,ak+1,ak+2} and the extension-set T={SA|S|=k+1} as in Example 12. Recall that T was not realizable by the naive semantics because dcl(T) was not k-tight. In fact, T itself is not k-tight either. Note that AT, but for {a1,a2,,ak+1}T we have that any S{a1,a2,,ak+1} satisfies S{ak+2}dcl(T) and thus S{ak+2}PAttTk. Hence, T cannot be realized as stable extensions of a k-SETAF. However, one can easily verify that T is (k+1)-tight and thus can be realized as stable extensions of a (k+1)-SETAF.

Note that, for incomparable S, whenever dcl(S) is k-tight, also S is k-tight. Hence, for k-SETAFs, the stable semantics is more expressible than the naive semantics. We next show that stable semantics is indeed strictly more expressive than naive semantics as long as k is bounded; recall that for SETAFs in general, stable and naive semantics are equally expressible modulo the empty set of extensions (cf. Main Theorem 1).

Example 14.

Consider the sets of arguments X={x1,,xk+1}, Y={y1,,yk+1} additional arguments a,b and the extension-set S={X{a}}{{b,yj}X{xj}1jk+1}. The set S is k-tight as {a,b},{a,yi},{yi,yj},{xi,yi}PAttSk. On the other hand, dcl(S) is not k-tight as for the set Xdcl(S) there is no XX such that |X|k and X{b}PAttSk. That is, the extension-set S can be realized with a k-SETAF under stable semantics but not with a k-SETAF under the naive semantics.

As we will see next, for k-SETAFs we also have different signatures for stable and preferred semantics. For the latter, we first need to understand admissible sets in k-SETAFs. This is also the reason why we analyse the semantics here in a slightly different order compared to Section 3.

4.3.Signatures of admissible and preferred semantics

We first parameterize the notions of conflict-sensitive and set-conflict-sensitive.

Definition 21.

Given an integer k1, a set S2A is called k-conflict-sensitive w.r.t. a set PAtt{(S,b)|S|k,S{b}PAttSk} if for each A,BS such that ABS, it holds that there is an argument bB satisfying (A,b)PAtt.

It turns out that the above generalization of set-conflict-sensitive is not sufficient to characterize admissible extension-sets in k-SETAFs. We thus introduce the notion of k-defensive, which is tautological for k=1 and covered by set-conflict-sensitivity for k=.

Definition 22.

A set S2A is called k-defensive w.r.t. a set PAtt{(S,b)|S|k,S{b}PAttSk} if for each AS,aA,(B,a)PAtt there are SA,bB with (S,b)PAtt.

Remark 2.

Notice that the terminology here has changed when compared to the conference version of the paper [11]. What was called k-defensive in [11] is now called k-adm-fortable and further split up in two properties, i.e., k-conflict-sensitivity and k-defensivity. This is due to the new characterization for complete semantics presented in the forthcoming subsection that shares the property of k-defensivity with admissible semantics but not k-conflict-sensitivity.

Definition 23.

A set S2A is called k-adm-fortable if there exists a set PAtt{(S,b)|S|k,S{b}PAttSk} such that S is k-conflict-sensitive w.r.t PAtt and k-defensive w.r.t. PAtt.

Remark 3.

Given an extension-set S, if there exists a set PAtt that meets the conditions of Definition 23 one such set can be computed by a fixed point iteration as follows. In an initial phase, for each SS consider all subsets B of size min(k,|S|) and bArgsSS and add (B,b) to PAtt whenever B{b}PAttSk. Then iteratively check whether the set is k-defensive and remove attacks that violate the k-defensive property from PAtt. When the fixed point is reached, i.e. S is k-defensive w.r.t. PAtt, check whether S is also k-conflict-sensitive w.r.t. PAtt. If so we have found a set PAtt that meets the conditions of Definition 23, otherwise there is no such set.

Whenever the union of two admissible sets is not admissible then (i) there must be an attack of degree k in this union and (ii) each admissible set must defend itself against all attacks we introduce to establish (i), again using only attacks of degree k.

Lemma 16.

For any k-SETAF F we have that adm(F) is k-adm-fortable and contains ∅.

Proof.

First, notice that the empty set is always admissible. Now we consider a k-SETAF F=(A,R), the set of attacks PAtt={(S,a)RSArgsadm(F),aArgsadm(F)} of all attacks between arguments that appear in at least one admissible set and show that it satisfies the two conditions for S being k-adm-fortable.

1) We first show that S is k-conflict-sensitive w.r.t. PAtt. Assume there are two admissible sets T, U such that the set C=TU is not admissible. By Lemma 2 the set C defends itself against all attackers and thus there must be a conflict in C, i.e. there exists an attack (S,a)R with SC and aC.

  • If aT then, as T is conflict-free, SU. Moreover, as T is admissible it has to defend itself against (S,a), i.e. there is an attack (T,u) with TT and uSU. Hence, we have (T,b)PAtt.

  • If aU then, as U is conflict-free, ST. Moreover, as U is admissible it has to defend itself against (S,a), i.e. there is an attack (U,t) with UU and tST. Now, as T is admissible as well, there is also an attack (T,u) with TT and uSU. Hence, we have (T,b)PAtt.

2) It remains to show that S is k-defensive w.r.t. PAtt. If (B,a)PAtt then B attacks a in F. Thus each set Eadm(F) with aE defends itself against B, i.e. for each Eadm(F) with aE there is a pair (S,b)R with SE and bB. Thus, also (S,b)PAtt and the second condition is satisfied. We obtain that adm(F) is k-defensive w.r.t. PAtt. □

Remark 4.

For k=1, we can make all the elements of PAtt symmetric, i.e. whenever ({a},b)PAtt then also ({b},a)PAtt, without affecting the 1-conflict-sensitive property. Any extensions S is trivially k-defensive w.r.t. symmetric attack sets PAtt and thus the notion of 1-adm-fortable reduces to being conflict-sensitive, cf. Definition 9. For unbounded k, each set (A,b)PAtt can be replaced by {(S,b)SS,AS} without violating k-conflict-sensitivity or k-defensivity w.r.t PAtt. Given that, testing whether S is k-conflict-sensitive w.r.t. PAtt reduced to testing whether S is set-conflict-sensitive. Moreover, whenever a set is set-conflict-sensitive it is also set-defensive w.r.t. PAtt={(S,a)SS,SAPAttS}. That is, an extension-set S being -adm-fortable reduces to S being set-conflict-sensitive.

Similarly as done in Section 3 for SETAFs of unbounded attack degree, we build the k-SETAF for the admissible semantics with several modules, starting with the module that exploits conflict-freeness.

Definition 24.

When given a extension-set S and a set PAtt{(S,b)|S|k,S{b}PAttSk} we define the k-SETAF FS,PAttcf,k=(ArgsS,PAtt).

We are now able to obtain similar results for this module as for the corresponding module in general SETAFs.

Lemma 17.

Let S be a extension-set that contains ∅ and is k-conflict-sensitive w.r.t. a set PAtt that meets the conditions of Definition 23, and let SArgsS be some set of arguments such that S=T for some set TS. Then, we have that Scf(FS,PAttcf,k) implies SS.

Proof.

Consider a SETAF FS,PAttcf,k as given in Definition 24 and a set S=T for some subset TS with Scf(FS,PAttcf,k). Let us consider AT such that AS and there is no AT such that AA and AS. Note that such A always exists because =S. We also define A=A. Towards a contradiction assume AT and pick any BTA. Then, by construction, we have that A,BS, (AB)S and that (AB)S. Furthermore, since S is k-conflict-sensitive, it follows that there are AA and bB such that |A|k and (A,b)PAtt. This implies that there is an attack (A,b)PAtt and, thus, (A{b})cf(FS,PAttcf,k). Finally, since (A{b})(AB)S and cf(FS,PAttcf,k) is downward-closed, this implies Scf(FS,PAttcf,k) which is a contradiction with the assumption that Scf(FS,PAttcf,k). Hence, it must be that A=T and, thus, that A=S holds. Since AS holds by construction, this implies SS. □

Lemma 18.

Let S be a extension-set with S that is k-defensive w.r.t. PAtt. Then, Sadm(FS,PAttcf,k).

Proof.

Pick any set SS. First of all by the choice of the attacks PAtt the set S is conflict-free. Now consider any argument aS and any attack (B,a)PAtt As S is k-defensive w.r.t. PAtt there are some SS, bB such that (S,b)PAtt. That is, in FS,PAttcf,k the set S defends a against the attack (S,a). Hence, S defends itself against all attacks in FS,PAttcf,k. □

Towards our defense module we recall the notion of defense-formulas from [7].

Definition 25

Definition 25([7]).

Given an extension-set S, the defense-formula DaS of an argument aArgsS in S is defined as

SS s.t. aSsS{a}s
DaS given as (a logically equivalent) CNF is called CNF-defense-formula CDaS of a in S.

The defense formula DaS tells us which arguments must be in the extension in order to defend the argument a. We can exploit this by using the following technical lemma.

Lemma 19

Lemma 19([7]).

Given an extension-set S and an argument aArgsS, then for each SArgsS with aS: (S{a}) is a model of DaS (resp. CDaS) iff there exists an SS with aS such that SS.

For our defense module we adjust the corresponding parts from the canonical defense-argumentation-framework in [7] to our setting with k-SETAFs.

Definition 26.

Given an extension-set S, we call FSdef=(ASdef,RSdef) with

ASdef=ArgsSaArgsS{αaγγCDaS}RSdef=aArgsS{({b},αaγ),({αaγ},αaγ),({αaγ},a)γCDaS,bγ}
the defense-argumentation-framework of S, and let FS,PAttadm,k=FS,PAttcf,kFSdef.

We next show that this defense framework ensures that only sets in S or the union of such sets are admissible.

Lemma 20.

For every extension-set S that contains ∅, we have that Sadm(FSdef) iff S=T for some TS.

Proof.

First notice that there are no conflicts between arguments in ArgsS and all arguments not in ArgsS are self-attacking. It thus suffices to show that S defends itself in FSdef iff S=T for some TS.

⇒: Let Sadm(FSdef) and consider an argument aS. S attacks all the arguments αaγ that attack a and by construction this implies that S contains a model M of CDaS. By Lemma 19 we have M{a}S. As this holds for each argument aS there is a TS such that S=T.

⇐: Let TS and S=T. Consider aS and a set TT with aT. By Lemma 19 we have that T{a} is a model of CDaS and thus attacks all of the arguments αaγ. That is a is defended by S. Hence, Sadm(FSdef). □

When combining the two modules to the SETAF FS,PAttadm,k, Lemmas 17, 18 and Lemma 20 imply that we get a SETAF that realizes extension-set S with admissible semantics.

Lemma 21.

For every extension-set S with {}S and set PAtt{(S,b)|S|k,S{b}PAttSk} such that S is k-conflict-sensitive and k-defensive w.r.t. PAtt we have adm(FS,PAttadm,k)=S.

Proof.

We consider the k-SETAF FS,PAttadm,k=FS,PAttcf,kFSdef from Definition 26 and show that S=adm(FS,PAttadm,k).

  • Sadm(FS,PAttadm,k): We have that, by Lemma 18, Sadm(FS,PAttcf,k), and, by Lemma 20, Sadm(FSdef). Hence, by Proposition 9(2), Sadm(FS,PAttadm).

  • Sadm(FS,PAttadm): Consider Sadm(FS,PAttadm) which by definition is conflict-free in FS,PAttadm. Notice that, attacks from FS,PAttcf cannot be used to defend against attacks from FSdef and vice versa. Thus, by Proposition 9(1) and the above observation, Sadm(FS,PAttcf) and Sadm(FSdef).

    By Lemma 20 we have that S=T for some TS. Now by Lemma 17 we have that if Scf(FS,PAttcf,k) then SS. As we already know that Sadm(FS,PAttcf,k)S we obtain SS.

 □

We now can state the exact characterization of the admissible signature for k-SETAFs.

Proposition 14.

Σadmk={SS is k-adm-fortable and contains }.

Proof.

First, by Lemma 16 we have that any SΣadmk is k-adm-fortable and contains . Second, given that an extension-set S is k-adm-fortable and contains , we know that there exists a set PAtt{(S,b)|S|k,S{b}PAttSk} such that S is k-conflict-sensitive and k-defensive w.r.t. PAtt. Thus, by Lemma 21, we have adm(FS,PAttadm,k)=S and thus SΣadmk. □

Based on our characterization of admissible semantics we can now also characterize the signature of preferred semantics.

Proposition 15.

Σprefk={SS is incomparable and k-adm-fortable}.

Proof.

We start with the ⊆-relation. Consider pref(F) for an arbitrary k-SETAF F=(A,R). The extension-set pref(F) is incomparable by the definition of preferred semantics.

Now we consider the set PAtt={(S,a)RSArgsadm(F)} and show that S is both (1) k-conflict-sensitive w.r.t. PAtt and (2) k-defensive w.r.t. PAtt, i.e. we show that S is k-adm-fortable.

1) Consider arbitrary extensions E,Tpref(F) with ET. By the maximality of E and T we have that ETpref(F), ET is not contained in any preferred extension, and, by Lemma 2, we know that ET defends itself against all attackers. That is, there is a conflict (B,a)R such that BET and aET.

  • If aE then, as E is conflict-free, BT. Moreover, as E is admissible it has to defend itself against (B,a), i.e. there is an attack (S,b) with SE and bBT. Hence, we have (S,b)PAtt.

  • If aT then, as T is conflict-free, BE. Moreover, as T is admissible it has to defend itself against (B,a), i.e. there is an attack (S,c) with ST and cBE. Now, as E is admissible as well, there is also an attack (S,b) with SE and bST. Hence, we have (S,b)PAtt.

2) If (S,b)PAtt then S attacks b in F. Thus each set Spref(F) with bS defends itself against S, i.e. for each Spref(F) with bS there is a pair (S,a)R with SS and aS. Thus, also (S,a)PAtt thus pref(F) is k-defensive

We obtain that pref(F) is k-adm-fortable.

To prove the ⊇-relation, consider an extension-set S that is incomparable and k-adm-fortable. The set S=S{} is k-adm-fortable and contains the empty set. We thus can apply Proposition 14 and obtain that there is a k-SETAF F such that adm(F)=S. As the preferred extensions are the ⊆-maximal admissible sets we have pref(F)=S as desired. □

The results of this subsection are summarized by the following theorem.

Theorem 10.

We have that

  • Σadmk={SS is k-adm-fortable and contains } and

  • Σprefk={SS is k-adm-fortable and incomparable}.

Example 15.

Reconsider the argument set A={a1,a2,,ak+1,ak+2} and the extension-set T={SA|S|=k+1} from Example 13 as well as U=T{}. We next argue that the extension-sets are not k-adm-fortable. Notice that PAttTk=PAttUk= thus the empty set is the only candidate for the set PAtt. However, S has to be k-conflict sensitive w.r.t. PAtt. That is, for the sets