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

Article type: Research Article

Authors: Dvořák, Wolfganga; * | Fandinno, Jorgeb | Woltran, Stefana

Affiliations: [a] Institute of Logic and Computation, TU Wien, Austria. E-mails: [email protected], [email protected] | [b] IRIT, Université de Toulouse, CNRS, Toulouse, France. E-mail: [email protected]

Correspondence: [*] Corresponding author. E-mail: [email protected].

Keywords: Abstract argumentation, SETAF, collective attacks, expressiveness

DOI: 10.3233/AAC-190457

Journal: Argument & Computation, vol. 10, no. 2, pp. 191-230, 2019

Published: 2 September 2019
Get PDF open access

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) [18–20]. 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,S′∈S, S⊆S′ 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 (k⩾1) 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 k⩾2 (Σσ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 A⊆A is finite, and R⊆(2A∖{∅})×A is the attack relation. For an integer k⩾1, 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 S↦Rb if there is a set S′⊆S with (S′,b)∈R. Moreover, we write S′↦RS if S′↦Rb for some b∈S.11 We drop subscript R in ↦R if there is no ambiguity. For S⊆A, we use SR+ to denote the set {b∣S↦Rb} of argument attacked by S (in R), and define the range of S (w.r.t. R), denoted SR⊕, as the set S∪SR+.

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 S⊆A is conflicting in F if S↦Ra for some a∈S. A set S⊆A 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 a∈A is defended (in F) by a set S⊆A if for each B⊆A, such that B↦Ra, also S↦RB. A set T of arguments is defended (in F) by S if each a∈T is defended by S (in F).

The notion of defense can be equivalently characterized as follows: an argument a∈A is defended by a set S⊆A if for each (B,a)∈R we have S↦RB.

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). S∈cf(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 S∈cf(F), we say that

  • S∈naive(F), if there is no T∈cf(F) with T⊃S,

  • S∈stb(F), if S↦a for all a∈A∖S,

  • S∈pref(F), if S∈adm(F) and there is no T∈adm(F) s.t. T⊃S,

  • S∈com(F), if S∈adm(F) and a∈S for all a∈A defended by S,

  • S∈grd(F), if S=⋂T∈com(F)T,

  • S∈stage(F), if ∄T∈cf(F) with TR⊕⊃SR⊕, and

  • S∈sem(F), if S∈adm(F) and ∄T∈adm(F) s.t. TR⊕⊃SR⊕.

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 B⊂A, and arguments a,b∈A 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,T⊆A. If both S and T defend itself in F, then S∪T defends itself in F.

Proof.

Towards a contradiction assume that S∪T does not defend itself, i.e. there exists a set B⊆A with B↦(S∪T) such that (S∪T)̸↦B. Consider B↦S. Since (S∪T)̸↦B also S̸↦B and thus S does not defend itself in F which is a contradiction to the assumption. The case where B↦T 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 ER⊕⊂DR⊕. Hence E∈sem(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 E∈stb(F) we have that ER⊕=A and thus there cannot be another conflict-free set D of F with ER⊕⊂DR⊕. Hence E∈stage(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 E⊂D. Let x∈D such that x∉E and E̸↦Rx (otherwise there would be a conflict in D). As the range operator ⊕ is monotone by definition, we have ER⊕⊆DR⊕ and as x∉ER⊕ we obtain that ER⊕⊂DR⊕. Hence, E∉sem(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 E⊂D. Let x∈D such that x∉E and E̸↦Rx. As the range operator ⊕ is monotone by definition we have ER⊕⊆DR⊕ and as x∉ER⊕ we obtain that ER⊕⊂DR⊕. Hence, E∉stage(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 k⩾1 be an integer. The signature Σσk of a semantics σ for k-SETAFs is defined as

Σσk={σ(F)∣F∈AFAk}.
For unrestricted SETAFs we use Σσ∞={σ(F)∣F∈AFA}. 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 S⊆2A,

  • we use ArgsS to denote ⋃S∈SS, 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 S⊆2A and E⊆ArgsS, we define

  • (a) the downward-closure of S as dcl(S)={S′⊆S∣S∈S};

  • (b) the set of potential conflicts in S as PAttS={S⊆ArgsS∣S∉dcl(S)};

  • (c) the completion-sets of E in S as CS(E)={S∈S∣E⊆S,∄S′∈S,E⊆S′⊂S}.

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 S∈S. 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 S∈S that contain E. In particular, if E∈S 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 S⊆2A. We call S

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

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

  • tight if for all S∈S and a∈ArgsS it holds that if S∪{a}∉S then there exists an s∈S such that {a,s}∈PAttS;

  • conflict-sensitive if for each A,B∈S such that A∪B∉S it holds that ∃a,b∈A∪B:{a,b}∈PAttS;

  • com-closed if for each T⊆S: if {a,b}∉PAttS for each a,b∈ArgsT, 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 a∈S and {a,c}∈PAttS′; for T={b,c} and argument a, we have c∈T and again {a,c}∈PAttS′. Likewise, it can be checked that S′ is conflict-sensitive since a∈S, c∈T 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={S≠∅∣S is downward-closed and tight}Σnaive1={S≠∅∣S is incomparable and dcl(S) is tight}Σstb1={S∣S is incomparable and tight}Σstage1={S≠∅∣S is incomparable and tight}Σadm1={S≠∅∣S is conflict-sensitive and contains ∅}Σpref1={S≠∅∣S is incomparable and conflict-sensitive}Σsem={S≠∅∣S is incomparable and conflict-sensitive}Σgrd1={S∣|S|=1}Σcom1⊆{S≠∅∣S is com-closed and ⋂S∈S}

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}∣S⊂A,|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 k⩾1.

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)∣S∈S,a∈ArgsS∖S}.

We first prove the desired result for stable semantics.

Proposition 2.

Σstb∞={S∣S 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 S∈S. For each a∈ArgsS∖S, we have (S,a)∈RSstb by construction. Moreover, as S is incomparable, we cannot have (S′,a)∈RSstb with S′⊂S and a∈S. Hence, S is conflict-free in FSstb and thus S∈stb(FSstb).

stb(FSstb)⊆S: Consider S⊆ArgsS, such that S∉S. First, if there is an E∈S such that E⊂S then for each argument a∈S∖E we have (E,a)∈RSstb and thus S attacks itself in FSstb. Hence, such an S is not stable. Alternatively, if there is no E∈S such that E⊆S then (a) S does not attack any argument and (b) there is an argument a∈E 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∞={S≠∅∣S 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 S∈S. As shown in the proof of Proposition 2, S∈stb(FSstb). By Relation (1), S∈pref(FSstb) follows.

pref(FSstb)⊆S: Consider S⊆ArgsS, such that S∉S. First, if there is an E∈S such that E⊂S, then there is an argument a∈S∖E such that (E,a)∈RSstb and thus S attacks itself in FSstb. Hence, S∉pref(FSstb). Thus let us consider the case where there is no E∈S such that E⊆S. Then S does not attack any argument. Notice that by construction all arguments, except those arguments contained in all sets S∈S (we call them skeptically accepted arguments), are attacked by at least one set S∈S. 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, S∉pref(FSstb). □

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

Theorem 3.

We have Σstb∞={S∣S 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 S⊆A then it holds for each model S′⊂S 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.22

Definition 11.

Given a non-empty extension-set S, let FScf=(ArgsS,RScf) be the SETAF with RScf={(S,a)∣S∈S,a∈ArgsS,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 S∈dcl(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 S∉dcl(S), i.e., S∈PAttS, a subset maximal set S′∈{E∈S∣E⊂S}, and some argument a∈S∖S′. Then, by construction (S′,a)∈R and, thus, S is not conflict-free in FScf. □

Proposition 4.

Σcf∞={S≠∅∣S 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∞={S≠∅∣S 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∞={S≠∅∣S is downward-closed} and

  • Σnaive∞={S≠∅∣S 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 FS′cf as specified in Definition 11, and we have cf(FS′cf)=S′. Also note that for S={{a,b},{b,c},{a,c}}, we have dcl(S)=S′ and naive(FS′cf)=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∞={S≠∅∣S 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∞={S≠∅∣S 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∞={S≠∅∣S 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 A∪B does not appear in S allow for a binary conflict, we now only require that they allow for conflicts (A,b), (B,a) with a∈A,b∈B.

Definition 12.

A set S⊆2A is called set-conflict-sensitive if for each T,U∈S such that T∪U∉S it holds that ∃u∈U: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=T∪U 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 S⊆C and a∈C.

  • If a∈T then, as T is conflict-free in F, B∩U≠∅. 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 T′⊆T and u∈B∩U. Hence, we have T′∪{u}∈PAttadm(F) and thus T∪{u}∈PAttadm(F).

  • If a∈U then, as U is conflict-free in F, B∩T≠∅. 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 U′⊆U and t∈B∩T. Now, as T is admissible in F as well, there is also an attack (T′,u)∈R with T′⊆T and u∈U′⊆U. 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 S⊆2A is said to be union-closed if ∅∈S and each pair A,B∈S satisfies A∪B∈S. Let us denote by ucl(S) the ⊆-minimal union-closed extension-set such that S⊆ucl(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 ∅∈S′∩S″ and that S′∩S″⊇S. Hence, it only remains to be shown that S′∩S″⊆S also holds. Suppose for the sake of contradiction that there is some set C∈(S′∩S″)∖S. Since C∈S″∖S, by construction, C must be of the form C=⋃T for some T⊆S. W.l.o.g. we can assume that |T|=2, i.e., C=S∪T with S,T∈S. Moreover, since S is set-conflict-sensitive, C∉S implies that there is some b∈T such that S∪{b}∈PAttS. Furthermore, since C∈S′, there is also some S′∈S such that C⊆S′ and, thus, we have S∪{b}⊆S∪T⊆S′ which is a contradiction. Hence, it must be that S′∩S″⊆S and S′∩S″=S hold. □

Proposition 9.

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

  • (1) S is conflict-free in F1∪F2=(A1∪A2,R1∪R2) 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 F1∪F2=(A1∪A2,R1∪R2).

Proof.

(1) Consider some S∉cf(F1∪F2), i.e., there is an attack (A,b)∈(R1∪R2) with A∪{b}⊆S. Hence, (A,b)∈Ri for some i∈{1,2} and thus S∉cf(Fi). For the reverse direction consider some S∉cf(Fi) for some i∈{1,2}, i.e., there is an attack (A,b)∈(Ri) with A∪{b}⊆S. Then (A,b)∈R1∪R2 and thus S∉cf(F1∪F2).

(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 F1∪F2. Let us show us that S also defends itself in F1∪F2. Pick any b∈S and (A,b)∈(R1∪R2). 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 C⊆S and a∈A such that (C,a)∈Ri. That is, for every argument b∈S and attack (A,b)∈(R1∪R2), there is some C⊆S and a∈A such that (C,a)∈(R1∪R2). Hence, S is admissible in F1∪F2. □

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 S⊆ArgsS be some set of arguments such that S=⋃T for some subset T⊆S. Then, we have that S∈cf(FScf) implies S∈S.

Proof.

Consider such a set S=⋃T with S∈cf(FScf) and pick A⊆T such that ⋃A∈S and there is no A′⊆T such that A⊂A′ and ⋃A′∈S. Note that such A always exists because ⋃∅=∅∈S. We also define A=⋃A. Towards a contradiction assume that A⊂T and pick any B∈T∖A. Then, by construction, we have that A,B∈S and that (A∪B)∉S. Furthermore, since S is set-conflict-sensitive, it follows that there is b∈B 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})⊆(A∪B)⊆S and cf(FScf) is downward-closed, this implies S∉cf(FScf) which is a contradiction with the assumption that S∈cf(FScf). Hence, it must be that A=T and, thus, that A=S holds. Since A∈S by construction, this implies S∈S. □

Lemma 11.

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

Proof.

Pick any set S∈S, any argument a∈S and any attack (S′,a)∈RScf. Then, (S∪S′)∉S and, since S,S′∈S and S is conflict-sensitive, it follows that there is some b∈S′ 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 S∈S 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 S∈S that contain a.

Definition 14.

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

ASucl=ArgsS∪{xa∣a∈ArgsS}andRSucl={({xa},a)∣a∈ArgsS}∪{({xa},xa)∣a∈ArgsS}∪{(S,xa)∣S∈S and a∈S}.
We then define FSadm=(ASadm,RSadm)=(FScf∪FSucl).

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 S∈S 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 S⊆adm(Fucl). Pick any A∈S, a∈A and (S,a)∈RSucl. Then, by construction, we have that S={xa} and, since a∈A, that (A,xa)∈RSucl, so A also defends itself against all attacks in RSucl. Hence, we have that S⊆adm(FSucl). Pick now A,B∈S. We already know that A,B∈adm(FSucl) and, moreover, A∪B defends itself in FSucl (Lemma 2). Furthermore, by construction, there are no attacks between elements of A∪B and thus A∪B∈adm(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 S⊆adm(FScf)∩adm(FSucl). Furthermore, from Proposition 9, this implies that S⊆adm(FSadm).

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

Now we can give an exact characterization of Σadm∞.

Theorem 6.

Σadm∞={S≠∅∣S 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 A∪B∉S′ 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 E⊆ArgsS in S are the ⊆-minimal sets S∈S with E⊆S. 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 S⊆2A is called set-com-closed iff, for each T,U⊆S with T=ArgsT, U=ArgsU,

  • (1) |CS(T∪U)|⩽1, and

  • (2) if T,U∈dcl(S) and |CS(T∪U)|=0, then there is an argument u∈U 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,U⊆com(F) and sets T=⋃T, U=⋃U such that T,U∈dcl(com(F)). From T,U∈dcl(com(F)), it follows that T,U∈cf(F) and from T=⋃T, U=⋃U with T,U⊆com(F) it follows that T and U defend themselves. Hence, we get T,U∈adm(F). If in addition we have T∪U∈cf(F), then by Lemma 2 we have that T∪U∈adm(F) and thus by Lemma 1 there is a unique ⊆-minimal complete extension E∈com(F) with T∪U⊆E, i.e. |Ccom(F)(T∪U)|=1. If T∪U∉cf(F) then there exists an attack (S,a)∈R with S⊆T∪U and a∈T∪U.

  • If a∈T, as T is admissible, there is an attack (T′,u) with T′⊆T and u∈S∖T⊆U. Thus, T∪{u}∈PAttcom(F).

  • If a∈U, as U is admissible, there is an attack (U′,s) with U′⊆U and s∈S∖U⊆T. Now, as T is admissible, there is an attack (T′,u) with T′⊆T and u∈U′⊆U. Thus T∪{u}∈PAttcom(F).

In both cases we have an u∈U 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)={S∖⋂S∣S∈S}, we denote a reduced extension-set whose corresponding ground extension is empty. Let S′=reduced(S). We then realize S∗=dcl(S′)∩ucl(S′)={⋃T∣T⊆S′,⋃T∈dcl(S′)} and add further attacks such that each set E∈S∗ 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=(ArgsS∪AS∗adm,RScom) we denote a SETAF with RScom=RS∗adm∪R′ and where R′={(A∪B,xa)∣A,B∈S′∖{∅},a∈CS′(A∪B)}.

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 AS∗adm={a,b,c,xa,xb,xc} and attacks RS∗adm={({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(AS∗adm,RS∗adm)=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(AS∗adm,RS∗adm∪R′)=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 S′⊂S, 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 ⋂S∈S, 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(FS′com)=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,U∈S∗ such that T∪U∉S∗. Then, by construction of S∗, we have that T∪U∉dcl(S′) and thus Ccom(F)(T∪U)=∅. Now as S′ is set-com-closed there is an argument u∈U such that T∪{u}∈PAttS. That is, for T,U∈S∗ such that T∪U∉S∗ there is an argument u∈U such that T∪{u}∈PAttS. Hence, the extension-set S∗ is set-conflict-sensitive and, from Lemma 13, it follows that adm(FS∗adm)=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 FS∗adm is admissible in FS′com as well (Proposition 9, condition (2)). That is, we have adm(FS∗adm)⊆adm(FS′com). Let us show S′⊆com(FS′com). Consider S∈S′⊆S∗. By the above, we have that S∈adm(FS∗adm) and it remains to be shown that S does not defend any a∈ArgsS∖S, i.e., does not attack any xa for a∈ArgsS∖S. By construction of FS′com the set S only attacks arguments xa with a∈S and thus S∈com(FS′com) follows. The other way around, let us show S′⊇com(FS′com). Consider S∈adm(FS′com). We next show that if S∉S′ then S∉com(FS′com). To this end we consider two cases.

  • S∈adm(FS′com)∖S∗: Notice that S∗=adm(FS∗adm). Consider a set S that is admissible in FS′com but not in FS∗adm. This can only be because of the attacks introduced with R′. That is, there is some xs with s∈S that prevents that S is admissible in FS∗adm and an attack (A∪B,xs)∈R′ with which S defends itself against xs in FS′com. That is A,B⊆S and, by the definition of R′, we have that there is a unique completion C=CS′(A∪B) and s∈C (recall that in R′ we only draw attacks for A∪B with a unique completion). As C∈S′⊆S∗ and s∈C, by construction, there is an attack (C,xs) in FS∗adm That is, if C⊆S then S attacks xs in FS∗adm, a contradiction to our initial assumption. Hence we have C⊈S. Now we can argue that in FS′com, S defends all arguments in C and thus S is not complete. To this end let c∈C∖S. By construction A∪B (and thus S) attacks all xa with a∈C. Now consider a set D∈S∗ that attacks c. As C is admissible in FS∗adm, we have that there is a d∈D such that (C,d)∈RS∗adm. By construction we have C∪{d}∈PAtt(S∗) and thus also A∪B∪{d}∈PAtt(S∗). As A∪B∈S∗, we then by construction have (A∪B,d)∈RS∗adm. That is A∪B defends c against both possible kinds of attackers and thus defends c.

  • S∈S∗∖S′: Then, there is a set T⊆S′ such that ⋃T=S and S∈dcl(S′). As S′ is set-com-closed for each A,B∈S′ with A,B⊆S, we have a unique completion set CS′(A∪B) (as A∪B∈dcl(S′) we cannot have a conflict in A∪B. Towards a contradiction assume that for all A,B∈S′ such that A,B⊆S we have CS′(A∪B)⊆S. Then we can iteratively replace A,B∈T by CS′(A∪B) and we end up with a single set in T. But then S∈S′, a contradiction. Thus there are two sets A,B∈S′ such that A,B⊆S and A∪B∉S′, and there is also a unique set C∈CS′(A∪B) with C⊈S. Let c∈C∖S, we next argue the S defends c and thus is not complete. By construction A∪B (and thus S) attacks all xa with a∈C. Now consider a set D∈S∗ that attacks c. As C is admissible in FS∗adm we have that there is a d∈D such that (C,d)∈RS∗adm. By construction we have C∪{d}∈PAtt(S∗) and thus also A∪B∪{d}∈PAtt(S∗). As A∪B∈S∗, by construction we have (A∪B,d)∈RS∗adm. That is A∪B defends c against both possible kinds of attackers and thus defends c.

Combining both cases we obtain that if S∉S′ then S∉com(FS′com). Finally, just note that FScom just adds to FS′com the arguments in ⋂S as unattacked. Hence, S∈com(FScom) iff (S∖⋂S)∈com(FS′com) and, thus, com(FScom)=S. □

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

Theorem 7.

Σcom∞={S≠∅∣S is set-com-closed and ⋂S∈S}.

Notice that when considering AFs not all extension-sets that are com-closed and satisfy ⋂S∈S 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 T∪U of sets with T=ArgsT and U=ArgsU with T,U⊆S. The first condition of S being set-com-closed is verified as follows.

  • (1) Whenever T∪U∈S we have |CS(T∪U)|=1 by the definition of CS.

  • (2) Whenever T∪U∉dclS then |CS(T∪U)|=0 by the definition of CS.

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

For the second condition we are interested in the choices of T,U where T,U∈dcl(S), i.e. we have T,U∈S∪{{a,b},{a,c},{b,c}}. We have to show that whenever T∪U∉dcl(S) then T∪{u}∈PAttS for some u∈U.

  • 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 3–7) are summarized in the following theorem.

Main Theorem 1.

Characterizations of the signatures for general SETAFs are as follows:

Σcf∞={S≠∅∣S is downward-closed}Σnaive∞={S≠∅∣S is incomparable}Σstb∞={S∣S is incomparable}Σadm∞={S≠∅∣S is set-conflict-sensitive and contains ∅}Σpref∞={S≠∅∣S is incomparable}Σcom∞={S≠∅∣S is set-com-closed and ⋂S∈S}Σsem∞={S≠∅∣S is incomparable}Σstage∞={S≠∅∣S 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,U⊆S, 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(T∪U)|⩾2. Then we have that T∪U∈dcl(S) and thus, as S is set-conflict-sensitive, T∪U∈S. The latter implies that CS(T∪U)={T∪U} which is in contradiction to |CS(T∪U)|⩾2. Let us now assume that condition (2) is violated, i.e. T,U∈dcl(S), |CS(T∪U)|=0, and there is no argument u∈U such that T∪{u}∈PAttS. As T,U∈dcl(S) and S is set-conflict-sensitive, we have that T,U∈S. Moreover, as |CS(T∪U)|=0 we have T∪U∉S, and thus, as S is set-conflict-sensitive, there is a b∈U: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 T∪U∉dcl(S′) and thus |CS(T∪U)|=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,B∈S such that A∪B∉S and there is no b∈B such that A∪{b}∈PAttS. As S is downward-closed there is no C∈S with A∪B⊆C and thus |CS({a,b})|=0. Now as S is set-com-closed there is an argument b∈B 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={S⊆ArgsS∣|S|⩽k+1 and S∉dcl(S)}.

Example 11.

Let S={{a,b},{a,c},{b,c}} and S′={{a},{b},{c}}. Then, we have PAttS1=∅ while PAttS′1={{a,b},{a,c},{b,c}}. Note that elements of PAttS′1 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 k⩾2, we have PAttSk={{a,b,c}}, and PAttS′k={{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 k⩾1, an extension-set S⊆2A is k-tight if for all S∈S and a∈ArgsS it holds that if S∪{a}∉S then there exists a set S′⊆S, 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 k⩾ArgsS the notion of k-tight simplifies to: for all S∈S and a∈ArgsS either S∪{a}∈S or there is no S′∈S 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,a∈ArgsS,S∪{a}∈PAttSk}.

Note that, for given k⩾1, 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={S≠∅∣S 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 S∈cf(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 S′⊆S∪{a} with (S′,a)∈R or there is a set E⊆S∪{a} with a∈E and (E,b)∈R for some b∈S. 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 S∈S and any attack (S′,a)∈R with S′⊆S. By construction, we have that (S′∪{a})∉dcl(S) and, thus, that (S′∪{a})⊈S. Hence, since S′⊆S, it follows that a∉S and that S is conflict-free. Hence, we have that cf(FScf,k)⊇S.

2) To show cf(FScf,k)⊆S, pick S⊆ArgsS with S∉S. As S is downward-closed we have that there is an S′∈S such that S′⊆S, and w.l.o.g. assume that S′ is a maximal such set. Pick a∈S∖S′. As S is k-tight there is an attack (B,a)∈R for some B⊆S′ and thus S∉cf(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={S≠∅∣S 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={S≠∅∣S is downward-closed and k-tight} and

  • Σnaivek={S≠∅∣S 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={S⊆A∣|S|⩽k+1} and T={S⊆A∣|S|=k+1}. We have that S is not k-tight, as A∉S, 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∪{xS∣S∈naive(FScf,k)∖S}R=RScf,k∪⋃S∈naive(FScf,k)∖S{({a},xS),({xS},xS)∣a∈ArgsS∖S}

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={S∣S 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 E∈stb(F). By definition for each argument a∉E there is an attack (B,a) with |B|⩽k. That is there is no E′∈stb(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 S∈S and any attack (S′,a)∈R with S′⊆S. By construction, we have that (S′∪{a})∈PAttSk and, thus, that (S′∪{a})⊈S. Now consider a∈ArgsS∖S. As S is k-tight there exists B⊆S,|B|⩽k such that B∪{a}∈PAttSk and thus (B,a)∈R. Finally, consider xE∈{xS∣S∉S and S ⊆-maximal in dcl(S)}. We have that S and E are incomparable and thus there is an argument a∈E such that ({a},xE)∈R. That is, S∈stb(FSstb,k).

2) It remains to show stb(FSstb,k)⊆S. Let S⊆ArgsS with S∉S. If S∉naive(FSstb,k) then it is not stable in FSstb,k. Thus assume S∈naive(FSstb,k). Observe that naive(FSstb,k)=naive(FScf,k). By construction, there is an argument xS∈A with xS∉S and S not attacking xS. Thus, S∉stb(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={S⊆A∣|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 A∉T, 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}∣1⩽j⩽k+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 X∈dcl(S) there is no X′⊆X 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 k⩾1, a set S⊆2A is called k-conflict-sensitive w.r.t. a set PAtt⊆{(S,b)∣|S|⩽k,S∪{b}∈PAttSk} if for each A,B∈S such that A∪B∉S, it holds that there is an argument b∈B 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 S⊆2A is called k-defensive w.r.t. a set PAtt⊆{(S,b)∣|S|⩽k,S∪{b}∈PAttSk} if for each A∈S,a∈A,(B,a)∈PAtt there are S⊆A,b∈B 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 S⊆2A 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 S∈S consider all subsets B of size min(k,|S|) and b∈ArgsS∖S 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)∈R∣S⊆Argsadm(F),a∈Argsadm(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=T∪U 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 S⊆C and a∈C.

  • If a∈T then, as T is conflict-free, S∩U≠∅. Moreover, as T is admissible it has to defend itself against (S,a), i.e. there is an attack (T′,u) with T′⊆T and u∈S∩U. Hence, we have (T′,b)∈PAtt.

  • If a∈U then, as U is conflict-free, S∩T≠∅. Moreover, as U is admissible it has to defend itself against (S,a), i.e. there is an attack (U′,t) with U′⊆U and t∈S∩T. Now, as T is admissible as well, there is also an attack (T′,u) with T′⊆T and u∈S′⊆U. 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 E∈adm(F) with a∈E defends itself against B, i.e. for each E∈adm(F) with a∈E there is a pair (S,b)∈R with S⊆E and b∈B. 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)∣S∈S,A⊂S} 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)∣S∈S,S∪A∈PAttS}. 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 S⊆ArgsS be some set of arguments such that S=⋃T for some set T⊆S. Then, we have that S∈cf(FS,PAttcf,k) implies S∈S.

Proof.

Consider a SETAF FS,PAttcf,k as given in Definition 24 and a set S=⋃T for some subset T⊆S with S∈cf(FS,PAttcf,k). Let us consider A⊆T such that ⋃A∈S and there is no A′⊆T such that A⊂A′ and ⋃A′∈S. Note that such A always exists because ⋃∅=∅∈S. We also define A=⋃A. Towards a contradiction assume A⊂T and pick any B∈T∖A. Then, by construction, we have that A,B∈S, (A∪B)⊆S and that (A∪B)∉S. Furthermore, since S is k-conflict-sensitive, it follows that there are A′⊆A and b∈B 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})⊆(A∪B)⊆S and cf(FS,PAttcf,k) is downward-closed, this implies S∉cf(FS,PAttcf,k) which is a contradiction with the assumption that S∈cf(FS,PAttcf,k). Hence, it must be that A=T and, thus, that A=S holds. Since A∈S holds by construction, this implies S∈S. □

Lemma 18.

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

Proof.

Pick any set S∈S. First of all by the choice of the attacks PAtt the set S is conflict-free. Now consider any argument a∈S and any attack (B,a)∈PAtt As S is k-defensive w.r.t. PAtt there are some S′⊆S, b∈B 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 a∈ArgsS in S is defined as

⋁S∈S s.t. a∈S⋀s∈S∖{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 a∈ArgsS, then for each S⊆ArgsS with a∈S: (S∖{a}) is a model of DaS (resp. CDaS) iff there exists an S′⊆S with a∈S′ such that S′∈S.

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=ArgsS∪⋃a∈ArgsS{αaγ∣γ∈CDaS}RSdef=⋃a∈ArgsS{({b},αaγ),({αaγ},αaγ),({αaγ},a)∣γ∈CDaS,b∈γ}
the defense-argumentation-framework of S, and let FS,PAttadm,k=FS,PAttcf,k∪FSdef.

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 S∈adm(FSdef) iff S=⋃T for some T⊆S.

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 T⊆S.

⇒: Let S∈adm(FSdef) and consider an argument a∈S. 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 a∈S there is a T⊆S such that S=⋃T.

⇐: Let T⊆S and S=⋃T. Consider a∈S and a set T∈T with a∈T. 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, S∈adm(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,k∪FSdef from Definition 26 and show that S=adm(FS,PAttadm,k).

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

  • S⊇adm(FS,PAttadm): Consider S∈adm(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, S∈adm(FS,PAttcf) and S∈adm(FSdef).

    By Lemma 20 we have that S=⋃T for some T⊆S. Now by Lemma 17 we have that if S∈cf(FS,PAttcf,k) then S∈S. As we already know that S∈adm(FS,PAttcf,k)⊆S we obtain S∈S.

 □

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

Proposition 14.

Σadmk={S≠∅∣S 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={S≠∅∣S 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)∈R∣S⊆Argsadm(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,T∈pref(F) with E≠T. By the maximality of E and T we have that E∪T∉pref(F), E∪T is not contained in any preferred extension, and, by Lemma 2, we know that E∪T defends itself against all attackers. That is, there is a conflict (B,a)∈R such that B⊆E∪T and a∈E∪T.

  • If a∈E then, as E is conflict-free, B∩T≠∅. Moreover, as E is admissible it has to defend itself against (B,a), i.e. there is an attack (S,b) with S⊆E and b∈B∩T. Hence, we have (S,b)∈PAtt.

  • If a∈T then, as T is conflict-free, B∩E≠∅. Moreover, as T is admissible it has to defend itself against (B,a), i.e. there is an attack (S′,c) with S′⊆T and c∈B∩E. Now, as E is admissible as well, there is also an attack (S,b) with S⊆E and b∈S⊆T. Hence, we have (S,b)∈PAtt.

2) If (S,b)∈PAtt then S attacks b in F. Thus each set S′∈pref(F) with b∈S′ defends itself against S, i.e. for each S′∈pref(F) with b∈S′ there is a pair (S″,a)∈R with S″⊆S′ and a∈S. 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={S≠∅∣S is k-adm-fortable and contains ∅} and

  • Σprefk={S≠∅∣S is k-adm-fortable and incomparable}.

Example 15.

Reconsider the argument set A={a1,a2,…,ak+1,ak+2} and the extension-set T={S⊆A∣|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 S1={a1,a2,…,ak+1}, S2={a2,a2,…,ak+2}, with S1∪S2∉T we need S′⊂S1 and t∈S2 such that S′∪{t}∈PAtt which is not true and thus there is no set PAtt such that the extension-sets are k-defensive w.r.t. PAtt. Hence, T (resp. U) cannot be realized as preferred (resp. admissible) extensions of a k-SETAF. However, one can verify that T is (k+1)-adm-fortable and thus T can be realized as preferred extensions of a (k+1)-SETAF as well as U can be realized as admissible extensions of a (k+1)-SETAF. To this end consider PAtt={(S,a)∣S⊆A|S|=k+1,a∈A∖S}. First, the extension-sets are both (k+1)-conflict-sensitive w.r.t. PAtt, e.g. for S1={a1,a2,…,ak+1}, S2={a2,a2,…,ak+2} with S1∪S2∉T we have S1∪{ak+2}∈PAtt (symmetric arguments work for other pairs of extensions from T). Second, the extension-sets are both (k+1)-defensive as for each (S,a)∈PAtt and a∈S′∈T there is an attack (S′,b)∈PAtt with b∈S (as a is the only argument not contained in S). That is, T is (k+1)-adm-fortable and with the same arguments we also get that U is (k+1)-adm-fortable.

4.4.Signature of complete semantics

This section heavily builds on recent work by Linsbichler [14]. Linsbichler provides an exact characterization for the signature of complete semantics in Dung AFs, i.e. of Σcom1 in our notation. In this section, we generalize his characterization and construction to the case of Σcomk for k⩾1.

In a first step we parametrize the notion of being com-closed by (a) a reference k to the arity of the attacks and (b) by reference to a subset PAtt of the possible attacks between arguments in ArgsS.

Definition 27.

Given an integer k⩾1, a set S⊆2A is called k-com-closed w.r.t. a set PAtt⊆{(S,b)∣|S|⩽k,S∪{b}∈PAttSk} iff for each T⊆S,T=⋃T we have |CS(T)|⩽1 and if |CS(T)|=0 then there is an attack (S,t)∈PAtt such that S∪{t}⊆T.

We summarize the necessary conditions for S∈Σcomk that refer to a set PAtt under the term k-com-fortable. That is, there must be a subset PAtt of the possible attacks between arguments in ArgsS such that S is k-defensive and k-com-closed w.r.t. PAtt. Additionally we require that, when considering the SETAF F=(ArgsS,PAtt), whenever CS(T)={C} for certain T then when we iteratively adding the arguments of C defended by T (in F) to the set T one eventually ends up with the set C.

Definition 28.

A set S⊆2A is called k-com-fortable if there exist a set PAtt⊆{(S,b)∣|S|⩽k,S∪{b}∈PAttSk} such that

  • (1) S is k-defensive w.r.t. PAtt,

  • (2) S is k-com-closed w.r.t. PAtt, and

  • (3) for each T⊆S and T=⋃T, if CS(T)={C} then there is an order (c1,…ck) of the elements in C∖T s.t. ∀(S,ci)∈PAtt: ∃S′⊆T∪{c1,…,ci−1},d∈S:(S′,d)∈PAtt.

Lemma 22.

For any k-SETAF F we have that com(F) is k-comp-fortable and ⋂com(F)∈com(F).

Proof.

First of all, we have ⋂com(F)=grd(F)∈com(F) and thus the second property is always satisfied. In order to show that com(F) is k-comp-fortable we have to construct a set PAtt satisfying the three properties. To this end let F=(A,R) and PAtt=R∩(Argscom(F)×Argscom(F)), i.e, we consider all the attacks between arguments that appear in at least one complete extension. It remains to check the three properties for being k-comp-fortable.

  • (1) com(F) is k-defensive w.r.t. PAtt: Consider a set E∈com(F) an attack (S,e)∈PAtt with e∈E. Thus (S,e)∈R and as E is admissible there is an attack (E′,s)∈R with s∈S and E′⊆E. Then by construction also (E′,s)∈PAtt and therefore com(F) is k-defensive w.r.t. PAtt.

  • (2) com(F) is k-com-closed w.r.t. PAtt: Consider a subset of the complete extensions T⊆com(F). By Lemma 2 we have that T=⋃T defends itself. Now either, there is an attack (S,a)∈R with S∪{a}⊂T and thus (S,a)∈PAtt as well, or T is an admissible set and thus there is a unique minimal complete extension E such that T⊆E, i.e., T has a unique completion in com(F).

  • (3) Consider a subset of the complete extensions T⊆com(F) such that T=⋃T is admissible and let C be the unique minimal complete extension E such that T⊆E. In case T=C all the conditions are trivially satisfied, thus we consider T⊂C. Now to order the arguments in C′=C∖T we use the following procedure: Starting from c1 iteratively select element ci by picking an arbitrary argument in C′∖{c1,…,ci−1} that is defended by T∪{c1,…,ci−1}. If these procedure succeeds we have found an order satisfying the conditions for being k-comp-fortable. Thus, towards a contradiction, let us assume the procedure eventually fails in picking an argument ci. That is, the set Ti−1=T∪{c1,…,ci−1} does not defend any argument in C′∖{c1,…,ci−1}. Moreover, as T⊆C and C is complete we have that Ti−1 does not defend any argument outside of Ti−1. That is, by Lemma 1, we have that Ti−1 is admissible, the set Ti−1 is a complete extension with T⊆Ti−1 which is in contradiction to the minimality of E.

 □

In order to realize extension-sets with complete semantics, again we first assume that ∅∈S, and then extend the construction to the general case. We build the k-SETAF with several modules, starting with recalling the module that exploits conflict-freeness from Definition 24. For a set PAtt⊆{(S,b)∣|S|⩽k,S∪{b}∈PAttSk} we have the k-SETAF FS,PAttcf,k=(ArgsS,PAtt).

Lemma 23.

Let S be k-com-closed w.r.t. PAtt⊆{(S,b)∣|S|⩽k,S∪{b}∈PAttSk} and T⊆ArgsS be some set of arguments such that T=⋃T for some subset T⊆S. Then, we have that T∈cf(FS,PAttcf,k) implies |CS(T)|=1.

Proof.

Consider T=⋃T and assume |CS(T)|=0. Then, as S is k-com-closed w.r.t. PAtt, there is an attack (S,t)∈PAtt with S∪{t}⊆T. By the construction of FS,PAttcf,k, this is in contradiction to T∈cf(FS,PAttcf,k). □

We next adapt the idea of defense-formulas, which we used for admissible semantics, to so-called extended-defense-formulas. To this end for each argument a∈ArgsS we consider all sets T=ArgsT with T⊆S such that |CS(T)|=1 and a∈CS(T).

Definition 29.

Given an extension-set S, the extended-defense-formula EDaS of an argument a∈ArgsS in S is defined as

⋁T∈{⋃T∣T⊆S} s.t. a∈CS(T)⋀s∈Ts
EDaS given as (a logically equivalent) CNF is called CNF-extended-defense-formula CEDaS of a in S.

The extended-defense-formula EDaS 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 (which is in the spirit of Lemma 19 for defense-formulas).

Lemma 24.

Given an extension-set S and an argument a∈ArgsS, then for each S⊆ArgsS with a∈S: S is a model of EDaS (resp. CEDaS) iff there exists an T⊆S,T=⋃T with a∈CS(T) and T⊆S.

Proof.

Notice that our formula EDaS only contains positive literals.

⇒: If S is a model of EDaS then it satisfies one of the conjuncts ⋀s∈T, and thus there is a set T⊆S with a∈CS(T) and T=⋃T for some T⊆S.

⇐: Assume that S has a subset T with a∈T and T=⋃T for some T⊆S. Then consider the sub-formula ⋀s∈Ts. As S is a super-set of T, S satisfies the sub-formula and thus also the disjunction over all sub-formulas. □

We next extend the concept of defense-argumentation-framework (cf. Definition 26).

Definition 30.

Given an extension-set S with ∅∈S, we call FSedef=(ASedef,RSedef) with

ASedef=ArgsS∪⋃a∈ArgsS{αaγ∣γ∈CEDaS}RSedef=⋃a∈ArgsS{({b},αaγ),({αaγ},αaγ),({αaγ},a)∣γ∈CEDaS,b∈γ}
the extended defense-argumentation-framework of S. Given an extension-set S and S′=reduced(S) we define FS,PAttcom,k=FS,PAttcf,k∪FS′edef.

We next show that FS,PAttcom,k realizes any k-comp-fortable extension-set S with ∅∈S.

Lemma 25.

For every extension-set S with ∅∈S that satisfies the three conditions for being k-comp-fortable w.r.t. a set PAtt⊆{(S,b)∣|S|⩽k,S∪{b}∈PAttSk} we have com(FS,PAttcom)=S.

Proof.

com(FS,PAttcom)⊆S: Consider S∈FS,PAttcom. As S is conflict free, by the construction of FS,PAttcf,k, we have that there is no attack (S′,a)∈PAtt with S′∪{a}⊆S. Let TS={T∈S∣T⊆S}. As S defends each argument in s∈S, against attackers αsγ, the set S is a model of EDsS. Thus, by Lemma 24, for each s∈S there is a set Ts⊆TS with Ts=⋃Ts⊆S and s∈CS(Ts). Let TS=⋃TS then as TS⊆S, by Lemma 23, it has a unique completion in S w.r.t. PAtt and by the above S⊆CS(TS). Next, we show that each argument s∈CS(TS) is defended by S and thus contained in S. Using the third condition of S being k-comp-fortable we have an order on the arguments CS(TS)∖TS as (c1,c2,…,ck) such that T∪{c1,…,ci−1} defends ci against all attacks from PAtt. Moreover, as T is a model of all EDcS for c∈{c1,…,ck}, by the construction of FSedef it defends the arguments c1,…,ck against attacks αciγ. Thus by induction on i all the arguments ci are defended and contained in S. Hence, CS(T)=S and hence S∈S.

com(FS,PAttcom)⊇S: Consider S∈S. By construction we have that S∈cf(FS,PAttcom). It remains to show that (i) S defends each of its arguments and (ii) does not defend any argument in ArgsS∖S (the arguments outside of ArgsS are self-attacking anyway).

  • (i) To show S∈adm(FS,PAttcom) consider an arbitrary argument s∈S. There are two kinds of attackers. First, the arguments αaγ. These arguments are attacked by S as S is a model of the formula CEDsS (cf. Lemma 24). Second, the attacks (B,s)∈PAtt. As S is k-defensive, there is a set S′⊆S and an argument b∈B such that (S′,b)∈PAtt. That is, S defends each s∈S.

  • (ii) To show S∈com(FS,PAttcom) consider an arbitrary argument a∈ArgsS∖S. As S∈S we have that CS(S)=S and thus neither the set S nor any of its subsets appear in the definition of the formula CEDaS, i.e., none of this sets is a model of CEDaS (cf. Lemma 24). That is, there is an argument αaγ that is not attacked by S but attacks a (note that, by construction, CEDaS has at least one clause, as there is always at least one T∈S with a∈CS(T)). Thus, S does not defend a. Hence, S is a complete extension of FS,PAttcom.

 □

We now can state the exact characterization of the complete signature in k-SETAFs.

Theorem 11.

Σcomk={S≠∅∣S is k-comp-fortable and ⋂S∈S}.

Proof.

The necessity of the conditions is by Lemma 22. To show that the conditions are also sufficient consider S′=reduced(S). By Lemma 25 we have an k-SETAF FS′,PAttcom with com(FS′,PAttcom)=S′. Thus with F=FS′,PAttcom∪(ArgsS,∅) we obtain com(F)=S. Also notice that FS,PAttcom=FS′,PAttcom∪(ArgsS,∅)=F. □

Example 16.

Consider the argument set A={a1,a2,…,ak+1,ak+2} and the extension-set U={S⊆A∣|S|=k+1}∪{∅} (cf. Example 15). Recall that PAttUk=∅ and thus the empty set is the only candidate for the set PAtt. We next show that U is not k-com-closed w.r.t. PAtt. Consider the sets S1={a1,a2,…,ak+1}, S2={a2,a2,…,ak+2}, with S1∪S2∉U and thus |CS(S1∪S2)|=0. In order to satisfy the k-com-closed we need an attack (S,t)∈PAtt such that S∪{t}⊆S1∪S2. However, as PAtt is empty there is no such attack an thus there is no set PAtt such that U is not k-com-closed w.r.t. PAtt. Hence, U cannot be realized with a k-SETAF and complete semantics. However, one can easily verify that for the (k+1)-SETAF F=(A,{(S,a)∣S∈T,a∈A∖S}) we have com(F)=U.

Exploiting a translation from [12] we can show that Σadmk⊆Σcomk.

Proposition 16.

Σadmk⊆Σcomk.

Proof.

Consider a set S∈Σadmk, i.e., there is a SETAF F=(A,R) with adm(F)=S. Now we apply the translation from admissible to complete semantics in Dung AFs [12]. That is we construct the SETAF F′=(A′,R′) with

A′=A∪{a′∣a∈A}R′=R∪{({a′},a′),({a},a′),({a′},a)∣a∈A}
Now it is easy to verify that none of the new arguments can be in an admissible set and moreover as the new attacks are all symmetric we have adm(F)=adm(F′). Finally, as for each a∈A, the argument a is the only argument attacking a′ and, thus, only sets containing a can defend a. Thus in F′ admissible sets and complete extensions coincide, i.e., com(F′)=adm(F′)=adm(F)=S and thus S∈Σcomk. □

Next, we give an example of an extension-set S∈Σcomk, but S∉Σadmk and thus show Σadmk⊂Σcomk.

Example 17.

Recall Example 9 showing that Σadm∞⊂Σcom∞. There we had the extension-set S={∅,{a},{b},{a,b,c}} which is not in Σadm∞ and thus also S∉Σadmk. However we can realize S with the 1-SETAF F=(A,R) with

A={a,b,c}∪{xa,xb,xc,yc}R={({xi},xi),({xi},i)∣i∈{a,b,c}}∪{({yc},yc),({yc},c)}∪{({a},xa),{b},xb),({a},xc),{b},yc)}
It can easily verified that com(F)=S and thus S∈Σcomk for k⩾1.

By the Examples 15, 16, & 17 we have that (a) there are extension-sets that are in Σcom1 but in no Σadmk (not even in Σadm∞) and that (b) there are extension-sets in Σadmk+1 that are not contained in Σcomk.

4.5.Signatures of semi-stable and stage semantics

Finally, we consider the signatures for semi-stable and stage semantics on SETAFs with attacks of bounded degree. As we will see, it turns out that semi-stable semantics on k-SETAFs is equally expressible to preferred semantics; and stage semantics is equally expressible (modulo the empty set of extensions) to stable semantics. This mirrors the behavior for Dung AFs.

We first exploit our results for preferred semantics to characterize the signature of semi-stable semantics.

Proposition 17.

Σsemk={S≠∅∣S is incomparable and k-adm-fortable}.

Proof.

Let F=(A,R) be a k-SETAF. We show that sem(F) is incomparable and k-adm-fortable. sem(F) is incomparable as it is a subset of pref(F) which is incomparable by definition. Now we can proceed as in the proof of Proposition 15 and consider the set PAtt={(S,a)∈R∣S⊆Argsadm(F)}. As shown there this set satisfies the conditions for S being k-adm-fortable.

Next we argue that Σprefk⊆Σsemk. To show this we adapt the translation from preferred to semi-stable semantics in Dung AFs from [12]. That is given a SETAF F=(A,R) we construct F′=(A′,R′) with

A′=A∪{a′∣a∈A}R′=R∪{({a′},a′),({a},a′)∣a∈A}
Now it is easy to verify that pref(F)=pref(F′)=sem(F′). That is, for each S∈Σprefk we have a SETAF F with pref(F)=S and thus a SETAF F′ with sem(F)=S, i.e., S∈Σsemk. By Proposition 15 we thus have that each non-empty incomparable and k-defensive extension-set S can be realized as a k-SETAF with semi-stable semantics. □

Next we exploit our results for stable semantics to characterize the signature of stage semantics.

Proposition 18.

Σstagek={S≠∅∣S is incomparable and k-tight}.

Proof.

First consider stage(F) for some k-SETAF F. As stb(F)⊆naive(F), and naive(F) is incomparable by definition, we have that stb(F) is incomparable, as well. Now consider E∈stage(F). As each stage extensions is also a naive extensions for each argument a∉E there is an attack (B,b) such that B∪{b}⊆E∪{a}. That is there is no E′∈stage(F) with B∪{b}⊆E′ and thus B∪{b}∈PAttstage(F). That is, the extension-set stage(F) is k-tight.

Now consider S∈Σstbk, i.e., there is an SETAF F with stb(F)=S. If S is non-empty, by Lemma 7, we also have stage(F)=S. Thus, by Theorem 9, each non-empty incomparable and k-tight extension-set S can be realized as a k-SETAF by stage semantics. □

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

Theorem 12.

We have that

  • Σstagek={S≠∅∣S is incomparable and k-tight} and

  • Σsemk={S≠∅∣S is incomparable and k-adm-fortable}.

4.6.Discussion of results on k-SETAFs

Our results on signatures of k-SETAFs (cf. Theorems 8–12) are summarized as follows.

Main Theorem 2.

The signatures for k-SETAFs can be characterized as follows:

Σcfk={S≠∅∣S is downward-closed and k-tight}Σnaivek={S≠∅∣S is incomparable and dcl(S) is k-tight}Σstbk={S∣S is incomparable and k-tight}Σadmk={S≠∅∣S is k-adm-fortable and contains ∅}Σprefk={S≠∅∣S is incomparable and k-adm-fortable}Σcomk={S≠∅∣S is k-com-fortable and ⋂S∈S}Σstagek={S≠∅∣S is incomparable and k-tight}Σsemk={S≠∅∣S is incomparable and k-adm-fortable}

For all semantics σ∈{cf,naive,stb,adm,pref,stage,sem} and 2⩽k<∞

(3)Σσ1⊂Σσk⊂Σσk+1⊂Σσ∞

The ⊆-relations follow immediately from the fact that AFAk⊆AFAk+1 and the definition of signatures. That the relations are strict has been illustrated in Examples 12– 13, 15, and 16.

Next we analyse the relation between signatures of different semantics for fixed k.

Proposition 19.

Every k-tight incomparable extension-set is also k-adm-fortable.

Proof.

Consider some k-tight incomparable extension-set S. We define PAtt as the set of pairs (S′,a) with S′∪{a}∈PAttSk and S′⊆S∈S. We next show that PAtt meets the conditions of Definition 23, i.e. S is k-conflict-sensitive and k-defensive w.r.t. PAtt.

  • S is k-conflict-sensitive w.r.t. PAtt: Consider S,T∈S. As S is incomparable we have S∪T∉S and for each t∈T∖S that S∪{t}∉S. In particular there exists at least one t∈T∖S and as S is k-tight there is a set S′⊆S with S′∪{t}∈PAttSk. By the construction of PAtt we have (S′,t)∈PAtt and the condition for being k-conflict-sensitive is satisfied

  • S is k-defensive w.r.t. PAtt: Now consider a set T∈S that is attacked by (S′,t)∈PAtt, i.e. t∈T. We have that S′ must contain an argument s such that T∪{s}∉S otherwise, as S is incomparable, S′∪{t}⊆T and thus S′∪{t}∉PAttSk. Then, as S is tight, there is a pair (T′,s)∈PAtt with T′⊆T and hence also the condition for being k-defensive is satisfied.

As S is both k-conflict-sensitive and k-defensive w.r.t. the constructed PAtt we obtain that S is k-adm-fortable. □

Hence, for k-SETAFs, the preferred semantics is more expressible than stable semantics. We next show that preferred semantics is indeed strictly more expressible than stable semantics.

Example 18.

We consider the argument set A=B∪C∪{e} with B={b1,b2,…,bk+1}, C={c1,c2,…,ck+1} and the extension-set S that contains (i) the set B, and (ii) the sets B∪{ci,e}∖{bi} for 1⩽i⩽k+1. It is easy to verify that S is incomparable. We next argue that the set S is not k-tight. Consider B∈S and the argument e. We have that S∪{e}∉S but for each S′⊂S with |S′|⩽k the set S′∪{e} is contained in one of the sets in S and thus S′∪{e}∉PAttSk. That is, S is not k-tight and cannot be realized with a k-SETAF under stable semantics. However, one can easily verify that S is conflict-sensitive and thus S can be realized with a 1-SETAF (and thus, by (3), with a k-SETAF for any k⩾1) under preferred semantics.

Moreover, recall that, for incomparable S, whenever S is k-tight, also dcl(S) is k-tight. Hence, Σnaivek⊆Σstbk∖{∅}. By Example 14, Σnaivek⊂Σstbk∖{∅}.

We conclude that for any k⩾1,

Σnaivek⊂Σstbk∖{∅}=Σstagek⊂Σprefk=Σsemk.

We finally turn to the relation between conflict-free sets, admissible sets and complete extensions. Recall that Proposition 16 already showed Σadmk⊆Σcomk. Example 17 in fact shows Σadmk⊂Σcomk for k⩾1. Inspecting Example 6 and 10 we have an extension-set S′={∅,{a},{b},{c},{a,b},{b,c},{a,c}} with S′∈Σcf2 but S′∉Σadm∞ and S′∉Σcom∞ which shows that, for k⩾2, Σcfk⊈Σadmk and Σcfk⊈Σcomk. Likewise, Σcfk⊉Σadmk is easy to see (k⩾1), e.g. consider S={∅,{a,b}} with S∈Σadm1 but, as S is not downward-closed, S∉Σcf∞. By Proposition 16, Σcfk⊉Σcomk follows, as well.

Finally, we show that the result of Proposition 11 carries over to k-SETAFs for any k⩾1.

Proposition 20.

Σcfk∩Σcomk⊆Σadmk.

Proof.

Consider S∈Σcf∞∩Σcom∞, i.e., a non-empty downward-closed, k-tight and k-com-fortable extension-set. Consider the set PAtt that satisfies the conditions for S being k-com-fortable. We immediately obtain that ∅∈S (S is nonempty and downward-closed) and that S is k-defensive w.r.t. PAtt. It remains to show that S is k-conflict-sensitive w.r.t. PAtt. Thus consider arbitrary A,B∈S such that A∪B∉S. As S is downward closed this implies |CS(A∪B)|=0 and thus, as S is k-com closed there is (T,u)∈PAtt with T∪{b}∈A∪B, w.l.o.g. b∈B. As S is k-defensive there is also an attack (B′,a) with B′⊂B, a∈T∩A and further an attack (A′,b′) with A′⊂A, b′∈B′. That is, S is also k-conflict-sensitive. □

The relation between the different signatures for k-SETAFs is depicted in Fig. 5.

Fig. 5.

Relations between signatures in k-SETAFs (cf. Main Theorem 2).

Relations between signatures in k-SETAFs (cf. Main Theorem 2).

5.Discussion and related work

In this paper we studied the expressiveness of SETAFs, a generalization of Dung’s abstract argumentation frameworks due to Nielsen and Parsons that extends the notion of (binary) attacks to collective attacks. In order to do so we investigated signatures for seven standard semantics. The signature Σσ∞ for a semantics σ is given by the collection of all sets of σ-extensions that can be expressed with at least one SETAF. Providing characterizations for signatures allows for an easy comparison of different semantics and we classify a semantics σ as more expressible than a semantics σ′ if Σσ∞⊇Σσ′∞. While Σσ∞ concerns the expressibility of SETAFs of arbitrary structure, we also considered the signatures Σσk of syntactically restricted SETAFs where the cardinality of attacks (S,a) is bounded by an arbitrary but fixed constant k, i.e. |S|⩽k. We call such SETAFs also k-SETAFs. This yields signatures for Dung AFs as special case, since 1-SETAFs exactly gives this class.

Our main results for unrestricted SETAFs (see Main Theorem 1 and Fig. 4) show that SETAF-signatures coincide for preferred, naive, semi-stable, stage, and (modulo the empty set of extensions) stable semantics, i.e. we have proven

Σnaive∞=Σstb∞∖{∅}=Σstage∞=Σpref∞=Σsem∞.
The picture changes as soon as we turn to k-SETAFs (see Main Theorem 2 and Fig. 5). Here we get the same relations as were already known for Dung AFs. That is, we have for any k⩾1,
Σnaivek⊂Σstbk∖{∅}=Σstagek⊂Σprefk=Σsemk.
Another interesting finding is that the relation between conflict-free, admissible, and complete semantics differs compared to Dung AFs. In fact, while for Dung AFs we have Σcf1⊆Σadm1⊆Σcom1, for k⩾2 we get Σcfk⊈Σcomk while Σadmk⊆Σcomk remains valid. Finally, we have shown that expressibility of SETAFs form a strict hierarchy w.r.t. the attack-cardinality: for all semantics σ∈{cf,naive,stb,adm,pref,stage,sem} and 2⩽k<∞, it holds that
Σσ1⊂Σσk⊂Σσk+1⊂Σσ∞
Hence, our results shed additional light on the properties of different argumentation semantics. In particular, we have analyzed here how expressibility of a semantics changes, if the structural features an abstract argumentation formalism at hand provides are gradually extended. Another important implication is that for SETAFs, preferred semantics (and likewise, stable, stage, naive, and semi-stable) essentially have the maximal possible expressive power, if one does not want to give up incomparability. In other words, since each possible incomparable set of extensions is provided by at least one SETAF, there is no need to further extend syntactic features of SETAFs to increase the expressibility.

Related work on signatures. The investigations of signatures have been initiated in [7], where the first characterization for Dung AFs have been introduced. Further analyses include signatures for compact AFs [1] where, given a semantics σ, one restricts the attention to AFs (A,R) where each argument of A is contained in at least one σ-extension. Another line of research is provided in [8] where semantics are coupled together in the concept of signature, i.e. one is interested in all pairs (S,S′) such that there is a framework with σ-extensions S and σ′-extensions S′. In our work, we already have related the signatures for Dung AFs with the signatures for SETAFs. In particular, we have seen that switching from binary to ternary attacks already yields a higher expressibility. Another interesting observation concerns compact frameworks. Inspecting our construction (cf. Definition 10) used to characterize signatures Σσ∞ for σ∈{stb,stage,pref,sem} shows that every S∈Σσ∞ can be realized with a SETAF that consists of arguments from S only. In other words, the signature for compact SETAFs and arbitrary SETAFs coincide under these semantics, which is not the case for Dung AFs [1].

Signatures have also been intensively studied for abstract dialectical frameworks (ADFs). ADFs specify the relation between arguments via acceptance conditions which are propositional formulas that are attached to each argument in the framework. In fact, as for instance clarified in [26], SETAFs can be understood as a particular subclass of ADFs where each acceptance conditions is given by a CNF over negative literals. General results on ADF signatures for the 3-valued semantics of ADFs (preferred, complete, admissible) have been provided by Pührer [18]. For the two-valued stable semantics of ADFs, similar results were provided by Strass [19]. Interestingly, for the subclass of bipolar ADFs it turns out that SETAFs and bipolar ADFs are equally expressible under stable semantics, i.e. their signatures coincide. The work closest to ours is by Linsbichler et al. [15] and by Polberg [17]. The former studies SETAFs as a sub-class of ADFs with 3-valued semantics. In order to meet the 3-valued setting the extension-based semantics of SETAFs are redefined as 3-valued semantics and an algorithmic framework is provided that tests whether a given set of 3-valued extensions can be realized as a SETAF. Their results allow to compare the expressiveness of admissible, complete, preferred, and stable semantics in AFs, SETAFs, and ADFs, but do not provide an explicit characterization of the sets that can be realized as SETAFs. Moreover, the setting with 3-valued semantics is more restrictive than the extension-based view and thus these results do not translate to the original definition of Dung AF and SETAF semantics. The work of Polberg [17, Section 4.4.1] studies translations between different abstract argumentation formalisms in the extension-based setting. It already shows that there are certain sets of extensions that can be realized by SETAFs but cannot be realized with AFs, in order to show that certain translations are impossible. However, the exact expressiveness of SETAFs is not investigated any further. Finally, signatures of further ADF subclasses have been investigated in [5]. However, their focus is on particular classes of symmetric ADFs and thus their results are not directly related to our investigations.

Further related work. Another measurement for the expressibility of formalisms is provided via complexity analysis. It is worth to notice that recent results [11] show that reasoning in SETAFs has the same complexity as reasoning in AFs [9]. In fact, this holds for all the semantics we consider here. This shows that studying and comparing the signatures of these formalisms provides a much more fine-grained picture concerning their expressibility.

In a recent paper, Flouris and Bikakis [13] investigate semantics of SETAFs and their relations. They extended semi-stable, stage, ideal and eager semantics to SETAFs, and provide three-valued labeling-based semantics for SETAFs.33 Moreover, they consider a translation from SETAFs to AFs (similar to that in [17]) and investigate the relations between extensions of the SETAF and extensions of the corresponding AF under the different semantics. While we did not consider ideal and eager semantics in our work, both semantics always propose a unique extension (for finite SETAFs) and thus we have Σideal∞=Σidealk=Σeager∞=Σeagerk={S∣|S|=1} for all integers k⩾1, cf. Proposition 1.

We also would like to mention here some work that considers collective attacks in a different manner than it is done in SETAFs. Bochman [2], for instance, extends Dung AFs such that sets of arguments can attack sets of arguments (i.e., it is not a single argument that is attacked). This however, leads to the development of new semantics and thus a direct application of our results is not possible. Finally, there is the work by Verheij rooted in dialectical argumentation which introduces several frameworks that allow for collective attacks [22–25]. Again, all these systems come with there own semantics, i.e. not generalizing Dung AF semantics, and thus a direct application of our results is not possible.

Future work. One direction of future research is to consider signatures for subclasses of SETAFs. Besides syntactic restrictions (for instance, generalizations of bipartite or symmetric AFs), we would like to study the already mentioned concept of compact SETAFs. This includes an analysis for compact SETAFs for admissible and complete semantics, and moreover, the question whether the relations between signatures for compact AFs as provided by [1] carry over to compact k-SETAFs. Another direction of research is to understand the interplay between semantics in SETAFs. As we have mentioned above, results for Dung AFs in this respect have been provided in [8] via the concept of 2-dimensional signatures. It is an interesting question to which extent these results apply to SETAFs as well.

Notes

1 This way of lifting attacks to sets of arguments is characteristic for SETAFs and crucial in the definition of the notion of defense. The fact that it suffices to attack one argument to attack a set reflects the conjunctive nature of collective attacks.

2 We note that for any incomparable extension-set S, FScf=FSstb.

3 For admissible, complete, preferred and stable semantics their approaches to labeling-based semantics seem to be equivalent to three-valued semantics of SETAFs introduced in [15].

Acknowledgements

This research has been supported by FWF through projects I2854 and P30168.

References

[1] 

R. Baumann, W. Dvořák, T. Linsbichler, C. Spanring, H. Strass and S. Woltran, On rejected arguments and implicit conflicts: The hidden power of argumentation semantics, Artif. Intell. 241: ((2016) ), 244–284. doi:10.1016/j.artint.2016.09.004.

[2] 

A. Bochman, Collective argumentation and disjunctive logic programming, J. Log. Comput. 13: (3) ((2003) ), 405–428. doi:10.1093/logcom/13.3.405.

[3] 

G. Brewka, S. Polberg and S. Woltran, Generalizations of dung frameworks and their role in formal argumentation, IEEE Intelligent Systems 29: (1) ((2014) ), 30–38. doi:10.1109/MIS.2013.122.

[4] 

M. Caminada, W.A. Carnielli and P.E. Dunne, Semi-stable semantics, J. Log. Comput. 22: ((2012) ), 1207–1254. doi:10.1093/logcom/exr033.

[5] 

M. Diller, A. Keshavarzi Zafarghandi, T. Linsbichler and S. Woltran, Investigating subclasses of abstract dialectical frameworks, in: Computational Models of Argument – Proceedings of COMMA 2018, Warsaw, Poland, 12–14 September 2018, S. Modgil, K. Budzynska and J. Lawrence, eds, Frontiers in Artificial Intelligence and Applications, Vol. 305: , IOS Press, (2018) , pp. 61–72, http://ebooks.iospress.nl/volume/computational-models-of-argument-proceedings-of-comma-2018. ISBN 978-1-61499-905-8.

[6] 

P.M. Dung, On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games, Artif. Intell. 77: (2) ((1995) ), 321–358. doi:10.1016/0004-3702(94)00041-X.

[7] 

P.E. Dunne, W. Dvořák, T. Linsbichler and S. Woltran, Characteristics of multiple viewpoints in abstract argumentation, Artif. Intell. 228: ((2015) ), 153–178. doi:10.1016/j.artint.2015.07.006.

[8] 

P.E. Dunne, C. Spanring, T. Linsbichler and S. Woltran, Investigating the relationship between argumentation semantics via signatures, in: Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI 2016, New York, NY, USA, 9–15 July 2016, S. Kambhampati, ed., IJCAI/AAAI Press, (2016) , pp. 1051–1057, http://www.ijcai.org/Abstract/16/153. ISBN 978-1-57735-770-4.

[9] 

W. Dvořák and P.E. Dunne, Computational problems in formal argumentation and their complexity, in: Handbook of Formal Argumentation, P. Baroni, D. Gabbay, M. Giacomin and L. van der Torre, eds, College Publications, (2018) , pp. 2557–2622, Chap. 14. also appears in IfCoLog Journal of Logics and their Applications 4(8): 2557–2622.

[10] 

W. Dvořák, J. Fandinno and S. Woltran, On the expressive power of collective attacks, in: Computational Models of Argument – Proceedings of COMMA 2018, Warsaw, Poland, 12–14 September 2018, S. Modgil, K. Budzynska and J. Lawrence, eds, Frontiers in Artificial Intelligence and Applications, Vol. 305: , IOS Press, (2018) , pp. 49–60. ISBN 978-1-61499-905-8. doi:10.3233/978-1-61499-906-5-49.

[11] 

W. Dvořák, A. Greßler and S. Woltran, Evaluating SETAFs via answer-set programming, in: Proceedings of the Second International Workshop on Systems and Algorithms for Formal Argumentation (SAFA 2018) Co-Located with the 7th International Conference on Computational Models of Argument (COMMA 2018), Warsaw, Poland, September 11, 2018, M. Thimm, F. Cerutti and M. Vallati, eds, CEUR Workshop Proceedings, Vol. 2171: , CEUR-WS.org, (2018) , pp. 10–21, http://ceur-ws.org/Vol-2171/paper_2.pdf.

[12] 

W. Dvořák and S. Woltran, On the intertranslatability of argumentation semantics, J. Artif. Intell. Res. (JAIR) 41: ((2011) ), 445–475. doi:10.1613/jair.3318.

[13] 

G. Flouris and A. Bikakis, A comprehensive study of argumentation frameworks with sets of attacking arguments, International Journal of Approximate Reasoning 109: ((2019) ), 55–86, http://www.sciencedirect.com/science/article/pii/S0888613X18304742. doi:10.1016/j.ijar.2019.03.006.

[14] 

T. Linsbichler, Characteristics of Multiple Viewpoints in Abstract Argumentation under Complete Semantics, Technical Report, DBAI-TR–2018-113, Technische Universität Wien, 2018, http://www.dbai.tuwien.ac.at/research/report/dbai-tr-2018-113.pdf.

[15] 

T. Linsbichler, J. Pührer and H. Strass, A uniform account of realizability in abstract argumentation, in: Proc. ECAI, Frontiers in Artificial Intelligence and Applications, Vol. 285: , IOS Press, (2016) , pp. 252–260. ISBN 978-1-61499-671-2. doi:10.3233/978-1-61499-672-9-252.

[16] 

S.H. Nielsen and S. Parsons, A generalization of Dung’s abstract framework for argumentation: Arguing with sets of attacking arguments, in: Proc. ArgMAS, Lecture Notes in Computer Science, Vol. 4766: , Springer, (2006) , pp. 54–73.

[17] 

S. Polberg, Developing the abstract dialectical framework, PhD thesis, TU Wien, Institute of Information Systems, 2017, http://katalog.ub.tuwien.ac.at/AC13773888.

[18] 

J. Pührer, Realizability of three-valued semantics for abstract dialectical frameworks, in: Proc. IJCAI, AAAI Press, (2015) , pp. 3171–3177.

[19] 

H. Strass, Expressiveness of two-valued semantics for abstract dialectical frameworks, J. Artif. Intell. Res. 54: ((2015) ), 193–231. doi:10.1613/jair.4879.

[20] 

H. Strass, The relative expressiveness of abstract argumentation and logic programming, in: Proc. AAAI, AAAI Press, (2015) , pp. 1625–1631, http://www.aaai.org/ocs/index.php/AAAI/AAAI15/paper/view/9352. ISBN 978-1-57735-698-1.

[21] 

B. Verheij, Two approaches to dialectical argumentation: Admissible sets and argumentation stages, in: Proceedings of the 8th Dutch Conference on Artificial Intelligence (NAIC’96), J.J.C. Meyer and L.C. van der Gaag, eds, (1996) , pp. 357–368.

[22] 

B. Verheij, Rules, Reasons, Arguments. Formal studies of argumentation and defeat, PhD thesis, Universiteit Maastricht, 1996, https://cris.maastrichtuniversity.nl/portal/files/1736888/guid-f8972ab2-c68f-4291-b229-d5207cd83320-ASSET1.0.

[23] 

B. Verheij, Argue! – an implemented system for computer-mediated defeasible argumentation, in: Proceedings of the Tenth Netherlands/Belgium Conference on Artificial Intelligence (NAIC ’98), H.L. Poutré and H. van den Herik, eds, CWI, Amsterdam, Netherlands, (1998) , pp. 57–66.

[24] 

B. Verheij, DefLog: On the logical interpretation of prima facie justified assumptions, J. Log. Comput. 13: (3) ((2003) ), 319–346. doi:10.1093/logcom/13.3.319.

[25] 

B. Verheij, Artificial argument assistants for defeasible argumentation, Artif. Intell. 150: (1–2) ((2003) ), 291–324. doi:10.1016/S0004-3702(03)00107-3.

[26] 

J.P. Wallner, Structural constraints for dynamic operators in abstract argumentation, in: Computational Models of Argument – Proceedings of COMMA 2018, Warsaw, Poland, 12–14 September 2018, S. Modgil, K. Budzynska and J. Lawrence, eds, Frontiers in Artificial Intelligence and Applications, Vol. 305: , IOS Press, (2018) , pp. 73–84. ISBN 978-1-61499-905-8. doi:10.3233/978-1-61499-906-5-73.

[27] 

B. Yun, S. Vesic and M. Croitoru, Toward a more efficient generation of structured argumentation graphs, in: Computational Models of Argument – Proceedings of COMMA 2018, Warsaw, Poland, 12–14 September 2018, S. Modgil, K. Budzynska and J. Lawrence, eds, Frontiers in Artificial Intelligence and Applications, Vol. 305: , IOS Press, (2018) , pp. 205–212. ISBN 978-1-61499-905-8. doi:10.3233/978-1-61499-906-5-205.

Show more