Investigating the Relationship between Argumentation Semantics via Signatures

1 Introduction

Within Artificial Intelligence argumentation has become one of the major fields over the last two decades (Rahwan and Simari, 2009; Bench-Capon and Dunne, 2007). In particular, abstract argumentation frameworks (AFs) introduced by Dung (1995) are a simple, yet powerful formalism for modeling and deciding argumentation problems that are integral to many advanced argumentation systems, see e.g. (Caminada and Amgoud, 2007). Evaluating AFs is done via so-called semantics (cf. (Baroni et al., 2011a) for an overview) that deliver subsets of jointly acceptable arguments.

Several semantics have been introduced over the years (Dung, 1995; Verheij, 1996; Caminada, 2007; Caminada et al., 2012; Baroni et al., 2011b). It is thus important to understand the behaviour of different semantics when applied to an AF. For instance, it is known that for any AF, its set of stable extensions is a subset of its set of preferred extensions (already proven by Dung (1995)). More recently, Dunne et al. (2015) have shown that for any AF F, its set of stable extensions (if not empty) can be realized via preferred semantics (i.e. there exists an AF F 0 such that the preferred extensions of F 0 equal the stable extensions of F). However, there is one aspect which has not been addressed yet. In fact, in this paper

Thomas Linsbichler and StefanWoltran

Institute of Information Systems TU Wien, Vienna, Austria ¶linsbich,woltran♦@dbai.tuwien.ac.at

we are interested in questions of the following kind: Given sets S↪ T of extensions, does there exist an AF F such that its stable extensions are given by S and its preferred extensions are given by T. More formally, we are interested in characterizing the following concepts for semantics σ↪ ⌧ , which we call two-dimensional signatures:

The motivation for such work is manyfold. First it tells us about the independence between semantics. Let us again consider stable (sb) and preferred (pr) extensions and suppose we have two AFs F↪ F 0 with sb(F ) ✓ pr(F 0 ). Is there also an AF F 00 with sb(F 00 ) = sb(F ) and pr(F 00 ) = pr(F 0 )? This might not always be possible since there are certain dependencies between the two semantics which can make the existence of such an F 00 impossible, and - as we will show - this is indeed the case for this particular pair of semantics, i.e.

However, for certain other pairs of semantics we shall prove such a strong form of independence; for instance, for naive (na) semantics, it is known that sb(F) ✓ na(F), and this is sufficient for the corresponding two-dimensional signature:

The second motivation for our work is that it helps to prune the search space for systems designed to enumerate all extensions of a given semantics ⌧. This is of particular interest when the complexity for some other semantics σ is milder than the one for ⌧. Again consider stable and preferred semantics, the latter being more complex (Dunne and BenchCapon, 2002). Results like (1) indicate that for enumerating all preferred extensions, starting with the computation of all stable extensions not only yields a subset of the desired preferred extensions but ultimately rules out certain candidates to become preferred extensions, besides those being comparable (wrt. subset inclusion) to already obtained ones.

For an example in a more concrete application, consider examination of evidence and facts in a legal case. The nature of which subsets are argued may depend on the environment in which the case is argued, e.g. standards of proof differ between civil and criminal cases so that based on the same evidence different conclusions may be reached. One view of stable semantics is that for a fixed stable extension, S, every argument has a definite status: either in S or attacked by S. In a legal setting, stable semantics is appropriate to cases that have to be demonstrated "beyond reasonable doubt". In contrast preferred semantics allows some arguments to have an undetermined state with respect to a fixed S: neither in S nor attacked by S. Our results shed light on how much undeterminism preferred semantics may add in contrast to stable semantics in such a situation.

Related work. There has been thorough research on translations (Dvoˇr´ak and Woltran, 2011; Dvoˇr´ak and Spanring, 2012) where mappings ✓ are studied such that, for any AF F, σ(✓(F)) is in a certain relation to ⌧(F). Naturally, these results are concerned with two different AFs; we on the other hand explore the range of pairs of extensions a single AF is able to express via two types of semantics. The already mentioned work by Dunne et al. (2015) has initiated this kind of research but treated semantics separately. Other results on dependencies between semantics occur in the work on spectra (Baumann and Brewka, 2013), which is concerned with enforcing single arguments.

Main Contributions. We aim for exactly characterizing all two-dimensional signatures for 9 prominent semantics. Due to symmetry this requires in total 36 results, from which we succeed to show 32. We also discuss the particular issue for the four open problems (which are all depending on the twodimensional signature for preferred and semi-stable semantics). Hereby, we provide an interesting observation concerning the role of implicit conflicts (Linsbichler et al., 2015).

