On the expressive power of collective attacks

Abstract

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

Keywords

Abstract argumentation SETAF collective attacks expressiveness

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.

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^{'} \in S$ , $S \subseteq 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 ( $Σ_{σ}^{\infty}$ ).

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 ( $Σ_{σ}^{\infty}$ ), 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 \subseteq A$ is finite, and $R \subseteq (2^{A} ∖ {\emptyset}) \times A$ is the attack relation. For an integer $k ⩾ 1$ , a k-SETAF is a SETAF $(A, R)$ where for all $(S, a) \in R$ , we have $| S | ⩽ k$ . The collection of all SETAFs (resp. k-SETAFs) over $A$ is given as ${AF}_{A}$ (resp. ${AF}_{A}^{k}$ ).

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 \mapsto_{R} b$ if there is a set $S^{'} \subseteq S$ with $(S^{'}, b) \in R$ . Moreover, we write $S^{'} \mapsto_{R} S$ if $S^{'} \mapsto_{R} b$ for some $b \in S$ .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.

We drop subscript R in $\mapsto_{R}$ if there is no ambiguity. For $S \subseteq A$ , we use $S_{R}^{+}$ to denote the set ${b ∣ S \mapsto_{R} b}$ of argument attacked by S (in R), and define the range of S (w.r.t. R), denoted $S_{R}^{\oplus}$ , as the set $S \cup S_{R}^{+}$ .
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} \mapsto_{R} c$ but neither ${a} \mapsto_{R} c$ nor ${b} \mapsto_{R} c$ for this SETAF. On the other hand ${a, b, c} \mapsto_{R} c$ indeed holds.

The notions of conflict and defense naturally generalize to SETAFs.
Definition 3.
Given a SETAF $F = (A, R)$ , a set $S \subseteq A$ is conflicting in F if $S \mapsto_{R} a$ for some $a \in S$ . A set $S \subseteq A$ is conflict-free in F, if S is not conflicting in F, i.e. if $S^{'} \cup {a} ⊈ S$ for each $(S^{'}, a) \in R$ .
Definition 4.
Given a SETAF $F = (A, R)$ , an argument $a \in A$ is defended (in F) by a set $S \subseteq A$ if for each $B \subseteq A$ , such that $B \mapsto_{R} a$ , also $S \mapsto_{R} B$ . A set T of arguments is defended (in F) by S if each $a \in T$ is defended by S (in F).

The notion of defense can be equivalently characterized as follows: an argument $a \in A$ is defended by a set $S \subseteq A$ if for each $(B, a) \in R$ we have $S \mapsto_{R} B$ .

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 \in 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 \in cf (F)$ , we say that
$S \in naive (F)$ , if there is no $T \in cf (F)$ with $T \supset S$ ,

$S \in stb (F)$ , if $S \mapsto a$ for all $a \in A ∖ S$ ,

$S \in pref (F)$ , if $S \in adm (F)$ and there is no $T \in adm (F)$ s.t. $T \supset S$ ,

$S \in com (F)$ , if $S \in adm (F)$ and $a \in S$ for all $a \in A$ defended by S,

$S \in grd (F)$ , if $S = ⋂_{T \in com (F)} T$ ,

$S \in stage (F)$ , if $∄ T \in cf (F)$ with $T_{R}^{\oplus} \supset S_{R}^{\oplus}$ , and

$S \in sem (F)$ , if $S \in adm (F)$ and $∄ T \in adm (F)$ s.t. $T_{R}^{\oplus} \supset S_{R}^{\oplus}$ .

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 ([16]).

Given a SETAF $F = (A, R)$ , a set $B \subset A$ , and arguments $a, b \in A$ that are defended by B in F. Then (a) $B \cup {a}$ is admissible in F and (b) $B \cup {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 \subseteq A$ . If both S and T defend itself in F, then $S \cup T$ defends itself in F.
Proof.
Towards a contradiction assume that $S \cup T$ does not defend itself, i.e. there exists a set $B \subseteq A$ with $B \mapsto (S \cup T)$ such that $(S \cup T) \mapsto B$ . Consider $B \mapsto S$ . Since $(S \cup T) \mapsto B$ also $S \mapsto B$ and thus S does not defend itself in F which is a contradiction to the assumption. The case where $B \mapsto 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, $\begin{matrix} stb (F) \subseteq pref (F) \subseteq com (F) \subseteq adm (F) \subseteq cf (F) \end{matrix}$ and $\begin{matrix} stb (F) \subseteq naive (F) \subseteq cf (F) . \end{matrix}$ 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) \subseteq 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 $E_{R}^{\oplus} = A$ and thus there cannot be another admissible set D of F with $E_{R}^{\oplus} \subset D_{R}^{\oplus}$ . Hence $E \in sem (F)$ . □
Lemma 4.
$stb (F) \subseteq 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 \in stb (F)$ we have that $E_{R}^{\oplus} = A$ and thus there cannot be another conflict-free set D of F with $E_{R}^{\oplus} \subset D_{R}^{\oplus}$ . Hence $E \in stage (F)$ . □
Lemma 5.
$sem (F) \subseteq 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 \subset D$ . Let $x \in D$ such that $x \notin E$ and $E \mapsto_{R} x$ (otherwise there would be a conflict in D). As the range operator $^{\oplus}$ is monotone by definition, we have $E_{R}^{\oplus} \subseteq D_{R}^{\oplus}$ and as $x \notin E_{R}^{\oplus}$ we obtain that $E_{R}^{\oplus} \subset D_{R}^{\oplus}$ . Hence, $E \notin sem (F)$ , a contradiction to our initial assumption. □
Lemma 6.
$stage (F) \subseteq 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 \subset D$ . Let $x \in D$ such that $x \notin E$ and $E \mapsto_{R} x$ . As the range operator $^{\oplus}$ is monotone by definition we have $E_{R}^{\oplus} \subseteq D_{R}^{\oplus}$ and as $x \notin E_{R}^{\oplus}$ we obtain that $E_{R}^{\oplus} \subset D_{R}^{\oplus}$ . Hence, $E \notin 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 $\begin{matrix} (1) & stb (F) \subseteq sem (F) \subseteq pref (F) \subseteq com (F) \subseteq adm (F) \subseteq cf (F) \end{matrix}$ and $\begin{matrix} (2) & stb (F) \subseteq stage (F) \subseteq naive (F) \subseteq cf (F) . \end{matrix}$

Moreover, the following property carries over from Dung AFs. Lemma 7.
For any SETAF $F = (A, R)$ , if $stb (F) \neq \emptyset$ then $stb (F) = sem (F) = stage (F)$ .
Proof.
Consider a SETAF $F = (A, R)$ with $stb (F) \neq \emptyset$ . 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 $\begin{matrix} Σ_{σ}^{k} = {σ (F) ∣ F \in {AF}_{A}^{k}} . \end{matrix}$ For unrestricted SETAFs we use $Σ_{σ}^{\infty} = {σ (F) ∣ F \in {AF}_{A}}$ . For $S \in Σ_{σ}^{k}$ (resp. $S \in Σ_{σ}^{\infty}$ ) we say that $S$ can be realized by k-SETAFs (resp. by SETAFs) under σ.

We require some further technical notions.
Definition 7.
Given $S \subseteq 2^{A}$ ,
we use ${Args}_{S}$ to denote $⋃_{S \in S} S$ , and

call $S$ an extension-set (over $A$ ) if ${Args}_{S}$ 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 ${Args}_{S}$ 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 \subseteq 2^{A}$ and $E \subseteq {Args}_{S}$ , we define
the downward-closure of $S$ as $dcl (S) = {S^{'} \subseteq S ∣ S \in S}$ ;

the set of potential conflicts in $S$ as ${PAtt}_{S} = {S \subseteq {Args}_{S} ∣ S \notin dcl (S)}$ ;

the completion-sets of E in $S$ as $C_{S} (E) = {S \in S ∣ E \subseteq S, ∄ S^{'} \in S, E \subseteq S^{'} \subset S}$ .

The downward-closure considers all subsets of sets in the extension-set. The set ${PAtt}_{S}$ list all attacks between arguments in ${Args}_{S}$ that do not add a conflicts within sets $S \in S$ . As all the semantics under our considerations are based on conflict-freeness this provides an upper bound on the attacks between arguments in ${PAtt}_{S}$ we can use in our constructions. Finally, the completion sets for E are the subset minimal sets $S \in S$ that contain E. In particular, if $E \in S$ then E itself is the only completion set of E.
Example 2.
Let $S = {{a, b}, {a, c}, {b, c}}$ . We have ${Args}_{S} = {a, b, c}$ and $dcl (S) = S \cup {{a}, {b}, {c}, \emptyset}$ . Furthermore, we have ${PAtt}_{S} = {{a, b, c}}$ , for $E = {a}$ , $C_{S} (E) = {{a, b}, {a, c}}$ , and for $E^{'} = {a, b, c}$ , $C_{S} (E^{'}) = \emptyset$ .
Definition 9.
Let $S \subseteq 2^{A}$ . We call $S$
downward-closed if $S = dcl (S)$ ;

incomparable if all elements $S \in S$ are pairwise incomparable, i.e. for each $S, S^{'} \in S$ , $S \subseteq S^{'}$ implies $S = S^{'}$ ;

tight if for all $S \in S$ and $a \in {Args}_{S}$ it holds that if $S \cup {a} \notin S$ then there exists an $s \in S$ such that ${a, s} \in {PAtt}_{S}$ ;

conflict-sensitive if for each $A, B \in S$ such that $A \cup B \notin S$ it holds that $\exists a, b \in A \cup B : {a, b} \in {PAtt}_{S}$ ;

com-closed if for each $T \subseteq S$ : if ${a, b} \notin {PAtt}_{S}$ for each $a, b \in {Args}_{T}$ , then ${Args}_{T}$ has a unique completion-set in S, i.e. $| C_{S} ({Args}_{T}) | = 1$ .

Example 3.
Let $S^{'} = {{a, b}, {b, c}}$ . Hence, ${PAtt}_{S^{'}} = {{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 \in S$ and ${a, c} \in {PAtt}_{S^{'}}$ ; for $T = {b, c}$ and argument a, we have $c \in T$ and again ${a, c} \in {PAtt}_{S^{'}}$ . Likewise, it can be checked that $S^{'}$ is conflict-sensitive since $a \in S$ , $c \in T$ and ${a, c} \in {PAtt}_{S^{'}}$ .

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 ([7]).

Characterizations of the signatures for Dung AFs are as follows: $\begin{array}{l} Σ_{cf}^{1} = {S \neq \emptyset ∣ S is downward-closed and tight} \\ Σ_{naive}^{1} = {S \neq \emptyset ∣ S is incomparable and dcl (S) is tight} \\ Σ_{stb}^{1} = {S ∣ S is incomparable and tight} \\ Σ_{stage}^{1} = {S \neq \emptyset ∣ S is incomparable and tight} \\ Σ_{adm}^{1} = {S \neq \emptyset ∣ S is conflict-sensitive and contains \emptyset} \\ Σ_{pref}^{1} = {S \neq \emptyset ∣ S is incomparable and conflict-sensitive} \\ Σ_{sem} = {S \neq \emptyset ∣ S is incomparable and conflict-sensitive} \\ Σ_{grd}^{1} = {S ∣ | S | = 1} \\ Σ_{com}^{1} \subseteq {S \neq \emptyset ∣ S is com-closed and ⋂ S \in S} \end{array}$

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).

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 ([7]).

The following relations hold $\begin{array}{l} Σ_{naive}^{1} \subset Σ_{stage}^{1} \subset Σ_{pref}^{1}, Σ_{cf}^{1} \subset Σ_{adm}^{1} \subset Σ_{com}^{1} \\ {dcl (S) ∣ S \in Σ_{naive}^{1}} = Σ_{cf}^{1}, Σ_{adm}^{1} \supset {S \cup {\emptyset} ∣ S \in Σ_{pref}^{1}} \\ Σ_{adm}^{1} \cap Σ_{pref}^{1} = {{\emptyset}} Σ_{com}^{1} \cap Σ_{pref}^{1} = {{S} ∣ S \subset A, | S | < \infty} \end{array}$

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}^{\infty} = Σ_{grd}^{k} = {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, \emptyset)$ . □

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 $F_{S}^{stb} = ({Args}_{S}, R_{S}^{stb})$ with $R_{S}^{stb} = {(S, a) ∣ S \in S, a \in {Args}_{S} ∖ S}$ .

We first prove the desired result for stable semantics.
Proposition 2.
$Σ_{stb}^{\infty} = {S ∣ S is incomparable}$ .
Proof.
First, as $stb (F) \subseteq pref (F)$ and the latter is incomparable by definition we have that also $stb (F)$ is incomparable for any SETAF F.

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

$stb (F_{S}^{stb}) \supseteq S$ : Consider $S \in S$ . For each $a \in {Args}_{S} ∖ S$ , we have $(S, a) \in R_{S}^{stb}$ by construction. Moreover, as $S$ is incomparable, we cannot have $(S^{'}, a) \in R_{S}^{stb}$ with $S^{'} \subset S$ and $a \in S$ . Hence, S is conflict-free in $F_{S}^{stb}$ and thus $S \in stb (F_{S}^{stb})$ .

$stb (F_{S}^{stb}) \subseteq S$ : Consider $S \subseteq {Args}_{S}$ , such that $S \notin S$ . First, if there is an $E \in S$ such that $E \subset S$ then for each argument $a \in S ∖ E$ we have $(E, a) \in R_{S}^{stb}$ and thus S attacks itself in $F_{S}^{stb}$ . Hence, such an S is not stable. Alternatively, if there is no $E \in S$ such that $E \subseteq S$ then (a) S does not attack any argument and (b) there is an argument $a \in E$ that is not contained in S. Hence, S is not stable in $F_{S}^{stb}$ 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}^{\infty} = {S \neq \emptyset ∣ S is incomparable}$ .
Proof.
First, $pref (F)$ is incomparable and non-empty by definition (for any SETAF F).

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