2 Background

We first recall basic notions of Dung's abstract frameworks (the reader is referred to (Dung, 1995; Baroni et al., 2011a) for further background).

An Argumentation Framework (AF) is a pair F = (A↪ R), where A ⇢ A is a finite set of arguments for A being the (countably infinite) universe of all arguments available, and R ✓ A⇥A is its attack relation. The collection of all AFs is given by AFA. For (a↪ b) 2 R we say that a attacks b (in F), accordingly a set S ✓ A attacks an argument a 2 A (in F ) if 9b 2 S : (b↪ a) 2 R. The range in F of a set of arguments S ✓ A is given as S+ F = S[¶a 2 A ♣ S attacks a♦. Subscript F may be dropped if clear from the context. A set S ✓ A defends argument a 2 A (in F ) if S attacks all attackers of a.

A semantics σ is a mapping from AFs to sets of arguments. For a given AF F = (A↪ R) the members of σ(F) are called (σ-)extensions. A set S ✓ A is conflict-free in F (S 2 cf(F )) if it does not contain any attacks, i.e. (S ⇥ S) \ R = ;; S 2 cf(F) is admissible in F (S 2 ad(F)) if each a 2 S is defended by S; S 2 ad(F) is complete (S 2 co(F)) if S contains all a 2 A it defends. We define the naive, stable, preferred and semi-stable extensions:

• ÷ S 2 na(F), if S 2 cf(F) and @T 2 cf(F) s.t. S ⇢ T ;
• ÷ S 2 pr(F), if S 2 ad(F) and @T 2 ad(F) s.t. S ⇢ T ;
• ÷ S 2 sb(F), if S 2 cf(F) and S+ F = A;
• ÷ S 2 sm(F), if S 2 ad(F) and @T 2 ad(F) s.t. S+ F ⇢ T + F .

Finally, for semantics σ↪ ⌧ we define the ideal reasoning semantics (see e.g. (Dunne et al., 2013)) for σ under ⌧ (idσ↪⌧ ) as sets S 2 σ(F) being ✓-maximal in satisfying S ✓ T for each T 2 ⌧(F). In this paper, we use the grounded (gr(F) = idad↪co(F)), ideal (id(F) = idad↪pr(F)) and eager (eg(F) = idad↪sm(F)) semantics. Since gr, id and eg always provide exactly one extension, we sometimes refer to this by Gr, Id and Eg; thus, for instance, gr(F) = ¶Gr(F)♦.

Towards the characterization of signatures, we require a few more concepts, mostly taken from (Dunne et al., 2015; Baumann et al., 2014) (however, written in a slightly different way). A set of sets of arguments S ✓ 2A is called extensionset if S S is finite. Given an extension-set S, we denote the ✓-maximal elements of S by max(S). Moreover, we define the conflicts in S (ConfsS ) and the borders of S (bd(S)) as

Finally, given S↪ T ✓ 2A , S is called conflict-sensitive wrt. T, or SoT for short, if for all A↪ B 2 S such that A[B ◁2 S there are a 2 A, b 2 B with (a↪ b) 2 ConfsT .

Example 1. Let S = ¶¶a↪ b♦↪ ¶a↪ c↪ e♦↪ ¶b↪ d↪ e♦♦. First, S is an extension-set. Moreover, we have max(S) = S, ConfsS = ¶(a↪ d)↪ (d↪ a)↪ (b↪ c)↪ (c↪ b)↪ (c↪ d)↪ (d↪ c)♦, and bd(S) = ¶¶a↪ b↪ e♦↪ ¶a↪ c↪ e♦↪ ¶b↪ d↪ e♦♦. Finally, S o S as, for instance, (b↪ c) 2 ConfsS for ¶a↪ b♦ and ¶a↪ c↪ e♦.

3 Signatures

We first recall the results from (Dunne et al., 2015) (similar in style of presentation to (Baumann et al., 2014)) on signatures and then generalize this concept to multiple semantics.

Definition 1. Given a semantics σ, a set S ✓ 2A is realizable under σ if there is an AF F with σ(F) = S (F realizes S under σ). The signature of σ is defined as ⌃σ = ¶σ(F) ♣ F 2 AFA♦.

Proposition 1. The following collections of extension-sets S yield the signatures of the semantics under consideration.

• ÷ ⌃gr = ⌃id = ⌃eg = ¶S ♣ ♣S♣ = 1♦;
• ÷ ⌃na = ¶S 6= ; ♣ S = bd(S)♦;
• ÷ ⌃cf = ¶S 6= ; ♣ max(S)=bd(S)↪ 8S 2 S8S0 ✓ S : S02S♦;
• ÷ ⌃sb = ¶S ♣ S ✓ bd(S)♦;
• ÷ ⌃pr = ⌃sm = ¶S 6= ; ♣ S = max(S)↪ S o S♦.
• ÷ ⌃ad = ¶S 6= ; ♣ ; 2 S↪ S o S♦;

The signatures for σ 2 ¶id↪ eg♦ have not been given explicitly in (Dunne et al., 2015), but they directly follow from the realization of any extension-set S 2 ⌃σ by the AF (S S↪ ;).

We now give (slight modifications of) the canonical AFs used in (Dunne et al., 2015) to realize certain extension-sets; they are the basis for some constructions used in Section 4.

Definition 2. Given extension-set S, define Fsb(;) = (¶a♦↪ ¶(a↪ a)♦) and, for S 6= ;, Fsb(S) = (A↪ ConfsS [ R) with

Definition 3. Given extension-set S, let Sns = S S∩T S, and Sa = ¶S2S ♣ a2S♦ for a 2 S S. The defense formula for a in S is WS2Sa Vb2S∩¶a♦ b; ΓS↪a is a logically equivalent formula in conjunctive normal form. Define Fpr(S) = Fad(S) = (A↪ ConfsS [ R), Fsm(S) = (A [ ¯ A↪ ConfsS [ R [ ¯R) with

Proposition 2. For σ 2 ¶sb↪ pr↪ sm↪ ad♦, given S 2 ⌃σ it holds that σ(Fσ(S)) = S.

The natural generalization of signatures is now defined as follows. It captures the capabilities of AFs with respect to different sets of semantics.

Definition 4. Given semantics σ1↪ ▷ ▷ ▷ ↪ σn, their (ndimensional) signature is defined as

We say that AF F realizes hS1↪ ▷ ▷ ▷ ↪ Sni under (σ1↪ ▷ ▷ ▷ ↪ σn) if σi(F) = Si for all i 2 ¶1↪ ▷ ▷ ▷ ↪ n♦.

In this paper, we will restrict to two-dimensional signatures. The following observation is crucial. Given arbitrary semantics σ and ⌧ it always holds for members hS↪ Ti of ⌃σ↪⌧ that S 2 ⌃σ and T 2 ⌃⌧ . When characterizing the twodimensional signatures we will omit this necessary condition by using the following abbreviation:

4 Characterizing 2-Dimensional Signatures

In this section, we give characterizations for the nine semantics we consider in this paper. Exploiting the obvious symmetry ⌃σ↪⌧ = ¶hS↪ Ti ♣ hT↪ Si 2 ⌃⌧↪σ♦, characterizing in total 36 signatures is still required. We proceed as follows. First, we consider signatures involving only unique status semantics (that is gr, id, and eg); second, we characterize signatures involving a unique status semantics and a multiple status semantics (that is na, sb, sm, and pr); third, we consider the combinations of multiple status semantics; then, we characterize the signatures involving cf and ad; Table 1 summarizes our results, leaving four open questions, all being related to the issue of sm and pr which we discuss in Section 4.5.

4.1 Unique Status Semantics

It is well known that Gr(F) ✓ Id(F) ✓ Eg(F) for any AF F. In order to characterize the respective signatures, the question occurs whether this condition is also sufficient. In other words, can we find, for any given finite sets S↪ T with S ✓ T , AFs F , F 0 and F 00 such that Gr(F ) = S, Id(F ) = T , Gr(F 0 ) = S, Eg(F 0 ) = T, Id(F 00 ) = S, and Eg(F 00 ) = T. The following example answers this question positively.

Example 2. For index sets I↪ J↪ K take into account the modular AF F = (A↪R) with A = ¶ai↪ bj↪¯bj↪ ck↪ c0k ↪ ¯ ck ♣ i 2 I↪ j 2 J↪ k 2 K♦, and R = ¶(bj↪¯bj)↪ (¯bj↪ bj)↪ (¯bj↪¯bj) ♣ j 2 J♦ [ ¶(ck↪ c0k )↪ (c0k ↪ ck)↪ (ck↪ ¯ ck)↪ (¯ ck↪ ¯ ck) ♣ k 2 K♦. We have that Gr(F) = ¶ai ♣ i 2 I♦, Id(F) = Gr(F) [ ¶bj ♣ j 2 J♦, and Eg(F) = Id(F) [ ¶ck ♣ k 2 K♦. Hence, with any of I↪ J↪K possibly empty, it is possible for gr and id, id and eg, or gr and eg to be in arbitrarily extending relationships.

The exact relations now immediately follow.

4.2 Unique vs. Multiple Status Semantics

We begin with the signatures involving naive semantics.

Proof. First observe that clearly for anyAF the σ-extension is conflict-free and thus also contained in some naive extension.

Now take an extension-set T 2 ⌃na, some T 2 T and some S ✓ T as given. Consider the AF F = (A↪R) with A = S T [ ¶x♦ and R = (ConfsT ∩ ¶(b↪ a) ♣ a 2 S↪ b 2 S T ∩ S♦) [ ¶(x↪ x)↪ (x↪ b) ♣ b 2 S T ∩ S♦. It can be shown that na(F ) = T and σ(F ) = ¶S♦.

For the two-dimensional signatures with ⌧ 2 ¶pr↪ sm↪ sb♦ we have the following condition which is more restrictive than with naive semantics (note that T ; = A).

Example 3. Note that (Eg↪ pr) steps out of line here. This is, for instance, witnessed by S = ¶¶a♦♦ and T = ¶¶a♦↪ ¶b♦♦. Despite S 6✓ T T = ; we can realize hS↪ Ti under (eg↪ pr) by the AF (¶a↪ b↪ x♦↪ ¶(a↪ b)↪ (b↪ a)↪ (a↪ x)↪ (x↪ x)♦). In fact, the relaxed condition 9T 2 pr(F) : Eg(F) ✓ T obviously holds for each AF F. However, as we will see in Section 4.5, this is far from a sufficient condition for realizability.

Proposition 3. For σ 2 ¶Gr↪ Id↪ Eg♦, ⌧ 2 ¶pr↪ sm↪ sb♦, (σ↪ ⌧) 6= (Eg↪ pr), σ(F) ✓ T ⌧(F) holds for any F 2 AFA.

The question whether we can select, for σ, an arbitrary subset of the intersection of all ⌧ -extensions has to be tackled differently, depending on the number of ⌧-extensions. We first consider the case when ⌧ provides exactly one extension.

This property does not hold for other σ-⌧-combinations. The following can be derived from Example 2.

Proposition 5. For (σ↪ ⌧) 2 ¶(gr↪ sb)↪ (gr↪ sm)↪ (gr↪ pr)↪ (id↪ sb)↪ (id↪ sm)♦ and arbitrary S ✓ T ✓ A there is an AF F with σ(F) = ¶S♦ and ⌧(F) = ¶T♦.

If ⌧ provides more than one extension, σ can select an arbitrary subset of the arguments occurring in every ⌧-extension.

Lemma 1. Let σ 2 ¶Gr↪ Id↪ Eg♦, ⌧ 2 ¶pr↪ sm↪ sb♦, F = (A↪R) be an AF such that σ(F) = T ⌧(F) and S ✓ σ(F). If ♣⌧(F)♣ > 1 and each a 2 σ(F) defends itself in F, then there exists an AF F 0 with σ(F 0 ) = S and ⌧ (F 0 ) = ⌧ (F ).

Proof. The AF F 0 = (A [ ¶x♦↪R0 ) with R0 = R [ ¶(x↪ x)↪ (x↪ c)↪ (d↪ x) ♣ c 2 σ(F) ∩ S↪ d 2 A ∩ σ(F)♦ provides the required properties.

We are now ready to give the exact signatures with the exception of (eg↪ pr). In order to realize pairs of extension-sets we build upon the canonical frameworks from Section 3.

Theorem 3. Let (σ1↪ ⌧1) 2 ¶(id↪ sm)↪ (gr↪ sm)↪ (gr↪ pr)♦,

Proof. The ✓-direction is by Propositions 3 and 4. The proof of the ◆-direction proceeds as follows: If ♣T♣ > 1 we can take F⌧(T), which has ⌧(F⌧(T)) = T by Proposition 2. Moreover, each argument a 2 T ⌧(F⌧(T)) is unattacked, meaning σ(Fpr(T)) = T ⌧(F⌧ (T)) and a defends itself in F⌧ (T). Therefore we know by Lemma 1 that there is an AF F 0 ⌧ (T) with σ(F 0 ⌧ (T)) = S and ⌧(F 0 ⌧ (T)) = T. If, on the other hand, ♣T♣ = 1, we can realize h¶S♦↪ ¶S♦iσ↪⌧ under (σ3↪ ⌧3) and (eg↪ sb) by the AF (S↪ ;) and get the result for the other σ-⌧-combinations by Proposition 5. Finally, we can realize h¶S♦↪ ;iσ↪sb under (σ↪ sb) by the AF (S [ ¶x♦↪ ¶(x↪ x)♦).

4.3 Multiple Status Semantics

Coming to signatures involving two multiple status semantics we begin with the following result, which is immediate by the basic property that stable and semi-stable extensions coincide in case a stable extension exists.

Stable extensions must always be maximal conflict-free sets, while preferred (resp. semi-stable) extensions can be arbitrary conflict-free sets as long as they are conflict-sensitive.

Theorem 5. Let σ 2 ¶sm↪ pr♦. It holds that

Proof. (na↪ sb): The ✓-direction follows immediately by the fact that for any AF F always sb(F) ✓ na(F). For the ◆- direction let hS↪ Tina↪sb with T ✓ S. We define Fna↪sb(S↪ T) = (A↪ R) with A = S S [ ¶xS ♣ S 2 S ∩ T♦ and R = ConfsS [ ¶(xS↪ xS)↪ (a↪ xS) ♣ S 2 S ∩ T↪ a 2 S S ∩ S♦. As S = bd(S) by S 2 ⌃na, it is clear that na(Fna↪sb(S↪ T)) = S and each

S 2 S attacks each a 2 S S ∩ S. Moreover, all elements of S are incomparable wrt. ✓, therefore each T 2 T attacks each xS with S 2 S ∩ T, hence T 2 sb(Fna↪sb(S↪ T)). Finally, each S 2 S ∩ T does not attack xS, hence S ◁2 sb(Fna↪sb(S↪ T)). We conclude that sb(Fna↪sb(S↪ T)) = T.

(na↪ σ): ✓: Let F 2 AFA. First observe that each S 2 σ(F) is conflict-free, i.e. 9T 2 na(F) s.t. S ✓ T. Now assume σ(F) o na(F) does not hold, witnessed by A↪B 2 σ(F) with 8a 2 A↪ b 2 B : (a↪ b) ◁2 Confs na(F) . But as A and B are admissible then also A[B must be, a contradiction to A and B being (range-)maximal admissible sets. ◆: A pair hS↪ Tina↪σ is realized under (na↪ σ) by the AFs Fna↪pr(S↪ T) = (A↪R) with A = S S [ ¶C 2 ΓT↪a ♣ a 2 Tns ♦ [ ¶x♦ and R = ConfsS [ ¶(C↪C)↪ (C↪ a)↪ (b↪C) ♣ C 2 ΓT↪a↪ b 2 C♦[¶(x↪ x)↪ (x↪ s) ♣ s 2 S S∩S T♦, and Fna↪sm(S↪ T) = (A[ ¯ A↪R[ ¯R) with ¯ A = ¶¯a ♣ a 2 S T♦ and ¯R = ¶(a↪ ¯a)↪ (¯a↪ ¯a) ♣ a 2 S T♦. These are slight modifications of the AF Fpr(T) and Fsm(F) from Definition 3 with the main difference that the attacks among arguments S T are not given by ConfsT but by ConfsS . Thus, we immediately get na(Fna↪pr(S↪ T)) = S. For pr and sm note the role of the arguments C 2 ΓT↪a, as shown in (Dunne et al., 2015): the only admissible sets can be (unions of) elements of T. As ConfsS ✓ ConfsT we get that each T 2 T is admissible in Fna↪σ(S↪ T). Moreover, for T1↪ T2 2 T we know by T o S that there are arguments a1 2 T1 and a2 2 T2 with (a1↪ a2) 2 ConfsS . Hence T1 [ T2 ◁2 ad(Fna↪σ(S↪ T)). Finally, arguments s 2 S S ∩ S T cannot be defended in Fna↪σ(S↪ T) by construction. Therefore the result for pr and sm follows.

Example 4. We illustrate the proof for (na↪ pr) by showing a concrete realization by the AF Fna↪pr. Let S = ¶¶a↪ b↪ d♦↪ ¶a↪ c↪ d♦♦ and T = ¶¶a↪ b♦↪ ¶c♦♦. First note that S 2 ⌃na, T 2 ⌃pr, 8T 2 T9S 2 S : T ✓ S, and T o S hold, hence hS↪ Ti is (na↪ pr)-realizable. We get CNF defense formulas ΓT↪a = ¶¶b♦♦, ΓT↪b = ¶¶a♦♦, and ΓT↪c = ;. The realizing AF Fna↪pr(S↪ T) is depicted in Figure 1, with arguments C 2 ΓT↪z denoted by γz. It is easy to verify that na(Fna↪pr(S↪ T)) = S and pr(Fna↪pr(S↪ T)) = T.

For the two-dimensional signature of stable and preferred semantics we first observe that for any pair hS↪ Ti 2 ⌃sb↪pr it holds that S ✓ T. However, already the fact that ⌃sb ⇢ ⌃pr (Dunne et al., 2015) implies that this condition cannot be sufficient as not all pairs with S = T are realizable under (sb↪ pr). The following example illustrates that stable extensions may only be certain subsets of the preferred extensions.

Example 5. Consider the extension-sets S = ¶¶a↪ d↪ e♦↪ ¶b↪ c↪ e♦↪ ¶c↪ d↪ e♦♦ and T = S [ ¶¶a↪ b♦♦. The pair hS↪ Ti is realized under (sb↪ pr) by the AF F depicted in Figure 2 (without the dotted or dashed parts). However, observe that T 6✓ bd(T) (since ¶a↪ b↪ e♦ 2 bd(T)) and therefore hT↪ Ti is not realizable under (sb↪ pr). In fact, no AF with T as preferred extensions can contain ¶a↪ b♦ as stable extension since

¶a↪ b♦ ◁2 bd(T) cannot achieve full range in such an AF. We can get an arbitrary subset of S under sb though: take AF F 0 in Figure 2 including the dotted part (argument a0 and attacks (a↪ a), (a↪ a0 )). Then, pr(F 0 ) = T and sb(F 0 ) = ¶¶a↪ d↪ e♦♦.

In order to make these ideas formal we first extend the AF Fpr from Definition 3 using techniques from Definition 2.

Definition 5. Given hS↪ Tisb↪pr, Fsb↪pr(S↪ T) is obtained from Fpr(T) with additional arguments ¶xT ♣ T2T∩S♦ and attacks

Intuitively, taking Fpr(T) as a basis ensures that pr(Fsb↪pr(S↪ T)) = T. Moreover, (2) guarantees that each T 2 T also attacks each other argument of Fpr(T). Finally, all T ∩ S are excluded from sb(Fsb↪pr(S↪ T)) by (3).

Proposition 6. For each hS↪ Tisb↪pr such that S ✓ T \ bd(T) it holds that sb(Fsb↪pr(S↪ T)) = S and pr(Fsb↪pr(S↪ T)) = T.

Proof. It can be checked that ad(Fpr(T)) = ad(Fsb↪pr(S↪ T)). Therefore, by pr(Fpr(T)) = T (cf. Proposition 2), pr(Fsb↪pr(S↪ T)) = T follows.

The fact that for stable extensions every argument has a definite status (of in or attacked) together with Propositions 1 and 6 now delivers the following.

It remains to show that sb(Fsb↪pr(S↪ T)) = S. ◆: Let S 2 S. By assumption S 2 T \ bd(T), hence S 2 pr(Fsb↪pr(S↪ T)) and for all a 2 S T ∩ S there is some s 2 S with (a↪ s) 2 ConfsT , meaning that s attacks a in Fsb↪pr(S↪ T). Arguments xT for T 2 T∩S are attacked by S since S 2 T and elements in T are pairwise incomparable, hence there is some a 2 S∩T attacking xT . Finally let C 2 ΓT↪a for an arbitrary a 2 S T. If there is some s 2 S with s 2 C then s attacks C. If S \C = ; it follows, by construction of ΓT↪a, that for all s 2 S, (a↪ s) 2 ConfsT . By (3) now (s↪ C) 2 R. It follows that S has full range in Fsb↪pr(S↪ T), hence S 2 sb(Fsb↪pr(S↪ T)). ✓: Let E 2 sb(Fsb↪pr(S↪ T)). We get E 2 pr(Fsb↪pr(S↪ T)), hence E 2 T. Moreover, as E must have full range, E 2 bd(T). Assuming E ◁2 S means that there is some xE 2 A which is only attacked by the arguments S T ∩ E, a contradiction.

4.4 Conflict-Free and Admissible Sets

So far we have disregarded conflict-free and admissible sets from our analysis. This is because of their close connection to naive and preferred semantics:

By transitivity we get the following signatures.

Theorem 8. For σ 2 ¶gr↪ id↪ eg♦, ⌧ 2 ¶ad↪ sm↪ pr♦,

The ideal extension of an AF is determined by its admissible sets. The crucial point for the signatures ⌃na↪ad and ⌃sb↪ad is the fact that changes to Fpr made by realizations in Theorem 5 and Proposition 6 do not affect the admissible sets.

Theorem 9. It holds that

Interestingly, ⌃gr↪ad cannot be directly obtained from the case of preferred extensions, since certain subsets of T max(T) need to lead to the required grounded extension. Theorem 10. It holds that

◆: Let h¶S♦↪ Tigr↪ad such that S ✓ T max(T) and there is a strict total order < on S s.t. 8s 2 S : ¶s♦ [ ¶s0 2 S ♣ s0 < s♦ 2 T. Define Fgr↪ad(S↪ T) as Fpr(T) with additional argument x and additional attacks ¶(x↪ x)↪ (x↪ c)↪ (c↪ x) ♣ c 2 T max(T) ∩ S♦. We get ad(Fgr↪ad(S↪ T)) = T from Proposition 2 and one can show that also Gr(Fgr↪ad(S↪ T)) = S.

Proof. ✓: Consider AF F = (A↪R). We have Gr(F) ✓ T pr(F) = T max(ad(F)). Gr(F) is the least fixpoint of the monotone characteristic function FF , mapping each set S ✓ A to the set of arguments defended by S. Hence, given some S 2 ad(F), for all S0 ✓ FF (S)∩S also S[S0 2 ad(F). Now let Si be the set of arguments added by the ith application of FF before reaching the fixpoint Gr(F) (beginning with ;). Define the strict total order < such that s < t if s 2 Si, t 2 Sj and i < j and arbitrarily for s↪ t 2 Si. By the observations above, ¶s♦[¶s0 2 S ♣ s0 < s♦ 2 ad(F) for all s 2 S.

4.5 Semi-Stable vs. Preferred Semantics

We now turn to the combination of preferred and semi-stable semantics. It is known that sm(F) ✓ pr(F) for every AF F. Moreover, it follows from Theorem 6 and sb(F) = sm(F) for sb(F) 6= ;, that S ✓ T \ bd(T) is a sufficient condition for realizing hS↪ Ti under (sm↪ pr). However, as the next example illustrates, the exact characterization of ⌃sm↪pr must lie somewhere in between these two conditions.

Example 6. Again consider S and T from Example 5. Obviously the AF F in Figure 2 realizes hS↪ Ti also under (sm↪ pr). But in contrast to before we can now realize hT↪ Ti, namely by the AF F 00 including all dotted or dashed arguments and attacks in Figure 2. It is, however, not possible to have ¶a↪ b♦ as only extension under sm. As it turns out, in any AF G having pr(G) = T, desiring ¶a↪ b♦ 2 sm(G) requires at least two members of S to be semi-stable extensions of G as well.

As a side remark, note that this also means that h¶a↪ b♦↪ Ti ◁2 ⌃eg↪pr. Hence, for realizing pairs h¶S♦↪ T0 ieg↪pr under (eg↪ pr), the fact that 9T 2 T0 : S ✓ T is not sufficient, as already suggested in Example 3.

To argue that the exact characterization turns out to be subtle, we define a stricter form of realizability, where each conflict is given explicitly as an attack in the realizing AF.

Definition 6. A pair of extension-sets hS↪ Ti is naturally realizable under (σ↪ ⌧) if there is an AF F = (A↪R) with σ(F ) = S, ⌧ (F ) = T and R ◆ (ConfsS \ ConfsT ).

Inspecting the canonical constructions in Definitions 2 and 3 and their modifications in the proofs of the theorems, we see that, so far, we only made use of natural realizations.

Proposition 7. For σ↪ ⌧ 2 ¶gr↪ id↪ eg↪ cf↪ ad↪ na↪ sb↪ sm↪ pr♦, (σ↪ ⌧)◁2¶(eg↪ ad)↪ (eg↪ pr)↪ (sm↪ ad)↪ (sm↪ pr)♦, hS↪ Ti is realizable under (σ↪ ⌧) iff it is naturally realizable under (σ↪ ⌧).

The following example witnesses that this is not the case for (sm↪ pr). There are pairs of extension-sets such that any simultaneous realization of these extension-sets under sm and pr must result in some conflicts being implicit, i.e. not represented by an attack. On the one hand this is surprising, as implicit conflicts between non-rejected arguments can be made explicit for preferred and semi-stable semantics on their own. On the other hand it means that for realizing pairs hS↪ Ti under (sm↪ pr) detection of implicit conflicts is a key ingredient.

Example 7. Consider the AF F = (A↪R) as depicted in Figure 3 with arguments bxy↪ cy↪ dy, symmetric 3-cycles over arguments aixy ↪ ui and directed 3-cycles over arguments eixy (i 2 ¶1↪ 2↪ 3♦). Symmetric arrows between regular arguments (or symmetric 3-cycles) and symmetric 3-cycles indicate symmetric attacks between each of the involved arguments. For instance b12 as well as a312 attack and are attacked by u1 ↪ u2 ↪ u3 . Directed arrows between symmetric 3cycles ↵i and directed 3-cycles βi represent attacks (↵i ↪ βj ) for i 6= j. For instance a212 defends e212 by attacking e112 and e312 . Thus aixy is in symmetric attack relationship with bxy and with uj , while eixy can be "activated" by ai1x as well as by ai2y . To capture this activation relationship, in what follows we denote, for S ✓ A, by S" e the union of S and the arguments eixy defended by S in F .

The preferred extensions of F are as follows (with i↪ j↪ k↪ l 2 ¶1↪ 2↪ 3♦ and x 6= y↪ x0 6= y0 2 ¶1↪ 2♦):

Observe that E+ u = E+ a ⇢ E+ ab and E+ b is incomparable to E+ ab , hence sm(F) only consists of Eab and Eb. Note that Eb misses some eixy in range, while Eab misses some dx in range; thus any realization of hsm(F)↪ pr(F)i has some eixy ◁2 E+ b and dx ◁2 E+ ab as members of pr(F ) must be conflict-free.

Now observe that the ui never occur together with dx in any semi-stable or preferred extension, a so called implicit conflict. Naturally realizing hsm(F)↪ pr(F)i has to make all implicit conflicts symmetrically explicit, in this case by adding attacks (ui ↪ dx)↪ (dx↪ ui ). But then we get dx↪ eixy 2 E+ u for x↪ y 2 ¶1↪ 2♦↪ i 2 ¶1↪ 2↪ 3♦ and thus E+ u contains or is at least incomparable to E+ ab and E+ b , whichmeans that Eu cannot be excluded from the semi-stable extensions.

We can state the following result, leaving the exact characterization of ⌃sm↪pr (as well as for ⌃eg↪pr, ⌃sm↪ad and ⌃eg↪ad where we anticipate similar issues) for future work.

Proposition 8. There exist hS↪ Ti 2 ⌃sm↪pr which are not naturally realizable under (sm↪ pr).

5 Discussion

In this paper, we have given a full characterization of all but four two-dimensional signatures for the semantics of conflict-free, admissible, naive, stable, preferred, semi-stable, grounded, ideal, and eager extensions. Two prominent semantics are missing: complete semantics, as its exact (onedimensional) signature is not established yet. Stage semantics has been treated in (Dunne et al., 2015), but turns out to behave quite differently when combined with other semantics. We leave them together with investigations on labelling-based semantics (Caminada and Gabbay, 2009) for future work.

Understanding two-dimensional signatures gives further insights about the relationship between semantics, but also yields practical implications. For example, when enumerating preferred extensions, we may start with computing the less complex stable semantics. Assume we have found ¶a↪ b♦ and some S [ ¶a♦ as stable (and therefore also preferred) extensions. By Theorem 6 we can now exclude any S0 [ ¶b♦ with S \ S0 6= ; from the search-space, even if it could still be compatible with ⌃pr. We envisage to investigate implications of this kind on a more general level.

Another natural issue for future work is to extend the results to n-dimensional signatures. Some of our results already provide such characterizations; for instance, Example 2 readily delivers the 3-dimensional signature ⌃gr↪id↪eg, but for other combinations the picture is not clear yet. The research on multi-dimensional signatures is by no ways limited to argumentation. We plan to apply our method also to the world of logic programming in order to compare stable, well-founded, and supported semantics (Gelfond and Lifschitz, 1988; Van Gelder et al., 1988; Clark, 1978) in a similar vein. For instance, understanding to which extent supported and stable models can diverge for a program might lead to shortcuts in the loop-formula approach (Lin and Zhao, 2004) for computing stable models.

Acknowledgements This research has been supported by the Austrian Science Fund (FWF) through projects I1102 and P25521.