$pref (F_{S}^{stb}) \supseteq S$ : Consider $S \in S$ . As shown in the proof of Proposition 2, $S \in stb (F_{S}^{stb})$ . By Relation (1), $S \in pref (F_{S}^{stb})$ follows.

$pref (F_{S}^{stb}) \subseteq S$ : Consider $S \subseteq {Args}_{S}$ , such that $S \notin S$ . First, if there is an $E \in S$ such that $E \subset S$ , then there is an argument $a \in S ∖ E$ such that $(E, a) \in R_{S}^{stb}$ and thus S attacks itself in $F_{S}^{stb}$ . Hence, $S \notin pref (F_{S}^{stb})$ . Thus let us consider the case where there is no $E \in S$ such that $E \subseteq S$ . Then S does not attack any argument. Notice that by construction all arguments, except those arguments contained in all sets $S \in S$ (we call them skeptically accepted arguments), are attacked by at least one set $S \in S$ . If S contains an argument that is not skeptically accepted, S cannot be admissible in $F_{S}^{stb}$ 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 $F_{S}^{stb}$ . That is, $S \notin pref (F_{S}^{stb})$ . □

The following theorem summarizes the results we have obtained so far.
Theorem 3.
We have $Σ_{stb}^{\infty} = {S ∣ S is incomparable}$ and $Σ_{pref}^{\infty} = Σ_{stb}^{\infty} ∖ {\emptyset}$ .

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 $F_{S}^{stb}$ yields exactly the framework in our previous examples. Remark 1.
Interestingly $Σ_{stb}^{\infty}$ 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 \subseteq A$ then it holds for each model $S^{'} \subset 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.2

²
We note that for any incomparable extension-set $S$ , $F_{S}^{cf} = F_{S}^{stb}$ .

Definition 11.

Given a non-empty extension-set $S$ , let $F_{S}^{cf} = ({Args}_{S}, R_{S}^{cf})$ be the SETAF with $R_{S}^{cf} = {(S, a) ∣ S \in S, a \in {Args}_{S}, S \cup {a} \in {PAtt}_{S}}$ .

The conflict-free sets of $F_{S}^{cf}$ 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 (F_{S}^{cf}) = dcl (S)$ .

Proof.

Let us show first that $cf (F_{S}^{cf}) \supseteq dcl (S)$ . Pick any $S \in dcl (S)$ and any attack $(S^{'}, a) \in R_{S}^{cf}$ . By construction, we have that $(S^{'} \cup {a}) \in {PAtt}_{S}$ , and thus, $(S^{'} \cup {a}) ⊈ S$ . That is, S is conflict-free in $F_{S}^{cf}$ and therefore $cf (F_{S}^{cf}) \supseteq dcl (S)$ .

Let us show now that $cf (F_{S}^{cf}) \subseteq dcl (S)$ also holds. Pick $S \notin dcl (S)$ , i.e., $S \in {PAtt}_{S}$ , a subset maximal set $S^{'} \in {E \in S ∣ E \subset S}$ , and some argument $a \in S ∖ S^{'}$ . Then, by construction $(S^{'}, a) \in R$ and, thus, S is not conflict-free in $F_{S}^{cf}$ . □

Proposition 4.

$Σ_{cf}^{\infty} = {S \neq \emptyset ∣ 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 (F_{S}^{cf}) = dcl (S)$ and thus also $cf (F_{S}^{cf}) = S$ . □

Proposition 5.

$Σ_{naive}^{\infty} = {S \neq \emptyset ∣ 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 $F_{S}^{cf}$ (see Definition 11). We show that $naive (F_{S}^{cf}) = S$ . By Lemma 8 we have $cf (F_{S}^{cf}) = dcl (S)$ . As $S$ contains exactly the ⊆-maximal elements of $dcl (S)$ and the naive extension of $F_{S}^{cf}$ are the ⊆-maximal elements of $cf (F_{S}^{cf})$ we obtain $naive (F_{S}^{cf}) = S$ . □

The following theorem summarizes the characterizations of this subsection.

Theorem 4.

We have

$Σ_{cf}^{\infty} = {S \neq \emptyset ∣ S is downward-closed}$ and

$Σ_{naive}^{\infty} = {S \neq \emptyset ∣ 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^{'} = {\emptyset, {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 $F_{S^{'}}^{cf}$ as specified in Definition 11, and we have $cf (F_{S^{'}}^{cf}) = S^{'}$ . Also note that for $S = {{a, b}, {b, c}, {a, c}}$ , we have $dcl (S) = S^{'}$ and $naive (F_{S^{'}}^{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}^{\infty} = {S \neq \emptyset ∣ S is incomparable}$ .
Proof.
By Lemma 5, $sem (F) \subseteq pref (F)$ holds for each SETAF F, we have that each $S \in Σ_{sem}^{\infty}$ 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}^{\infty} = {S \neq \emptyset ∣ S is incomparable}$ .
Proof.
By Lemma 6, for each SETAF F, $stage (F) \subseteq naive (F)$ . We thus have that each $S \in Σ_{stage}^{\infty}$ 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}^{\infty} = Σ_{sem}^{\infty} = {S \neq \emptyset ∣ 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 $Σ_{cf}^{1} \subset Σ_{adm}^{1}$ ) $Σ_{adm}^{\infty}$ is not a superset of $Σ_{cf}^{\infty}$ . 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 \cup 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 \in A, b \in B$ .

Definition 12.
A set $S \subseteq 2^{A}$ is called set-conflict-sensitive if for each $T, U \in S$ such that $T \cup U \notin S$ it holds that $\exists u \in U : T \cup {u} \in {PAtt}_{S}$ .

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 \cup 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) \in R$ with $S \subseteq C$ and $a \in C$ .
If $a \in T$ then, as T is conflict-free in F, $B \cap U \neq \emptyset$ . Moreover, as T is admissible in F it has to defend itself against $(B, a)$ , i.e. there is an attack $(T^{'}, u) \in R$ with $T^{'} \subseteq T$ and $u \in B \cap U$ . Hence, we have $T^{'} \cup {u} \in {PAtt}_{adm (F)}$ and thus $T \cup {u} \in {PAtt}_{adm (F)}$ .

If $a \in U$ then, as U is conflict-free in F, $B \cap T \neq \emptyset$ . Moreover, as U is admissible in F it has to defend itself against $(B, a)$ , i.e. there is an attack $(U^{'}, t) \in R$ with $U^{'} \subseteq U$ and $t \in B \cap T$ . Now, as T is admissible in F as well, there is also an attack $(T^{'}, u) \in R$ with $T^{'} \subseteq T$ and $u \in U^{'} \subseteq U$ . Hence, we have $T^{'} \cup {u} \in {PAtt}_{adm (F)}$ and thus $T \cup {u} \in {PAtt}_{adm (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 \subseteq 2^{A}$ is said to be union-closed if $\emptyset \in S$ and each pair $A, B \in S$ satisfies $A \cup B \in S$ . Let us denote by $ucl (S)$ the ⊆-minimal union-closed extension-set such that $S \subseteq ucl (S)$ .
Proposition 8.
Let $S$ be a set-conflict-sensitive extension-set that contains ∅. Then, we have that $S = dcl (S) \cap 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 $\emptyset \in S^{'} \cap S^{″}$ and that $S^{'} \cap S^{″} \supseteq S$ . Hence, it only remains to be shown that $S^{'} \cap S^{″} \subseteq S$ also holds. Suppose for the sake of contradiction that there is some set $C \in (S^{'} \cap S^{″}) ∖ S$ . Since $C \in S^{″} ∖ S$ , by construction, C must be of the form $C = ⋃ T$ for some $T \subseteq S$ . W.l.o.g. we can assume that $| T | = 2$ , i.e., $C = S \cup T$ with $S, T \in S$ . Moreover, since $S$ is set-conflict-sensitive, $C \notin S$ implies that there is some $b \in T$ such that $S \cup {b} \in {PAtt}_{S}$ . Furthermore, since $C \in S^{'}$ , there is also some $S^{'} \in S$ such that $C \subseteq S^{'}$ and, thus, we have $S \cup {b} \subseteq S \cup T \subseteq S^{'}$ which is a contradiction. Hence, it must be that $S^{'} \cap S^{″} \subseteq S$ and $S^{'} \cap S^{″} = S$ hold. □
Proposition 9.
Let $F_{1} = (A_{1}, R_{1})$ and $F_{2} = (A_{2}, R_{2})$ be two SETAFs and let $S \subseteq (A_{1} \cap A_{2})$ be a set of arguments. Then,
S is conflict-free in $F_{1} \cup F_{2} = (A_{1} \cup A_{2}, R_{1} \cup R_{2})$ iff S is conflict-free in both $F_{1}$ and $F_{2}$ ; and

if S is admissible in both $F_{1}$ and $F_{2}$ , then S is admissible in $F_{1} \cup F_{2} = (A_{1} \cup A_{2}, R_{1} \cup R_{2})$ .

Proof.
(1) Consider some $S \notin cf (F_{1} \cup F_{2})$ , i.e., there is an attack $(A, b) \in (R_{1} \cup R_{2})$ with $A \cup {b} \subseteq S$ . Hence, $(A, b) \in R_{i}$ for some $i \in {1, 2}$ and thus $S \notin cf (F_{i})$ . For the reverse direction consider some $S \notin cf (F_{i})$ for some $i \in {1, 2}$ , i.e., there is an attack $(A, b) \in (R_{i})$ with $A \cup {b} \subseteq S$ . Then $(A, b) \in R_{1} \cup R_{2}$ and thus $S \notin cf (F_{1} \cup F_{2})$ .

(2) First, note that if S is admissible in both $F_{1}$ and $F_{2}$ , it is also conflict-free in both $F_{1}$ and $F_{2}$ and, by (1) this implies that S is conflict-free in $F_{1} \cup F_{2}$ . Let us show us that S also defends itself in $F_{1} \cup F_{2}$ . Pick any $b \in S$ and $(A, b) \in (R_{1} \cup R_{2})$ . Hence, $(A, b) \in R_{i}$ for some $i \in {1, 2}$ and, since S is admissible in both $F_{1}$ and $F_{2}$ , it follows that there is a $C \subseteq S$ and $a \in A$ such that $(C, a) \in R_{i}$ . That is, for every argument $b \in S$ and attack $(A, b) \in (R_{1} \cup R_{2})$ , there is some $C \subseteq S$ and $a \in A$ such that $(C, a) \in (R_{1} \cup R_{2})$ . Hence, S is admissible in $F_{1} \cup F_{2}$ . □

The next two lemmas analyze the SETAF $F_{S}^{cf}$ from Definition 11 w.r.t. admissible semantics.
Lemma 10.
Let $S$ be a set-conflict-sensitive extension-set that contains ∅ and $S \subseteq {Args}_{S}$ be some set of arguments such that $S = ⋃ T$ for some subset $T \subseteq S$ . Then, we have that $S \in cf (F_{S}^{cf})$ implies $S \in S$ .
Proof.
Consider such a set $S = ⋃ T$ with $S \in cf (F_{S}^{cf})$ and pick $A \subseteq T$ such that $⋃ A \in S$ and there is no $A^{'} \subseteq T$ such that $A \subset A^{'}$ and $⋃ A^{'} \in S$ . Note that such $A$ always exists because $⋃ \emptyset = \emptyset \in S$ . We also define $A = ⋃ A$ . Towards a contradiction assume that $A \subset T$ and pick any $B \in T ∖ A$ . Then, by construction, we have that $A, B \in S$ and that $(A \cup B) \notin S$ . Furthermore, since $S$ is set-conflict-sensitive, it follows that there is $b \in B$ such that $(A \cup {b}) \in {PAtt}_{S}$ . This implies that there is an attack $(A, b) \in R_{S}^{cf}$ and, thus, $(A \cup {b}) \notin cf (F_{S}^{cf})$ . Finally, since $(A \cup {b}) \subseteq (A \cup B) \subseteq S$ and $cf (F_{S}^{cf})$ is downward-closed, this implies $S \notin cf (F_{S}^{cf})$ which is a contradiction with the assumption that $S \in cf (F_{S}^{cf})$ . Hence, it must be that $A = T$ and, thus, that $A = S$ holds. Since $A \in S$ by construction, this implies $S \in S$ . □
Lemma 11.
Let $S$ be a set-conflict-sensitive extension-set that contains ∅. Then, we have that $S \subseteq adm (F_{S}^{cf})$ .
Proof.
Pick any set $S \in S$ , any argument $a \in S$ and any attack $(S^{'}, a) \in R_{S}^{cf}$ . Then, $(S \cup S^{'}) \notin S$ and, since $S, S^{'} \in S$ and $S$ is conflict-sensitive, it follows that there is some $b \in S^{'}$ such that $(S \cup {b}) \in {PAtt}_{S}$ . This implies that $(S, b) \in R_{S}^{cf}$ and, thus, that S defends a against $(S^{'}, a)$ in $F_{S}^{cf}$ . Hence, S defends itself against all attacks in $R_{S}^{cf}$ . □

Finally, we expand $F_{S}^{cf}$ by additional arguments and attacks that ensure that only sets $S \in S$ are admissible in the resulting SETAF $F_{S}^{adm}$ . In particular, for each argument a we add an argument $x_{a}$ that attacks a and itself, and is only attacked by sets $S \in S$ that contain a.
Definition 14.
Given an extension $S$ set we define $F_{S}^{ucl} = (A_{S}^{ucl}, R_{S}^{ucl})$ with $\begin{array}{l} A_{S}^{ucl} = {Args}_{S} \cup {x_{a} ∣ a \in {Args}_{S}} and \\ R_{S}^{ucl} = {({x_{a}}, a) ∣ a \in {Args}_{S}} \cup {({x_{a}}, x_{a}) ∣ a \in {Args}_{S}} \cup {(S, x_{a}) ∣ S \in S and a \in S} . \end{array}$ We then define $F_{S}^{adm} = (A_{S}^{adm}, R_{S}^{adm}) = (F_{S}^{cf} \cup F_{S}^{ucl})$ .

We next illustrate the construction on an example
Example 5.
Consider the extension-set $S = {\emptyset, {a, b}, {a, c}}$ . We have ${Args}_{S} = {a, b, c}$ and we add three additional arguments ${x_{a}, x_{b}, x_{c}}$ , one for each of the existing arguments. That is, $A_{S}^{adm} = {a, b, c, x_{a}, x_{b}, x_{c}}$ . 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 $R_{S}^{cf} = {({a, b}, c), ({a, c}, b)}$ . Now we have $adm ({Args}_{S}, R_{S}^{cf}) = {\emptyset, {a}, {a, b}, {a, c}}$ , that is we still have the unwanted extension ${a}$ . We now use the additional arguments ${x_{a}, x_{b}, x_{c}}$ to avoid such extensions. The arguments $x_{i}$ are self-attacking, i.e. we have attacks ${({x_{a}}, x_{a}), ({x_{b}}, x_{b}), ({x_{c}}, x_{c})}$ in $R_{S}^{ucl}$ , and attack their corresponding argument i, i.e. we have attacks ${({x_{a}}, a), ({x_{b}}, b), ({x_{c}}, c)}$ in $R_{S}^{ucl}$ , and are only attacked by those sets $S \in S$ that contain i, i.e. we have attacks ${({a, b}, x_{a}), ({a, b}, x_{b}), ({a, c}, x_{a}), ({a, c}, x_{c})}$ in $R_{S}^{ucl}$ . That is, $R_{S}^{adm} = {({x_{a}}, x_{a}), ({x_{b}}, x_{b}), ({x_{c}}, x_{c}), ({x_{a}}, a), ({x_{b}}, b), ({x_{c}}, c), ({a, b}, c), ({a, b}, x_{a})$ , $({a, b}, x_{b}), ({a, c}, b), {a, c}, x_{a}), ({a, c}, x_{c})$ and we have $adm (A_{S}^{adm}, R_{S}^{adm}) = {\emptyset, {a, b}, {a, c}}$ as now ${a}$ does not defend it self against the attack $({x_{a}}, a)$ .

With the following lemma we show that $F_{S}^{ucl}$ can realize $ucl (S)$ .
Lemma 12.
For every extension-set $S$ that is set-conflict-sensitive and contains ∅, we have that $ucl (S) \subseteq adm (F_{S}^{ucl})$ .
Proof.
Let us first show that $S \subseteq adm (F^{ucl})$ . Pick any $A \in S$ , $a \in A$ and $(S, a) \in R_{S}^{ucl}$ . Then, by construction, we have that $S = {x_{a}}$ and, since $a \in A$ , that $(A, x_{a}) \in R_{S}^{ucl}$ , so A also defends itself against all attacks in $R_{S}^{ucl}$ . Hence, we have that $S \subseteq adm (F_{S}^{ucl})$ . Pick now $A, B \in S$ . We already know that $A, B \in adm (F_{S}^{ucl})$ and, moreover, $A \cup B$ defends itself in $F_{S}^{ucl}$ (Lemma 2). Furthermore, by construction, there are no attacks between elements of $A \cup B$ and thus $A \cup B \in adm (F_{S}^{ucl})$ . □

It remains to combine the results for the SETAFs $F_{S}^{cf}$ , $F_{S}^{ucl}$ 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 (F_{S}^{adm}) = S$ .
Proof.
From Proposition 8, we have that $S = dcl (S) \cap ucl (S)$ . Then, from Lemmas 11 and 12, we get that $S \subseteq adm (F_{S}^{cf}) \cap adm (F_{S}^{ucl})$ . Furthermore, from Proposition 9, this implies that $S \subseteq adm (F_{S}^{adm})$ .

Let us show that $adm (F_{S}^{adm}) \subseteq S$ also holds. Pick any $A \in adm (F_{S}^{adm})$ . Then, for every argument $a \in A$ , there is an attack $({x_{a}}, a) \in R_{S}^{adm}$ by construction, and so there must be an attack $(T_{a}, {x_{a}}) \in R_{S}^{adm}$ with $T_{a} \subseteq A$ . Furthermore, by construction, we also have that $T_{a} \in S$ and $a \in T_{a}$ . Let $T = {T_{a} \subseteq A ∣ a \in A} \subseteq S$ and $C = ⋃ T$ . Then, we have that $C = A$ and, from Lemma 10 and the fact that $A \in adm (F_{S}^{adm}) \subseteq cf (F_{S}^{adm}) \subseteq cf (F_{S}^{cf})$ , it follows that, $A \in S$ . □

Now we can give an exact characterization of $Σ_{adm}^{\infty}$ .
Theorem 6.
$Σ_{adm}^{\infty} = {S \neq \emptyset ∣ S is set-conflict-sensitive and contains \emptyset}$ .

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 = {\emptyset, {a, b}, {b, c}, {a, c}}$ . As ${a, b, c} \notin S$ but ${a, b}, {b, c} \in S$ (and thus neither ${a, c} \in {PAtt}_{S}$ nor ${b, c} \in {PAtt}_{S}$ ), 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} \in {PAtt}_{S}$ . Indeed, one can verify that our running example SETAF F satisfies $adm (F) = S$ .

On the other hand, the set $S^{'} = {\emptyset, {a}, {b}, {c}, {a, b}, {b, c}, {a, c}} \in Σ_{cf}^{\infty}$ from Example 4 is not set-conflict-sensitive. Take $A = {a}$ and $B = {b, c}$ . Then $A \cup B \notin S^{'}$ but neither ${a, b} \in {PAtt}_{S^{'}}$ nor ${a, c} \in {PAtt}_{S^{'}}$ . 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) \cap ucl (S)$ is a necessary, but not a sufficient condition. Indeed, in our example we have $dcl (S^{'}) = S$ , $ucl (S^{'}) = S^{'} \cup {{a, b, c}}$ and $S^{'} = dcl (S^{'}) \cap ucl (S^{'})$ .

3.5. Signature of complete semantics

Finally, we consider the signature of complete semantics. First, recall that the completion-sets $C_{S} (E)$ of a set $E \subseteq {Args}_{S}$ in $S$ are the ⊆-minimal sets $S \in S$ with $E \subseteq 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 \subseteq 2^{A}$ is called set-com-closed iff, for each $T, U \subseteq S$ with $T = {Args}_{T}$ , $U = {Args}_{U}$ ,
$| C_{S} (T \cup U) | ⩽ 1$ , and

if $T, U \in dcl (S)$ and $| C_{S} (T \cup U) | = 0$ , then there is an argument $u \in U$ such that $T \cup {u} \in {PAtt}_{S}$ .

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) \in 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 \subseteq com (F)$ and sets $T = ⋃ T$ , $U = ⋃ U$ such that $T, U \in dcl (com (F))$ . From $T, U \in dcl (com (F))$ , it follows that $T, U \in cf (F)$ and from $T = ⋃ T$ , $U = ⋃ U$ with $T, U \subseteq com (F)$ it follows that T and U defend themselves. Hence, we get $T, U \in adm (F)$ . If in addition we have $T \cup U \in cf (F)$ , then by Lemma 2 we have that $T \cup U \in adm (F)$ and thus by Lemma 1 there is a unique ⊆-minimal complete extension $E \in com (F)$ with $T \cup U \subseteq E$ , i.e. $| C_{com (F)} (T \cup U) | = 1$ . If $T \cup U \notin cf (F)$ then there exists an attack $(S, a) \in R$ with $S \subseteq T \cup U$ and $a \in T \cup U$ .
If $a \in T$ , as T is admissible, there is an attack $(T^{'}, u)$ with $T^{'} \subseteq T$ and $u \in S ∖ T \subseteq U$ . Thus, $T \cup {u} \in {PAtt}_{com (F)}$ .

If $a \in U$ , as U is admissible, there is an attack $(U^{'}, s)$ with $U^{'} \subseteq U$ and $s \in S ∖ U \subseteq T$ . Now, as T is admissible, there is an attack $(T^{'}, u)$ with $T^{'} \subseteq T$ and $u \in U^{'} \subseteq U$ . Thus $T \cup {u} \in {PAtt}_{com (F)}$ .
In both cases we have an $u \in U$ such that $T \cup {u} \in {PAtt}_{com (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 \in S}$ , we denote a reduced extension-set whose corresponding ground extension is empty. Let $S^{'} = reduced (S)$ . We then realize $S^{} = dcl (S^{'}) \cap ucl (S^{'}) = {⋃ T ∣ T \subseteq S^{'}, ⋃ T \in dcl (S^{'})}$ and add further attacks such that each set $E \in S^{}$ defends all arguments of the unique set in $C_{S} (E)$ . In the following we use $C_{S} (E)$ to denote the unique element of $C_{S} (E)$ iff $| C_{S} (E) | = 1$ and the empty set otherwise.
Definition 16.
Given an extension-set $S$ , let $S^{'} = reduced (S)$ and $S^{} = dcl (S^{'}) \cap ucl (S^{'})$ . Then, by $F_{S}^{com} = ({Args}_{S} \cup A_{S^{}}^{adm}, R_{S}^{com})$ we denote a SETAF with $R_{S}^{com} = R_{S^{}}^{adm} \cup R^{'}$ and where $R^{'} = {(A \cup B, x_{a}) ∣ A, B \in S^{'} ∖ {\emptyset}, a \in C_{S^{'}} (A \cup 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) = {\emptyset, {a}, {b}, {a, b, c}}$ as well as $S^{} = {\emptyset, {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 $A_{S^{}}^{adm} = {a, b, c, x_{a}, x_{b}, x_{c}}$ and attacks $R_{S^{}}^{adm} = {({x_{a}}, x_{a}), ({x_{a}}, a), ({x_{b}}, x_{b}), ({x_{b}}, b), ({x_{c}}, x_{c}), ({x_{c}}, c)} \cup {({a}, x_{a}), ({b}, x_{b}), ({a, b}, x_{a})$ , $({a, b}, x_{b}), ({a, b, c}, x_{a}), ({a, b, c}, x_{b}), ({a, b, c}, x_{c})}$ . We now have that $adm (A_{S^{}}^{adm}, R_{S^{}}^{adm}) = S^{}$ . The only attack added by $R^{'}$ is $({a, b}, x_{c})$ , which ensures that ${a, b}$ is not complete as it defends c. Thus we have $com (A_{S^{}}^{adm}, R_{S^{}}^{adm} \cup R^{'}) = S^{'}$ . Finally we also add the argument d to the SETAF (without any attacks) and obtain that $F_{S}^{com} = ({a, b, c, d, x_{a}, x_{b}, x_{c}}, {({x_{a}}, x_{a}), ({x_{a}}, a), ({x_{b}}, x_{b}), ({x_{b}}, b), ({x_{c}}, x_{c})$ , $({x_{c}}, c), ({a}, x_{a}), ({b}, x_{b})$ , $({a, b}, x_{a}), ({a, b}, x_{b}), ({a, b, c}, x_{a}), ({a, b, c}, x_{b})$ , $({a, b, c}, x_{c})}, ({a, b}, x_{c}))}$ and $com (F_{S}^{com}) = S$ . Finally, by removing redundant attacks, i.e. attacks $(S, a)$ such that there is an attack $(S^{'}, a)$ with $S^{'} \subset S$ , the attack relation of $F_{S}^{com}$ simplifies to ${({x_{a}}, x_{a}), ({x_{a}}, a), ({x_{b}}, x_{b}), ({x_{b}}, b), ({x_{c}}, x_{c}), ({x_{c}}, c)$ , $({a}, x_{a}), ({b}, x_{b}), ({a, b}, x_{c}))}$ .

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 \in S$ , we have that $com (F_{S}^{com}) = S$ .
Proof.
Consider the SETAF $F_{S}^{com}$ from Definition 16. Let $S^{'} = reduced (S)$ , $S^{} = dcl (S^{'}) \cap ucl (S^{'})$ and let us show first that $com (F_{S^{'}}^{com}) = S^{'}$ . Notice that $S^{'}$ is still set-com-closed and $\emptyset \in S^{'}$ .

In order to apply the construction for admissible semantics on $S^{}$ we next show that $S^{}$ is set-conflict-sensitive. Consider $T, U \in S^{}$ such that $T \cup U \notin S^{}$ . Then, by construction of $S^{}$ , we have that $T \cup U \notin dcl (S^{'})$ and thus $C_{com (F)} (T \cup U) = \emptyset$ . Now as $S^{'}$ is set-com-closed there is an argument $u \in U$ such that $T \cup {u} \in {PAtt}_{S}$ . That is, for $T, U \in S^{}$ such that $T \cup U \notin S^{}$ there is an argument $u \in U$ such that $T \cup {u} \in {PAtt}_{S}$ . Hence, the extension-set $S^{}$ is set-conflict-sensitive and, from Lemma 13, it follows that $adm (F_{S^{}}^{adm}) = S^{}$ .

Now consider the new attacks in $R^{'}$ and how they affect the admissibility of sets. Notice that only auxiliary arguments $x_{a}$ are attacked and thus each set that is admissible in $F_{S^{}}^{adm}$ is admissible in $F_{S^{'}}^{com}$ as well (Proposition 9, condition (2)). That is, we have $adm (F_{S^{}}^{adm}) \subseteq adm (F_{S^{'}}^{com})$ . Let us show $S^{'} \subseteq com (F_{S^{'}}^{com})$ . Consider $S \in S^{'} \subseteq S^{}$ . By the above, we have that $S \in adm (F_{S^{}}^{adm})$ and it remains to be shown that S does not defend any $a \in {Args}_{S} ∖ S$ , i.e., does not attack any $x_{a}$ for $a \in {Args}_{S} ∖ S$ . By construction of $F_{S^{'}}^{com}$ the set S only attacks arguments $x_{a}$ with $a \in S$ and thus $S \in com (F_{S^{'}}^{com})$ follows. The other way around, let us show $S^{'} \supseteq com (F_{S^{'}}^{com})$ . Consider $S \in adm (F_{S^{'}}^{com})$ . We next show that if $S \notin S^{'}$ then $S \notin com (F_{S^{'}}^{com})$ . To this end we consider two cases.
$S \in adm (F_{S^{'}}^{com}) ∖ S^{}$ : Notice that $S^{} = adm (F_{S^{}}^{adm})$ . Consider a set S that is admissible in $F_{S^{'}}^{com}$ but not in $F_{S^{}}^{adm}$ . This can only be because of the attacks introduced with $R^{'}$ . That is, there is some $x_{s}$ with $s \in S$ that prevents that S is admissible in $F_{S^{}}^{adm}$ and an attack $(A \cup B, x_{s}) \in R^{'}$ with which S defends itself against $x_{s}$ in $F_{S^{'}}^{com}$ . That is $A, B \subseteq S$ and, by the definition of $R^{'}$ , we have that there is a unique completion $C = C_{S^{'}} (A \cup B)$ and $s \in C$ (recall that in $R^{'}$ we only draw attacks for $A \cup B$ with a unique completion). As $C \in S^{'} \subseteq S^{}$ and $s \in C$ , by construction, there is an attack $(C, x_{s})$ in $F_{S^{}}^{adm}$ That is, if $C \subseteq S$ then S attacks $x_{s}$ in $F_{S^{}}^{adm}$ , a contradiction to our initial assumption. Hence we have $C ⊈ S$ . Now we can argue that in $F_{S^{'}}^{com}$ , S defends all arguments in C and thus S is not complete. To this end let $c \in C ∖ S$ . By construction $A \cup B$ (and thus S) attacks all $x_{a}$ with $a \in C$ . Now consider a set $D \in S^{}$ that attacks c. As C is admissible in $F_{S^{}}^{adm}$ , we have that there is a $d \in D$ such that $(C, d) \in R_{S^{}}^{adm}$ . By construction we have $C \cup {d} \in PAtt (S^{})$ and thus also $A \cup B \cup {d} \in PAtt (S^{})$ . As $A \cup B \in S^{}$ , we then by construction have $(A \cup B, d) \in R_{S^{}}^{adm}$ . That is $A \cup B$ defends c against both possible kinds of attackers and thus defends c.

$S \in S^{} ∖ S^{'}$ : Then, there is a set $T \subseteq S^{'}$ such that $⋃ T = S$ and $S \in dcl (S^{'})$ . As $S^{'}$ is set-com-closed for each $A, B \in S^{'}$ with $A, B \subseteq S$ , we have a unique completion set $C_{S^{'}} (A \cup B)$ (as $A \cup B \in dcl (S^{'})$ we cannot have a conflict in $A \cup B$ . Towards a contradiction assume that for all $A, B \in S^{'}$ such that $A, B \subseteq S$ we have $C_{S^{'}} (A \cup B) \subseteq S$ . Then we can iteratively replace $A, B \in T$ by $C_{S^{'}} (A \cup B)$ and we end up with a single set in $T$ . But then $S \in S^{'}$ , a contradiction. Thus there are two sets $A, B \in S^{'}$ such that $A, B \subseteq S$ and $A \cup B \notin S^{'}$ , and there is also a unique set $C \in C_{S^{'}} (A \cup B)$ with $C ⊈ S$ . Let $c \in C ∖ S$ , we next argue the S defends c and thus is not complete. By construction $A \cup B$ (and thus S) attacks all $x_{a}$ with $a \in C$ . Now consider a set $D \in S^{}$ that attacks c. As C is admissible in $F_{S^{}}^{adm}$ we have that there is a $d \in D$ such that $(C, d) \in R_{S^{}}^{adm}$ . By construction we have $C \cup {d} \in PAtt (S^{})$ and thus also $A \cup B \cup {d} \in PAtt (S^{})$ . As $A \cup B \in S^{}$ , by construction we have $(A \cup B, d) \in R_{S^{}}^{adm}$ . That is $A \cup B$ defends c against both possible kinds of attackers and thus defends c.
Combining both cases we obtain that if $S \notin S^{'}$ then $S \notin com (F_{S^{'}}^{com})$ . Finally, just note that $F_{S}^{com}$ just adds to $F_{S^{'}}^{com}$ the arguments in $⋂ S$ as unattacked. Hence, $S \in com (F_{S}^{com})$ iff $(S ∖ ⋂ S) \in com (F_{S^{'}}^{com})$ and, thus, $com (F_{S}^{com}) = S$ . □

This now gives a complete characterization of the signature for complete semantics.
Theorem 7.
$Σ_{com}^{\infty} = {S \neq \emptyset ∣ S is set-com-closed and ⋂ S \in S}$ .

Notice that when considering AFs not all extension-sets that are com-closed and satisfy $⋂ S \in 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 = {\emptyset, {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 \cup U$ of sets with $T = {Args}_{T}$ and $U = {Args}_{U}$ with $T, U \subseteq S$ . The first condition of $S$ being set-com-closed is verified as follows.
Whenever $T \cup U \in S$ we have $| C_{S} (T \cup U) | = 1$ by the definition of $C_{S}$ .

Whenever $T \cup U \notin dcl S$ then $| C_{S} (T \cup U) | = 0$ by the definition of $C_{S}$ .

It only remains to consider $T, U \in {{a}, {b}, {c}}$ with $T \neq U$ we have that $C_{S} ({a, b}) = C_{S} ({a, c}) = C_{S} ({b, c}) = {{a, b, c}}$ , i.e. $| C_{S} (T \cup U) | = 1$ .
For the second condition we are interested in the choices of $T, U$ where $T, U \in dcl (S)$ , i.e. we have $T, U \in S \cup {{a, b}, {a, c}, {b, c}}$ . We have to show that whenever $T \cup U \notin dcl (S)$ then $T \cup {u} \in {PAtt}_{S}$ for some $u \in U$ .
Consider $T = {a}$ , then for $U = {b, d, f}$ we have ${a, f} \in {PAtt}_{S}$ , and for $U \in {{x, c}, {x, d}}$ we have ${a, x} \in {PAtt}_{S}$ .

Consider $T = {b}$ , then for $U = {a, d, e}$ we have ${b, e} \in {PAtt}_{S}$ , for $U \in {{x, c}, {x, d}}$ we have ${b, x} \in {PAtt}_{S}$ .

Consider $T = {c}$ , then for $U \in {{a, d, e}, {b, d, f}}$ we have ${c, d} \in {PAtt}_{S}$ , and for $U = {x, d}$ we have ${c, d} \in {PAtt}_{S}$ .

Consider $T = {a, b}$ , then for $U = {a, d, e}$ we have ${a, b, e} \in {PAtt}_{S}$ for $U = {b, d, f}$ we have ${a, b, f} \in {PAtt}_{S}$ ,and for $U \in {{x, c}, {x, d}}$ we have ${a, b, x} \in {PAtt}_{S}$ .

Consider $T = {a, c}$ , then for $U = {a, d, e}$ we have ${a, c, d} \in {PAtt}_{S}$ , for $U = {b, d, f}$ we have ${a, c, f} \in {PAtt}_{S}$ , and for $U \in {{x, c}, {x, d}}$ we have ${a, c, x} \in {PAtt}_{S}$ .

Consider $T = {b, c}$ , then for $U = {a, d, e}$ we have ${b, c, e} \in {PAtt}_{S}$ , for $U = {b, d, f}$ we have ${b, c, d} \in {PAtt}_{S}$ , for $U \in {{x, c}, {x, d}}$ we have ${b, c, x} \in {PAtt}_{S}$ .

Consider $T = {a, b, c}$ , then for $U = {a, d, e}$ we have ${a, b, c, e} \in {PAtt}_{S}$ , for $U = {b, d, f}$ we have ${a, b, c, d} \in {PAtt}_{S}$ , for $U \in {{x, c}, {x, d}}$ we have ${a, b, c, x} \in {PAtt}_{S}$ .

Consider $T = {a, d, e}$ , then for $U \in {{b}, {a, b}, {b, c}, {a, b, c}, {b, d, f}}$ we have ${a, d, e, b} \in {PAtt}_{S}$ , for $U \in {{c}, {a, c}, {x, c}}$ we have ${a, d, e, c} \in {PAtt}_{S}$ , and for $U = {x, d}$ we have ${a, d, e, x} \in {PAtt}_{S}$ .

Consider $T = {b, d, f}$ , then for $U \in {{a}, {a, b}, {a, c}, {a, b, c}, {a, d, e}}$ we have ${b, d, f, a} \in {PAtt}_{S}$ , for $U \in {{c}, {b, c}, {x, c}}$ we have ${b, d, f, c} \in {PAtt}_{S}$ , and for $U = {x, d}$ we have ${b, d, f, x} \in {PAtt}_{S}$ .

Consider $T = {x, c}$ , then for $U \in {{a}, {a, b}, {a, c}, {a, b, c}, {a, d, e}}$ we have ${x, c, a} \in {PAtt}_{S}$ , for $U \in {{b}, {b, c}, {b, d, f}}$ we have ${x, c, b} \in {PAtt}_{S}$ , and for $U = {x, d}$ we have ${x, c, d} \in {PAtt}_{S}$ .

Consider $T = {x, d}$ , then for $U \in {{a}, {a, b}, {a, c}, {a, b, c}, {a, d, e}}$ we have ${x, d, a} \in {PAtt}_{S}$ , for $U \in {{b}, {b, c}, {b, d, f}}$ we have ${x, d, b} \in {PAtt}_{S}$ , and for $U \in {{c}, {x, c}}$ we have ${x, d, c} \in {PAtt}_{S}$ .
This shows that $S$ is set-com-closed and thus $com (F_{S}^{com}) = 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: $\begin{array}{l} Σ_{cf}^{\infty} = {S \neq \emptyset ∣ S is downward-closed} \\ Σ_{naive}^{\infty} = {S \neq \emptyset ∣ S is incomparable} \\ Σ_{stb}^{\infty} = {S ∣ S is incomparable} \\ Σ_{adm}^{\infty} = {S \neq \emptyset ∣ S is set-conflict-sensitive and contains \emptyset} \\ Σ_{pref}^{\infty} = {S \neq \emptyset ∣ S is incomparable} \\ Σ_{com}^{\infty} = {S \neq \emptyset ∣ S is set-com-closed and ⋂ S \in S} \\ Σ_{sem}^{\infty} = {S \neq \emptyset ∣ S is incomparable} \\ Σ_{stage}^{\infty} = {S \neq \emptyset ∣ S is incomparable} \end{array}$

Let us now consider the relations between the signatures of the different semantics. First for the semantics possessing incomparable extension-sets we have $\begin{matrix} Σ_{naive}^{\infty} = Σ_{stb}^{\infty} ∖ {\emptyset} = Σ_{pref}^{\infty} = Σ_{sem}^{\infty} = Σ_{stage}^{\infty} . \end{matrix}$ 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}^{\infty} \subseteq Σ_{com}^{\infty}$ .
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 \subseteq S$ , $T = {Args}_{T}$ and $U = {Args}_{U}$ 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. $| C_{S} (T \cup U) | ⩾ 2$ . Then we have that $T \cup U \in dcl (S)$ and thus, as $S$ is set-conflict-sensitive, $T \cup U \in S$ . The latter implies that $C_{S} (T \cup U) = {T \cup U}$ which is in contradiction to $| C_{S} (T \cup U) | ⩾ 2$ . Let us now assume that condition (2) is violated, i.e. $T, U \in dcl (S)$ , $| C_{S} (T \cup U) | = 0$ , and there is no argument $u \in U$ such that $T \cup {u} \in {PAtt}_{S}$ . As $T, U \in dcl (S)$ and $S$ is set-conflict-sensitive, we have that $T, U \in S$ . Moreover, as $| C_{S} (T \cup U) | = 0$ we have $T \cup U \notin S$ , and thus, as $S$ is set-conflict-sensitive, there is a $b \in U : T \cup {b} \in {PAtt}_{S}$ , a contradiction to our initial assumption. □

Next, we give an example of an extension-set $S \in Σ_{com}^{\infty}$ but $S \notin Σ_{adm}^{\infty}$ and thus show $Σ_{adm}^{\infty} \subset Σ_{com}^{\infty}$ .
Example 9.
Consider the extension-set $S = {\emptyset, {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} \notin S$ . However, $S$ can be easily verified to be set-com-closed (as $| C_{S} ({a, b}) | = 1$ ) and thus $S \in Σ_{com}^{\infty}$ .

In contrast to Dung AFs we have that $Σ_{cf}^{\infty} ⊈ Σ_{adm}^{\infty}$ as we have already seen in Example 6. We next continue this example to show that also $Σ_{cf}^{\infty} ⊈ Σ_{com}^{\infty}$ .
Example 10.
Reconsider the extension-set $S^{'} = {\emptyset, {a}, {b}, {c}, {a, b}, {b, c}, {a, c}} \in Σ_{cf}^{\infty}$ from Example 6, which is not set-com-closed. Take $T = {a}$ and $U = {b, c}$ . Then $T \cup U \notin dcl (S^{'})$ and thus $| C_{S} (T \cup U) | = 0$ , but neither ${a, b} \in {PAtt}_{S^{'}}$ nor ${a, c} \in {PAtt}_{S^{'}}$ . Hence, by Theorem 7, there is no SETAF F with $com (F) = S^{'}$ .

Likewise, $Σ_{cf}^{\infty} ⊉ Σ_{adm}^{\infty}$ is easy to see. In Example 6, we have argued that $S = {\emptyset, {a, b}, {a, c}, {b, c}} \in Σ_{adm}^{\infty}$ , but since $S$ is not downward-closed, $S \notin Σ_{cf}^{\infty}$ . By Proposition 10, $Σ_{cf}^{\infty} ⊉ Σ_{com}^{\infty}$ 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}^{\infty} \cap Σ_{com}^{\infty} \subseteq Σ_{adm}^{\infty}$ .
Proof.
Consider $S \in Σ_{cf}^{\infty} \cap Σ_{com}^{\infty}$ , 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 \in S$ such that $A \cup B \notin S$ and there is no $b \in B$ such that $A \cup {b} \in {PAtt}_{S}$ . As $S$ is downward-closed there is no $C \in S$ with $A \cup B \subseteq C$ and thus $| C_{S} ({a, b}) | = 0$ . Now as $S$ is set-com-closed there is an argument $b \in B$ such that $A \cup {b} \in {PAtt}_{S}$ , 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).
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 $\begin{matrix} {PAtt}_{S}^{k} = {S \subseteq {Args}_{S} ∣ | S | ⩽ k + 1 and S \notin dcl (S)} . \end{matrix}$
Example 11.
Let $S = {{a, b}, {a, c}, {b, c}}$ and $S^{'} = {{a}, {b}, {c}}$ . Then, we have ${PAtt}_{S}^{1} = \emptyset$ while ${PAtt}_{S^{'}}^{1} = {{a, b}, {a, c}, {b, c}}$ . Note that elements of ${PAtt}_{S^{'}}^{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 ${PAtt}_{S}^{k} = {{a, b, c}}$ , and ${PAtt}_{S^{'}}^{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 \subseteq 2^{A}$ is k-tight if for all $S \in S$ and $a \in {Args}_{S}$ it holds that if $S \cup {a} \notin S$ then there exists a set $S^{'} \subseteq S$ , such that $S^{'} \cup {a} \in {PAtt}_{S}^{k}$ .

Indeed, for $k = 1$ the notion of k-tight corresponds to the notion of tight on Dung AFs (see Definition 9) while for $k ⩾ {Args}_{S}$ the notion of k-tight simplifies to: for all $S \in S$ and $a \in {Args}_{S}$ either $S \cup {a} \in S$ or there is no $S^{'} \in S$ with $S \cup {a} \subseteq 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 \cup {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 $F_{S}^{cf, k} = ({Args}_{S}, R_{S}^{cf, k})$ be the k-SETAF with $R_{S}^{cf, k} = {(S, a) ∣ | S | ⩽ k, a \in {Args}_{S}, S \cup {a} \in {PAtt}_{S}^{k}}$ .

Note that, for given $k ⩾ 1$ , $F_{S}^{cf, 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 (F_{S}^{cf, k}) = S$ .
Proposition 12.
$Σ_{cf}^{k} = {S \neq \emptyset ∣ 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 \in 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 \cup {a} \notin cf (F)$ . Then $S \cup {a}$ attacks $S \cup {a}$ , that is either there is a set $S^{'} \subseteq S \cup {a}$ with $(S^{'}, a) \in R$ or there is a set $E \subseteq S \cup {a}$ with $a \in E$ and $(E, b) \in R$ for some $b \in S$ . In the former case $S^{'} \cup {a}$ is of size $⩽ k + 1$ and $S^{'} \cup {a} \notin dcl (cf (F))$ . In the latter case consider $S^{'} = (E ∖ {a}) \cup {b}$ which is of size $⩽ k$ (since $(E, b) \in R$ ) and $S^{'} \cup {a} = E \cup {b} \notin dcl (cf (F))$ . In both cases we have $S^{'} \cup {a} \in {PAtt}_{cf (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 $F_{S}^{cf, k}$ from Definition 19. We prove that $cf (F_{S}^{cf, k}) = S$ .

1) Let us show first that $cf (F_{S}^{cf, k}) \supseteq S$ . Pick any $S \in S$ and any attack $(S^{'}, a) \in R$ with $S^{'} \subseteq S$ . By construction, we have that $(S^{'} \cup {a}) \notin dcl (S)$ and, thus, that $(S^{'} \cup {a}) ⊈ S$ . Hence, since $S^{'} \subseteq S$ , it follows that $a \notin S$ and that S is conflict-free. Hence, we have that $cf (F_{S}^{cf, k}) \supseteq S$ .

2) To show $cf (F_{S}^{cf, k}) \subseteq S$ , pick $S \subseteq {Args}_{S}$ with $S \notin S$ . As $S$ is downward-closed we have that there is an $S^{'} \in S$ such that $S^{'} \subseteq S$ , and w.l.o.g. assume that $S^{'}$ is a maximal such set. Pick $a \in S ∖ S^{'}$ . As $S$ is k-tight there is an attack $(B, a) \in R$ for some $B \subseteq S^{'}$ and thus $S \notin cf (F_{S}^{cf, k})$ . □

Next we show that for each $S$ that is incomparable and whose downward-closure is k-tight we have that $naive (F_{S}^{cf, k}) = S$ .
Proposition 13.
$Σ_{naive}^{k} = {S \neq \emptyset ∣ 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
$Σ_{cf}^{k} = {S \neq \emptyset ∣ S is downward-closed and k -tight}$ and

$Σ_{naive}^{k} = {S \neq \emptyset ∣ 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 = {a_{1}, a_{2}, \dots, a_{k + 1}, a_{k + 2}}$ and the extension-sets $S = {S \subseteq A ∣ | S | ⩽ k + 1}$ and $T = {S \subseteq A ∣ | S | = k + 1}$ . We have that $S$ is not k-tight, as $A \notin S$ , but for $S = {a_{1}, a_{2}, \dots, a_{k + 1}}$ we have that every $S^{'} \subset {a_{1}, a_{2}, \dots, a_{k + 1}}$ satisfies $S^{'} \cup {a_{k + 2}} \in S$ and thus $S^{'} \cup {a_{k + 2}} \notin {PAtt}_{S}^{k}$ . Note that $S \cup {a_{k + 2}} \notin {PAtt}_{S}^{k}$ because $| S \cup {a_{k + 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 $F_{S}^{cf, k}$ from Definition 19 by arguments $x_{s}$ that eliminate unwanted naive extensions of $F_{S}^{cf, k}$ .

Definition 20.
Given an extension-set $S$ that is incomparable and k-tight, we construct the k-SETAF $F_{S}^{stb, k} = (A, R)$ based on $F_{S}^{cf, k} = ({Args}_{S}, R_{S}^{cf, k})$ as follows: $\begin{array}{l} A = {Args}_{S} \cup {x_{S} ∣ S \in naive (F_{S}^{cf, k}) ∖ S} \\ R = R_{S}^{cf, k} \cup ⋃_{S \in naive (F_{S}^{cf, k}) ∖ S} {({a}, x_{S}), ({x_{S}}, x_{S}) ∣ a \in {Args}_{S} ∖ S} \end{array}$

One can show that for each $S$ that is incomparable and k-tight we have that $stb (F_{S}^{stb, k}) = S$ by building on Theorem 8 and using similar arguments as in [7, Prop. 7].
Theorem 9.
$Σ_{stb}^{k} = {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) \subseteq pref (F)$ , it is clear that $stb (F)$ is incomparable. Now consider $E \in stb (F)$ . By definition for each argument $a \notin E$ there is an attack $(B, a)$ with $| B | ⩽ k$ . That is there is no $E^{'} \in stb (F)$ with $B \cup {a} \subseteq E^{'}$ and thus $B \cup {a} \in {PAtt}_{stb (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 $F_{S}^{stb, k} = (A, R)$ from Definition 20. We show that $stb (F_{S}^{stb, k}) = S$ .

1) Let us show first that $stb (F_{S}^{stb, k}) \supseteq S$ . Pick any $S \in S$ and any attack $(S^{'}, a) \in R$ with $S^{'} \subseteq S$ . By construction, we have that $(S^{'} \cup {a}) \in {PAtt}_{S}^{k}$ and, thus, that $(S^{'} \cup {a}) ⊈ S$ . Now consider $a \in {Args}_{S} ∖ S$ . As $S$ is k-tight there exists $B \subseteq S, | B | ⩽ k$ such that $B \cup {a} \in {PAtt}_{S}^{k}$ and thus $(B, a) \in R$ . Finally, consider $x_{E} \in {x_{S} ∣ S \notin S and S \subseteq -maximal in dcl (S)}$ . We have that S and E are incomparable and thus there is an argument $a \in E$ such that $({a}, x_{E}) \in R$ . That is, $S \in stb (F_{S}^{stb, k})$ .

2) It remains to show $stb (F_{S}^{stb, k}) \subseteq S$ . Let $S \subseteq {Args}_{S}$ with $S \notin S$ . If $S \notin naive (F_{S}^{stb, k})$ then it is not stable in $F_{S}^{stb, k}$ . Thus assume $S \in naive (F_{S}^{stb, k})$ . Observe that $naive (F_{S}^{stb, k}) = naive (F_{S}^{cf, k})$ . By construction, there is an argument $x_{S} \in A$ with $x_{S} \notin S$ and S not attacking $x_{S}$ . Thus, $S \notin stb (F_{S}^{stb, k})$ . □

The above theorem gives a strict hierarchy of signatures $Σ_{stb}^{k}$ which is illustrated in the following example.
Example 13.
Consider the argument set $A = {a_{1}, a_{2}, \dots, a_{k + 1}, a_{k + 2}}$ and the extension-set $T = {S \subseteq 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 \notin T$ , but for ${a_{1}, a_{2}, \dots, a_{k + 1}} \in T$ we have that any $S \subset {a_{1}, a_{2}, \dots, a_{k + 1}}$ satisfies $S \cup {a_{k + 2}} \in dcl (T)$ and thus $S \cup {a_{k + 2}} \notin {PAtt}_{T}^{k}$ . 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 = {x_{1}, \dots, x_{k + 1}}$ , $Y = {y_{1}, \dots, y_{k + 1}}$ additional arguments $a, b$ and the extension-set $S = {X \cup {a}} \cup {{b, y_{j}} \cup X ∖ {x_{j}} ∣ 1 ⩽ j ⩽ k + 1}$ . The set $S$ is k-tight as ${a, b}, {a, y_{i}}, {y_{i}, y_{j}}, {x_{i}, y_{i}} \in {PAtt}_{S}^{k}$ . On the other hand, $dcl (S)$ is not k-tight as for the set $X \in dcl (S)$ there is no $X^{'} \subseteq X$ such that $| X^{'} | ⩽ k$ and $X^{'} \cup {b} \in {PAtt}_{S}^{k}$ . 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 \subseteq 2^{A}$ is called k-conflict-sensitive w.r.t. a set $PAtt \subseteq {(S, b) ∣ | S | ⩽ k, S \cup {b} \in {PAtt}_{S}^{k}}$ if for each $A, B \in S$ such that $A \cup B \notin S$ , it holds that there is an argument $b \in B$ satisfying $(A, b) \in 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 = \infty$ .
Definition 22.
A set $S \subseteq 2^{A}$ is called k-defensive w.r.t. a set $PAtt \subseteq {(S, b) ∣ | S | ⩽ k, S \cup {b} \in {PAtt}_{S}^{k}}$ if for each $A \in S, a \in A, (B, a) \in PAtt$ there are $S \subseteq A, b \in B$ with $(S, b) \in 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 \subseteq 2^{A}$ is called k-adm-fortable if there exists a set $PAtt \subseteq {(S, b) ∣ | S | ⩽ k, S \cup {b} \in {PAtt}_{S}^{k}}$ 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 \in S$ consider all subsets B of size $min (k, | S |)$ and $b \in {Args}_{S} ∖ S$ and add $(B, b)$ to $PAtt$ whenever $B \cup {b} \in {PAtt}_{S}^{k}$ . 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) \in R ∣ S \subseteq {Args}_{adm (F)}, a \in {Args}_{adm (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 \cup 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) \in R$ with $S \subseteq C$ and $a \in C$ .
If $a \in T$ then, as T is conflict-free, $S \cap U \neq \emptyset$ . Moreover, as T is admissible it has to defend itself against $(S, a)$ , i.e. there is an attack $(T^{'}, u)$ with $T^{'} \subseteq T$ and $u \in S \cap U$ . Hence, we have $(T^{'}, b) \in PAtt$ .

If $a \in U$ then, as U is conflict-free, $S \cap T \neq \emptyset$ . Moreover, as U is admissible it has to defend itself against $(S, a)$ , i.e. there is an attack $(U^{'}, t)$ with $U^{'} \subseteq U$ and $t \in S \cap T$ . Now, as T is admissible as well, there is also an attack $(T^{'}, u)$ with $T^{'} \subseteq T$ and $u \in S^{'} \subseteq U$ . Hence, we have $(T^{'}, b) \in PAtt$ .

2) It remains to show that $S$ is k-defensive w.r.t. $PAtt$ . If $(B, a) \in PAtt$ then B attacks a in F. Thus each set $E \in adm (F)$ with $a \in E$ defends itself against B, i.e. for each $E \in adm (F)$ with $a \in E$ there is a pair $(S, b) \in R$ with $S \subseteq E$ and $b \in B$ . Thus, also $(S, b) \in 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) \in PAtt$ then also $({b}, a) \in 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) \in PAtt$ can be replaced by ${(S, b) ∣ S \in S, A \subset 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 \in S, S \cup A \in {PAtt}_{S}}$ . 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 \subseteq {(S, b) ∣ | S | ⩽ k, S \cup {b} \in {PAtt}_{S}^{k}}$ we define the k-SETAF $F_{S, PAtt}^{cf, k} = ({Args}_{S}, 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 \subseteq {Args}_{S}$ be some set of arguments such that $S = ⋃ T$ for some set $T \subseteq S$ . Then, we have that $S \in cf (F_{S, PAtt}^{cf, k})$ implies $S \in S$ .
Proof.
Consider a SETAF $F_{S, PAtt}^{cf, k}$ as given in Definition 24 and a set $S = ⋃ T$ for some subset $T \subseteq S$ with $S \in cf (F_{S, PAtt}^{cf, k})$ . Let us consider $A \subseteq T$ such that $⋃ A \in S$ and there is no $A^{'} \subseteq T$ such that $A \subset A^{'}$ and $⋃ A^{'} \in S$ . Note that such $A$ always exists because $⋃ \emptyset = \emptyset \in S$ . We also define $A = ⋃ A$ . Towards a contradiction assume $A \subset T$ and pick any $B \in T ∖ A$ . Then, by construction, we have that $A, B \in S$ , $(A \cup B) \subseteq S$ and that $(A \cup B) \notin S$ . Furthermore, since $S$ is k-conflict-sensitive, it follows that there are $A^{'} \subseteq A$ and $b \in B$ such that $| A^{'} | ⩽ k$ and $(A^{'}, b) \in PAtt$ . This implies that there is an attack $(A^{'}, b) \in PAtt$ and, thus, $(A^{'} \cup {b}) \notin cf (F_{S, PAtt}^{cf, k})$ . Finally, since $(A^{'} \cup {b}) \subseteq (A \cup B) \subseteq S$ and $cf (F_{S, PAtt}^{cf, k})$ is downward-closed, this implies $S \notin cf (F_{S, PAtt}^{cf, k})$ which is a contradiction with the assumption that $S \in cf (F_{S, PAtt}^{cf, k})$ . Hence, it must be that $A = T$ and, thus, that $A = S$ holds. Since $A \in S$ holds by construction, this implies $S \in S$ . □
Lemma 18.
Let $S$ be a extension-set with $\emptyset \in S$ that is k-defensive w.r.t. $PAtt$ . Then, $S \subseteq adm (F_{S, PAtt}^{cf, k})$ .
Proof.
Pick any set $S \in S$ . First of all by the choice of the attacks $PAtt$ the set S is conflict-free. Now consider any argument $a \in S$ and any attack $(B, a) \in PAtt$ As $S$ is k-defensive w.r.t. $PAtt$ there are some $S^{'} \subseteq S$ , $b \in B$ such that $(S^{'}, b) \in PAtt$ . That is, in $F_{S, PAtt}^{cf, k}$ the set S defends a against the attack $(S^{'}, a)$ . Hence, S defends itself against all attacks in $F_{S, PAtt}^{cf, k}$ . □

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

Given an extension-set $S$ , the defense-formula $D_{a}^{S}$ of an argument $a \in {Args}_{S}$ in $S$ is defined as $\begin{matrix} \underset{S \in S s.t. a \in S}{⋁} \underset{s \in S ∖ {a}}{⋀} s \end{matrix}$ $D_{a}^{S}$ given as (a logically equivalent) CNF is called CNF-defense-formula ${CD}_{a}^{S}$ of a in $S$ .

The defense formula $D_{a}^{S}$ 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 ([7]).

Given an extension-set $S$ and an argument $a \in {Args}_{S}$ , then for each $S \subseteq {Args}_{S}$ with $a \in S$ : $(S ∖ {a})$ is a model of $D_{a}^{S}$ (resp. ${CD}_{a}^{S}$ ) iff there exists an $S^{'} \subseteq S$ with $a \in S^{'}$ such that $S^{'} \in 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 $F_{S}^{def} = (A_{S}^{def}, R_{S}^{def})$ with $\begin{array}{l} A_{S}^{def} = {Args}_{S} \cup ⋃_{a \in {Args}_{S}} {α_{a γ} ∣ γ \in {CD}_{a}^{S}} \\ R_{S}^{def} = ⋃_{a \in {Args}_{S}} {({b}, α_{a γ}), ({α_{a γ}}, α_{a γ}), ({α_{a γ}}, a) ∣ γ \in {CD}_{a}^{S}, b \in γ} \end{array}$ the defense-argumentation-framework of $S$ , and let $F_{S, PAtt}^{adm, k} = F_{S, PAtt}^{cf, k} \cup F_{S}^{def}$ .

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 \in adm (F_{S}^{def})$ iff $S = ⋃ T$ for some $T \subseteq S$ .
Proof.
First notice that there are no conflicts between arguments in ${Args}_{S}$ and all arguments not in ${Args}_{S}$ are self-attacking. It thus suffices to show that S defends itself in $F_{S}^{def}$ iff $S = ⋃ T$ for some $T \subseteq S$ .

⇒: Let $S \in adm (F_{S}^{def})$ and consider an argument $a \in S$ . S attacks all the arguments $α_{a γ}$ that attack a and by construction this implies that S contains a model M of ${CD}_{a}^{S}$ . By Lemma 19 we have $M \cup {a} \in S$ . As this holds for each argument $a \in S$ there is a $T \subseteq S$ such that $S = ⋃ T$ .

⇐: Let $T \subseteq S$ and $S = ⋃ T$ . Consider $a \in S$ and a set $T \in T$ with $a \in T$ . By Lemma 19 we have that $T ∖ {a}$ is a model of ${CD}_{a}^{S}$ and thus attacks all of the arguments $α_{a γ}$ . That is a is defended by S. Hence, $S \in adm (F_{S}^{def})$ . □

When combining the two modules to the SETAF $F_{S, PAtt}^{adm, 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 ${\emptyset} \in S$ and set $PAtt \subseteq {(S, b) ∣ | S | ⩽ k, S \cup {b} \in {PAtt}_{S}^{k}}$ such that $S$ is k-conflict-sensitive and k-defensive w.r.t. $PAtt$ we have $adm (F_{S, PAtt}^{adm, k}) = S$ .
Proof.
We consider the k-SETAF $F_{S, PAtt}^{adm, k} = F_{S, PAtt}^{cf, k} \cup F_{S}^{def}$ from Definition 26 and show that $S = adm (F_{S, PAtt}^{adm, k})$ .
$S \subseteq adm (F_{S, PAtt}^{adm, k})$ : We have that, by Lemma 18, $S \subseteq adm (F_{S, PAtt}^{cf, k})$ , and, by Lemma 20, $S \subseteq adm (F_{S}^{def})$ . Hence, by Proposition 9(2), $S \subseteq adm (F_{S, PAtt}^{adm})$ .

$S \supseteq adm (F_{S, PAtt}^{adm})$ : Consider $S \in adm (F_{S, PAtt}^{adm})$ which by definition is conflict-free in $F_{S, PAtt}^{adm}$ . Notice that, attacks from $F_{S, PAtt}^{cf}$ cannot be used to defend against attacks from $F_{S}^{def}$ and vice versa. Thus, by Proposition 9(1) and the above observation, $S \in adm (F_{S, PAtt}^{cf})$ and $S \in adm (F_{S}^{def})$ .

By Lemma 20 we have that $S = ⋃ T$ for some $T \subseteq S$ . Now by Lemma 17 we have that if $S \in cf (F_{S, PAtt}^{cf, k})$ then $S \in S$ . As we already know that $S \in adm (F_{S, PAtt}^{cf, k}) \subseteq S$ we obtain $S \in S$ .
□

We now can state the exact characterization of the admissible signature for k-SETAFs.
Proposition 14.
$Σ_{adm}^{k} = {S \neq \emptyset ∣ S is k -adm-fortable and contains \emptyset}$ .
Proof.
First, by Lemma 16 we have that any $S \in Σ_{adm}^{k}$ 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 \subseteq {(S, b) ∣ | S | ⩽ k, S \cup {b} \in {PAtt}_{S}^{k}}$ such that $S$ is k-conflict-sensitive and k-defensive w.r.t. $PAtt$ . Thus, by Lemma 21, we have $adm (F_{S, PAtt}^{adm, k}) = S$ and thus $S \in Σ_{adm}^{k}$ . □

Based on our characterization of admissible semantics we can now also characterize the signature of preferred semantics.
Proposition 15.
$Σ_{pref}^{k} = {S \neq \emptyset ∣ 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) \in R ∣ S \subseteq {Args}_{adm} (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 \in pref (F)$ with $E \neq T$ . By the maximality of E and T we have that $E \cup T \notin pref (F)$ , $E \cup T$ is not contained in any preferred extension, and, by Lemma 2, we know that $E \cup T$ defends itself against all attackers. That is, there is a conflict $(B, a) \in R$ such that $B \subseteq E \cup T$ and $a \in E \cup T$ .
If $a \in E$ then, as E is conflict-free, $B \cap T \neq \emptyset$ . Moreover, as E is admissible it has to defend itself against $(B, a)$ , i.e. there is an attack $(S, b)$ with $S \subseteq E$ and $b \in B \cap T$ . Hence, we have $(S, b) \in PAtt$ .

If $a \in T$ then, as T is conflict-free, $B \cap E \neq \emptyset$ . Moreover, as T is admissible it has to defend itself against $(B, a)$ , i.e. there is an attack $(S^{'}, c)$ with $S^{'} \subseteq T$ and $c \in B \cap E$ . Now, as E is admissible as well, there is also an attack $(S, b)$ with $S \subseteq E$ and $b \in S \subseteq T$ . Hence, we have $(S, b) \in PAtt$ .

2) If $(S, b) \in PAtt$ then S attacks b in F. Thus each set $S^{'} \in pref (F)$ with $b \in S^{'}$ defends itself against S, i.e. for each $S^{'} \in pref (F)$ with $b \in S^{'}$ there is a pair $(S^{″}, a) \in R$ with $S^{″} \subseteq S^{'}$ and $a \in S$ . Thus, also $(S^{″}, a) \in 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 \cup {\emptyset}$ 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
$Σ_{adm}^{k} = {S \neq \emptyset ∣ S is k -adm-fortable and contains \emptyset}$ and

$Σ_{pref}^{k} = {S \neq \emptyset ∣ S is k -adm-fortable and incomparable}$ .

Example 15.
Reconsider the argument set $A = {a_{1}, a_{2}, \dots, a_{k + 1}, a_{k + 2}}$ and the extension-set $T = {S \subseteq A ∣ | S | = k + 1}$ from Example 13 as well as $U = T \cup {\emptyset}$ . We next argue that the extension-sets are not k-adm-fortable. Notice that ${PAtt}_{T}^{k} = {PAtt}_{U}^{k} = \emptyset$ 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 $S_{1} = {a_{1}, a_{2}, \dots, a_{k + 1}}$ , $S_{2} = {a_{2}, a_{2}, \dots, a_{k + 2}}$ , with $S_{1} \cup S_{2} \notin T$ we need $S^{'} \subset S_{1}$ and $t \in S_{2}$ such that $S^{'} \cup {t} \in 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 \subseteq A | S | = k + 1, a \in A ∖ S}$ . First, the extension-sets are both $(k + 1)$ -conflict-sensitive w.r.t. $PAtt$ , e.g. for $S_{1} = {a_{1}, a_{2}, \dots, a_{k + 1}}$ , $S_{2} = {a_{2}, a_{2}, \dots, a_{k + 2}}$ with $S_{1} \cup S_{2} \notin T$ we have $S_{1} \cup {a_{k + 2}} \in 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) \in PAtt$ and $a \in S^{'} \in T$ there is an attack $(S^{'}, b) \in PAtt$ with $b \in 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 $Σ_{com}^{1}$ in our notation. In this section, we generalize his characterization and construction to the case of $Σ_{com}^{k}$ 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 ${Args}_{S}$ .

Definition 27.
Given an integer $k ⩾ 1$ , a set $S \subseteq 2^{A}$ is called k-com-closed w.r.t. a set $PAtt \subseteq {(S, b) ∣ | S | ⩽ k, S \cup {b} \in {PAtt}_{S}^{k}}$ iff for each $T \subseteq S, T = ⋃ T$ we have $| C_{S} (T) | ⩽ 1$ and if $| C_{S} (T) | = 0$ then there is an attack $(S, t) \in PAtt$ such that $S \cup {t} \subseteq T$ .

We summarize the necessary conditions for $S \in Σ_{com}^{k}$ 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 ${Args}_{S}$ such that $S$ is k-defensive and k-com-closed w.r.t. $PAtt$ . Additionally we require that, when considering the SETAF $F = ({Args}_{S}, PAtt)$ , whenever $C_{S} (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 \subseteq 2^{A}$ is called k-com-fortable if there exist a set $PAtt \subseteq {(S, b) ∣ | S | ⩽ k, S \cup {b} \in {PAtt}_{S}^{k}}$ such that
$S$ is k-defensive w.r.t. $PAtt$ ,

$S$ is k-com-closed w.r.t. $PAtt$ , and

for each $T \subseteq S$ and $T = ⋃ T$ , if $C_{S} (T) = {C}$ then there is an order $(c_{1}, \dots c_{k})$ of the elements in $C ∖ T$ s.t. $\forall (S, c_{i}) \in PAtt$ : $\exists S^{'} \subseteq T \cup {c_{1}, \dots, c_{i - 1}}, d \in S : (S^{'}, d) \in PAtt$ .

Lemma 22.
For any k-SETAF F we have that $com (F)$ is k-comp-fortable and $⋂ com (F) \in com (F)$ .
Proof.
First of all, we have $⋂ com (F) = grd (F) \in 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 \cap ({Args}_{com (F)} \times {Args}_{com (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.
$com (F)$ is k-defensive w.r.t. $PAtt$ : Consider a set $E \in com (F)$ an attack $(S, e) \in PAtt$ with $e \in E$ . Thus $(S, e) \in R$ and as E is admissible there is an attack $(E^{'}, s) \in R$ with $s \in S$ and $E^{'} \subseteq E$ . Then by construction also $(E^{'}, s) \in PAtt$ and therefore $com (F)$ is k-defensive w.r.t. $PAtt$ .

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

Consider a subset of the complete extensions $T \subseteq com (F)$ such that $T = ⋃ T$ is admissible and let C be the unique minimal complete extension E such that $T \subseteq E$ . In case $T = C$ all the conditions are trivially satisfied, thus we consider $T \subset C$ . Now to order the arguments in $C^{'} = C ∖ T$ we use the following procedure: Starting from $c_{1}$ iteratively select element $c_{i}$ by picking an arbitrary argument in $C^{'} ∖ {c_{1}, \dots, c_{i - 1}}$ that is defended by $T \cup {c_{1}, \dots, c_{i - 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 $c_{i}$ . That is, the set $T_{i - 1} = T \cup {c_{1}, \dots, c_{i - 1}}$ does not defend any argument in $C^{'} ∖ {c_{1}, \dots, c_{i - 1}}$ . Moreover, as $T \subseteq C$ and C is complete we have that $T_{i - 1}$ does not defend any argument outside of $T_{i - 1}$ . That is, by Lemma 1, we have that $T_{i - 1}$ is admissible, the set $T_{i - 1}$ is a complete extension with $T \subseteq T_{i - 1}$ which is in contradiction to the minimality of E.
□

In order to realize extension-sets with complete semantics, again we first assume that $\emptyset \in 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 \subseteq {(S, b) ∣ | S | ⩽ k, S \cup {b} \in {PAtt}_{S}^{k}}$ we have the k-SETAF $F_{S, PAtt}^{cf, k} = ({Args}_{S}, PAtt)$ .
Lemma 23.
Let $S$ be k-com-closed w.r.t. $PAtt \subseteq {(S, b) ∣ | S | ⩽ k, S \cup {b} \in {PAtt}_{S}^{k}}$ and $T \subseteq {Args}_{S}$ be some set of arguments such that $T = ⋃ T$ for some subset $T \subseteq S$ . Then, we have that $T \in cf (F_{S, PAtt}^{cf, k})$ implies $| C_{S} (T) | = 1$ .
Proof.
Consider $T = ⋃ T$ and assume $| C_{S} (T) | = 0$ . Then, as $S$ is k-com-closed w.r.t. $PAtt$ , there is an attack $(S, t) \in PAtt$ with $S \cup {t} \subseteq T$ . By the construction of $F_{S, PAtt}^{cf, k}$ , this is in contradiction to $T \in cf (F_{S, PAtt}^{cf, 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 \in {Args}_{S}$ we consider all sets $T = {Args}_{T}$ with $T \subseteq S$ such that $| C_{S} (T) | = 1$ and $a \in C_{S} (T)$ .
Definition 29.
Given an extension-set $S$ , the extended-defense-formula ${ED}_{a}^{S}$ of an argument $a \in {Args}_{S}$ in $S$ is defined as $\begin{matrix} \underset{T \in {⋃ T ∣ T \subseteq S} s.t. a \in C_{S} (T)}{⋁} \underset{s \in T}{⋀} s \end{matrix}$ ${ED}_{a}^{S}$ given as (a logically equivalent) CNF is called CNF-extended-defense-formula ${CED}_{a}^{S}$ of a in $S$ .

The extended-defense-formula ${ED}_{a}^{S}$ 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 \in {Args}_{S}$ , then for each $S \subseteq {Args}_{S}$ with $a \in S$ : S is a model of ${ED}_{a}^{S}$ (resp. ${CED}_{a}^{S}$ ) iff there exists an $T \subseteq S, T = ⋃ T$ with $a \in C_{S} (T)$ and $T \subseteq S$ .
Proof.
Notice that our formula ${ED}_{a}^{S}$ only contains positive literals.

⇒: If S is a model of ${ED}_{a}^{S}$ then it satisfies one of the conjuncts $⋀_{s \in T}$ , and thus there is a set $T \subseteq S$ with $a \in C_{S} (T)$ and $T = ⋃ T$ for some $T \subseteq S$ .

⇐: Assume that S has a subset T with $a \in T$ and $T = ⋃ T$ for some $T \subseteq S$ . Then consider the sub-formula $⋀_{s \in T} s$ . 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 $\emptyset \in S$ , we call $F_{S}^{edef} = (A_{S}^{edef}, R_{S}^{edef})$ with $\begin{array}{l} A_{S}^{edef} = {Args}_{S} \cup ⋃_{a \in {Args}_{S}} {α_{a γ} ∣ γ \in {CED}_{a}^{S}} \\ R_{S}^{edef} = ⋃_{a \in {Args}_{S}} {({b}, α_{a γ}), ({α_{a γ}}, α_{a γ}), ({α_{a γ}}, a) ∣ γ \in {CED}_{a}^{S}, b \in γ} \end{array}$ the extended defense-argumentation-framework of $S$ . Given an extension-set $S$ and $S^{'} = reduced (S)$ we define $F_{S, PAtt}^{com, k} = F_{S, PAtt}^{cf, k} \cup F_{S^{'}}^{edef}$ .

We next show that $F_{S, PAtt}^{com, k}$ realizes any k-comp-fortable extension-set $S$ with $\emptyset \in S$ .
Lemma 25.
For every extension-set $S$ with $\emptyset \in S$ that satisfies the three conditions for being k-comp-fortable w.r.t. a set $PAtt \subseteq {(S, b) ∣ | S | ⩽ k, S \cup {b} \in {PAtt}_{S}^{k}}$ we have $com (F_{S, PAtt}^{com}) = S$ .
Proof.
$com (F_{S, PAtt}^{com}) \subseteq S$ : Consider $S \in F_{S, PAtt}^{com}$ . As S is conflict free, by the construction of $F_{S, PAtt}^{cf, k}$ , we have that there is no attack $(S^{'}, a) \in PAtt$ with $S^{'} \cup {a} \subseteq S$ . Let $T_{S} = {T \in S ∣ T \subseteq S}$ . As S defends each argument in $s \in S$ , against attackers $α_{s γ}$ , the set S is a model of ${ED}_{s}^{S}$ . Thus, by Lemma 24, for each $s \in S$ there is a set $T_{s} \subseteq T_{S}$ with $T_{s} = ⋃ T_{s} \subseteq S$ and $s \in C_{S} (T_{s})$ . Let $T_{S} = ⋃ T_{S}$ then as $T_{S} \subseteq S$ , by Lemma 23, it has a unique completion in $S$ w.r.t. $PAtt$ and by the above $S \subseteq C_{S} (T_{S})$ . Next, we show that each argument $s \in C_{S} (T_{S})$ 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 $C_{S} (T_{S}) ∖ T_{S}$ as $(c_{1}, c_{2}, \dots, c_{k})$ such that $T \cup {c_{1}, \dots, c_{i} - 1}$ defends $c_{i}$ against all attacks from $PAtt$ . Moreover, as T is a model of all ${ED}_{c}^{S}$ for $c \in {c_{1}, \dots, c_{k}}$ , by the construction of $F_{S}^{edef}$ it defends the arguments $c_{1}, \dots, c_{k}$ against attacks $α_{c_{i} γ}$ . Thus by induction on i all the arguments $c_{i}$ are defended and contained in S. Hence, $C_{S} (T) = S$ and hence $S \in S$ .

$com (F_{S, PAtt}^{com}) \supseteq S$ : Consider $S \in S$ . By construction we have that $S \in cf (F_{S, PAtt}^{com})$ . It remains to show that (i) S defends each of its arguments and (ii) does not defend any argument in ${Args}_{S} ∖ S$ (the arguments outside of ${Args}_{S}$ are self-attacking anyway).
To show $S \in adm (F_{S, PAtt}^{com})$ consider an arbitrary argument $s \in 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 ${CED}_{s}^{S}$ (cf. Lemma 24). Second, the attacks $(B, s) \in PAtt$ . As $S$ is k-defensive, there is a set $S^{'} \subseteq S$ and an argument $b \in B$ such that $(S^{'}, b) \in PAtt$ . That is, S defends each $s \in S$ .

To show $S \in com (F_{S, PAtt}^{com})$ consider an arbitrary argument $a \in {Args}_{S} ∖ S$ . As $S \in S$ we have that $C_{S} (S) = S$ and thus neither the set S nor any of its subsets appear in the definition of the formula ${CED}_{a}^{S}$ , i.e., none of this sets is a model of ${CED}_{a}^{S}$ (cf. Lemma 24). That is, there is an argument $α_{a γ}$ that is not attacked by S but attacks a (note that, by construction, ${CED}_{a}^{S}$ has at least one clause, as there is always at least one $T \in S$ with $a \in C_{S} (T)$ ). Thus, S does not defend a. Hence, S is a complete extension of $F_{S, PAtt}^{com}$ .
□

We now can state the exact characterization of the complete signature in k-SETAFs.
Theorem 11.
$Σ_{com}^{k} = {S \neq \emptyset ∣ S is k -comp-fortable and ⋂ S \in 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 $F_{S^{'}, PAtt}^{com}$ with $com (F_{S^{'}, PAtt}^{com}) = S^{'}$ . Thus with $F = F_{S^{'}, PAtt}^{com} \cup ({Args}_{S}, \emptyset)$ we obtain $com (F) = S$ . Also notice that $F_{S, PAtt}^{com} = F_{S^{'}, PAtt}^{com} \cup ({Args}_{S}, \emptyset) = F$ . □
Example 16.
Consider the argument set $A = {a_{1}, a_{2}, \dots, a_{k + 1}, a_{k + 2}}$ and the extension-set $U = {S \subseteq A ∣ | S | = k + 1} \cup {\emptyset}$ (cf. Example 15). Recall that ${PAtt}_{U}^{k} = \emptyset$ 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 $S_{1} = {a_{1}, a_{2}, \dots, a_{k + 1}}$ , $S_{2} = {a_{2}, a_{2}, \dots, a_{k + 2}}$ , with $S_{1} \cup S_{2} \notin U$ and thus $| C_{S} (S_{1} \cup S_{2}) | = 0$ . In order to satisfy the k-com-closed we need an attack $(S, t) \in PAtt$ such that $S \cup {t} \subseteq S_{1} \cup S_{2}$ . 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 \in T, a \in A ∖ S})$ we have $com (F) = U$ .

Exploiting a translation from [12] we can show that $Σ_{adm}^{k} \subseteq Σ_{com}^{k}$ .
Proposition 16.
$Σ_{adm}^{k} \subseteq Σ_{com}^{k}$ .
Proof.
Consider a set $S \in Σ_{adm}^{k}$ , 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 $\begin{array}{l} A^{'} = A \cup {a^{'} ∣ a \in A} \\ R^{'} = R \cup {({a^{'}}, a^{'}), ({a}, a^{'}), ({a^{'}}, a) ∣ a \in A} \end{array}$ 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 \in 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 \in Σ_{com}^{k}$ . □

Next, we give an example of an extension-set $S \in Σ_{com}^{k}$ , but $S \notin Σ_{adm}^{k}$ and thus show $Σ_{adm}^{k} \subset Σ_{com}^{k}$ .
Example 17.
Recall Example 9 showing that $Σ_{adm}^{\infty} \subset Σ_{com}^{\infty}$ . There we had the extension-set $S = {\emptyset, {a}, {b}, {a, b, c}}$ which is not in $Σ_{adm}^{\infty}$ and thus also $S \notin Σ_{adm}^{k}$ . However we can realize $S$ with the 1-SETAF $F = (A, R)$ with $\begin{array}{l} A = & {a, b, c} \cup {x_{a}, x_{b}, x_{c}, y_{c}} \\ R = & {({x_{i}}, x_{i}), ({x_{i}}, i) ∣ i \in {a, b, c}} \cup {({y_{c}}, y_{c}), ({y_{c}}, c)} \\ \cup {({a}, x_{a}), {b}, x_{b}), ({a}, x_{c}), {b}, y_{c})} \end{array}$ It can easily verified that $com (F) = S$ and thus $S \in Σ_{com}^{k}$ for $k ⩾ 1$ .

By the Examples 15, 16, & 17 we have that (a) there are extension-sets that are in $Σ_{com}^{1}$ but in no $Σ_{adm}^{k}$ (not even in $Σ_{adm}^{\infty}$ ) and that (b) there are extension-sets in $Σ_{adm}^{k + 1}$ that are not contained in $Σ_{com}^{k}$ .
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.
$Σ_{sem}^{k} = {S \neq \emptyset ∣ 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) \in R ∣ S \subseteq {Args}_{adm} (F)}$ . As shown there this set satisfies the conditions for $S$ being k-adm-fortable.

Next we argue that $Σ_{pref}^{k} \subseteq Σ_{sem}^{k}$ . 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 $\begin{array}{l} A^{'} = A \cup {a^{'} ∣ a \in A} \\ R^{'} = R \cup {({a^{'}}, a^{'}), ({a}, a^{'}) ∣ a \in A} \end{array}$ Now it is easy to verify that $pref (F) = pref (F^{'}) = sem (F^{'})$ . That is, for each $S \in Σ_{pref}^{k}$ we have a SETAF F with $pref (F) = S$ and thus a SETAF $F^{'}$ with $sem (F) = S$ , i.e., $S \in Σ_{sem}^{k}$ . 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.
$Σ_{stage}^{k} = {S \neq \emptyset ∣ S is incomparable and k -tight}$ .
Proof.
First consider $stage (F)$ for some k-SETAF F. As $stb (F) \subseteq naive (F)$ , and $naive (F)$ is incomparable by definition, we have that $stb (F)$ is incomparable, as well. Now consider $E \in stage (F)$ . As each stage extensions is also a naive extensions for each argument $a \notin E$ there is an attack $(B, b)$ such that $B \cup {b} \subseteq E \cup {a}$ . That is there is no $E^{'} \in stage (F)$ with $B \cup {b} \subseteq E^{'}$ and thus $B \cup {b} \in {PAtt}_{stage (F)}$ . That is, the extension-set $stage (F)$ is k-tight.

Now consider $S \in Σ_{stb}^{k}$ , 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
$Σ_{stage}^{k} = {S \neq \emptyset ∣ S is incomparable and k -tight}$ and

$Σ_{sem}^{k} = {S \neq \emptyset ∣ 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: $\begin{array}{l} Σ_{cf}^{k} = {S \neq \emptyset ∣ S is downward-closed and k -tight} \\ Σ_{naive}^{k} = {S \neq \emptyset ∣ S is incomparable and dcl (S) is k -tight} \\ Σ_{stb}^{k} = {S ∣ S is incomparable and k -tight} \\ Σ_{adm}^{k} = {S \neq \emptyset ∣ S is k -adm-fortable and contains \emptyset} \\ Σ_{pref}^{k} = {S \neq \emptyset ∣ S is incomparable and k -adm-fortable} \\ Σ_{com}^{k} = {S \neq \emptyset ∣ S is k -com-fortable and ⋂ S \in S} \\ Σ_{stage}^{k} = {S \neq \emptyset ∣ S is incomparable and k -tight} \\ Σ_{sem}^{k} = {S \neq \emptyset ∣ S is incomparable and k -adm-fortable} \end{array}$

For all semantics $σ \in {cf, naive, stb, adm, pref, stage, sem}$ and $2 ⩽ k < \infty$ $\begin{matrix} (3) & Σ_{σ}^{1} \subset Σ_{σ}^{k} \subset Σ_{σ}^{k + 1} \subset Σ_{σ}^{\infty} \end{matrix}$

The ⊆-relations follow immediately from the fact that ${AF}_{A}^{k} \subseteq {AF}_{A}^{k + 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^{'} \cup {a} \in {PAtt}_{S}^{k}$ and $S^{'} \subseteq S \in 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 \in S$ . As $S$ is incomparable we have $S \cup T \notin S$ and for each $t \in T ∖ S$ that $S \cup {t} \notin S$ . In particular there exists at least one $t \in T ∖ S$ and as $S$ is k-tight there is a set $S^{'} \subseteq S$ with $S^{'} \cup {t} \in {PAtt}_{S}^{k}$ . By the construction of $PAtt$ we have $(S^{'}, t) \in PAtt$ and the condition for being k-conflict-sensitive is satisfied

$S$ is k-defensive w.r.t. $PAtt$ : Now consider a set $T \in S$ that is attacked by $(S^{'}, t) \in PAtt$ , i.e. $t \in T$ . We have that $S^{'}$ must contain an argument s such that $T \cup {s} \notin S$ otherwise, as $S$ is incomparable, $S^{'} \cup {t} \subseteq T$ and thus $S^{'} \cup {t} \notin {PAtt}_{S}^{k}$ . Then, as $S$ is tight, there is a pair $(T^{'}, s) \in PAtt$ with $T^{'} \subseteq 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 \cup C \cup {e}$ with $B = {b_{1}, b_{2}, \dots, b_{k + 1}}$ , $C = {c_{1}, c_{2}, \dots, c_{k + 1}}$ and the extension-set $S$ that contains (i) the set B, and (ii) the sets $B \cup {c_{i}, e} ∖ {b_{i}}$ 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 \in S$ and the argument e. We have that $S \cup {e} \notin S$ but for each $S^{'} \subset S$ with $| S^{'} | ⩽ k$ the set $S^{'} \cup {e}$ is contained in one of the sets in $S$ and thus $S^{'} \cup {e} \notin {PAtt}_{S}^{k}$ . 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, $Σ_{naive}^{k} \subseteq Σ_{stb}^{k} ∖ {\emptyset}$ . By Example 14, $Σ_{naive}^{k} \subset Σ_{stb}^{k} ∖ {\emptyset}$ .

We conclude that for any $k ⩾ 1$ , $\begin{matrix} Σ_{naive}^{k} \subset Σ_{stb}^{k} ∖ {\emptyset} = Σ_{stage}^{k} \subset Σ_{pref}^{k} = Σ_{sem}^{k} . \end{matrix}$

We finally turn to the relation between conflict-free sets, admissible sets and complete extensions. Recall that Proposition 16 already showed $Σ_{adm}^{k} \subseteq Σ_{com}^{k}$ . Example 17 in fact shows $Σ_{adm}^{k} \subset Σ_{com}^{k}$ for $k ⩾ 1$ . Inspecting Example 6 and 10 we have an extension-set $S^{'} = {\emptyset, {a}, {b}, {c}, {a, b}, {b, c}, {a, c}}$ with $S^{'} \in Σ_{cf}^{2}$ but $S^{'} \notin Σ_{adm}^{\infty}$ and $S^{'} \notin Σ_{com}^{\infty}$ which shows that, for $k ⩾ 2$ , $Σ_{cf}^{k} ⊈ Σ_{adm}^{k}$ and $Σ_{cf}^{k} ⊈ Σ_{com}^{k}$ . Likewise, $Σ_{cf}^{k} ⊉ Σ_{adm}^{k}$ is easy to see ( $k ⩾ 1$ ), e.g. consider $S = {\emptyset, {a, b}}$ with $S \in Σ_{adm}^{1}$ but, as $S$ is not downward-closed, $S \notin Σ_{cf}^{\infty}$ . By Proposition 16, $Σ_{cf}^{k} ⊉ Σ_{com}^{k}$ follows, as well.

Finally, we show that the result of Proposition 11 carries over to k-SETAFs for any $k ⩾ 1$ .
Proposition 20.
$Σ_{cf}^{k} \cap Σ_{com}^{k} \subseteq Σ_{adm}^{k}$ .
Proof.
Consider $S \in Σ_{cf}^{\infty} \cap Σ_{com}^{\infty}$ , 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 $\emptyset \in 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 \in S$ such that $A \cup B \notin S$ . As $S$ is downward closed this implies $| C_{S} (A \cup B) | = 0$ and thus, as $S$ is k-com closed there is $(T, u) \in PAtt$ with $T \cup {b} \in A \cup B$ , w.l.o.g. $b \in B$ . As $S$ is k-defensive there is also an attack $(B^{'}, a)$ with $B^{'} \subset B$ , $a \in T \cap A$ and further an attack $(A^{'}, b^{'})$ with $A^{'} \subset A$ , $b^{'} \in 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).
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 $Σ_{σ}^{\infty}$ 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 $Σ_{σ}^{\infty} \supseteq Σ_{σ^{'}}^{\infty}$ . While $Σ_{σ}^{\infty}$ 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 $\begin{matrix} Σ_{naive}^{\infty} = Σ_{stb}^{\infty} ∖ {\emptyset} = Σ_{stage}^{\infty} = Σ_{pref}^{\infty} = Σ_{sem}^{\infty} . \end{matrix}$ 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$ , $\begin{matrix} Σ_{naive}^{k} \subset Σ_{stb}^{k} ∖ {\emptyset} = Σ_{stage}^{k} \subset Σ_{pref}^{k} = Σ_{sem}^{k} . \end{matrix}$ 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 $Σ_{cf}^{1} \subseteq Σ_{adm}^{1} \subseteq Σ_{com}^{1}$ , for $k ⩾ 2$ we get $Σ_{cf}^{k} ⊈ Σ_{com}^{k}$ while $Σ_{adm}^{k} \subseteq Σ_{com}^{k}$ remains valid. Finally, we have shown that expressibility of SETAFs form a strict hierarchy w.r.t. the attack-cardinality: for all semantics $σ \in {cf, naive, stb, adm, pref, stage, sem}$ and $2 ⩽ k < \infty$ , it holds that $\begin{matrix} Σ_{σ}^{1} \subset Σ_{σ}^{k} \subset Σ_{σ}^{k + 1} \subset Σ_{σ}^{\infty} \end{matrix}$ 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 $Σ_{σ}^{\infty}$ for $σ \in {stb, stage, pref, sem}$ shows that every $S \in Σ_{σ}^{\infty}$ 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.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].

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}^{\infty} = Σ_{ideal}^{k} = Σ_{eager}^{\infty} = Σ_{eager}^{k} = {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.

Footnotes

Acknowledgements

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

References

Baumann ,

Dvořák ,

Linsbichler ,

Spanring ,

Strass and

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.

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

Brewka ,

Polberg and

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.

Caminada ,

W.A.

Carnielli and

P.E.

Dunne , Semi-stable semantics, J. Log. Comput. 22 (2012), 1207–1254. doi:10.1093/logcom/exr033.

Diller ,

Keshavarzi Zafarghandi ,

Linsbichler and

Woltran , Investigating subclasses of abstract dialectical frameworks, in: Computational Models of Argument – Proceedings of COMMA 2018, Warsaw, Poland, 12–14 September 2018,

Modgil ,

Budzynska and

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.

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.

P.E.

Dunne ,

Dvořák ,

Linsbichler and

Woltran , Characteristics of multiple viewpoints in abstract argumentation, Artif. Intell. 228 (2015), 153–178. doi:10.1016/j.artint.2015.07.006.

P.E.

Dunne ,

Spanring ,

Linsbichler and

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,

Kambhampati , ed., IJCAI/AAAI Press, 2016, pp. 1051–1057, http://www.ijcai.org/Abstract/16/153 . ISBN 978-1-57735-770-4.

Dvořák and

P.E.

Dunne , Computational problems in formal argumentation and their complexity, in: Handbook of Formal Argumentation,

Baroni ,

Gabbay ,

Giacomin and

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.

Dvořák ,

Fandinno and

Woltran , On the expressive power of collective attacks, in: Computational Models of Argument – Proceedings of COMMA 2018, Warsaw, Poland, 12–14 September 2018,

Modgil ,

Budzynska and

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.

Dvořák ,

Greßler and

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,

Thimm ,

Cerutti and

Vallati , eds, CEUR Workshop Proceedings, Vol. 2171, CEUR-WS.org, 2018, pp. 10–21, http://ceur-ws.org/Vol-2171/paper_2.pdf .

12.

Dvořák and

Woltran , On the intertranslatability of argumentation semantics, J. Artif. Intell. Res. (JAIR) 41 (2011), 445–475. doi:10.1613/jair.3318.

13.

Flouris and

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.

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.

Linsbichler ,

Pührer and

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

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.

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

18.

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

19.

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

20.

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.

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.

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.

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

van den Herik , eds, CWI, Amsterdam, Netherlands, 1998, pp. 57–66.

24.

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.

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,

Modgil ,

Budzynska and

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.

Yun ,

Vesic and

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,

Modgil ,

Budzynska and

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.

On the expressive power of collective attacks

Abstract

Keywords

1. Introduction

2.1. Argumentation frameworks with collective attacks

3. Signatures of SETAFs with unrestricted collective attacks

2 We note that for any incomparable extension-set S , F S cf = F S stb .

Lemma 19 ([7]).

Footnotes

Acknowledgements

References

²
We note that for any incomparable extension-set $S$ , $F_{S}^{cf} = F_{S}^{stb}$ .