Proceedings of the KI 2015 Workshop on Formal and Cognitive Reasoning On the Functional Completeness of Argumentation Semantics� Massimiliano Giacomin1 , Thomas Linsbichler2 , and Stefan Woltran2 1 University of Brescia, Italy 2 TU Wien, Austria Abstract. Abstract argumentation frameworks (AFs) are one of the central formalisms in AI; equipped with a wide range of semantics, they have proven useful in several application domains. We contribute to the systematic analysis of semantics for AFs by connecting two recent lines of research – the work on input/output frameworks and the study of the expressiveness of semantics. We do so by considering the following ques- tion: given a function describing an input/output behaviour by mapping extensions (resp. labellings) to sets of extensions (resp. labellings), is there an AF with designated input and output arguments realizing this function under a given semantics? For the major semantics we give exact characterizations of the functions which are realizable in this manner. 1 Introduction Dung’s argumentation frameworks (afs) have been extensively investigated, mainly because they represent an abstract model unifying a large variety of specific formalisms ranging from nonmonotonic reasoning to logic programming and game theory [9]. After the development and analysis of different semantics [13, 6, 2], recent attention has been drawn to their expressive power, i.e. deter- mining which sets of extensions [10] and labellings [11] can be enforced in a single af under a given semantics. Such results have recently been facilitated in order to express AGM-based revision in the context of abstract argumentation [8]. In [1], it has been shown that an af can be viewed as a set of partial in- teracting sub-frameworks each characterized by an input/output behavior, i.e. a semantics-dependent function which maps each labelling of the “input” ar- guments (the external arguments affecting the sub-framework) into the set of labellings prescribed for the “output” arguments (the arguments of the sub- framework affecting the external ones). It turns out that under the major seman- tics, i.e. complete, grounded, stable and (under some mild conditions) preferred semantics, sub-frameworks with the same input/output behavior can be safely exchanged, i.e. replacing a sub-framework with an equivalent one does not affect the justification status of the invariant arguments: semantics of this kind are called transparent [1]. � This research has been supported by the Austrian Science Fund (FWF) through projects I1102 and P25521. 43 Proceedings of the KI 2015 Workshop on Formal and Cognitive Reasoning Then, somewhat resembling functional completeness of a specific set of logic gates, a natural question concerns the expressive power of transparent semantics in the context of an interacting sub-framework: given a so-called I/O specifica- tion, i.e. a function describing an input/output behaviour by mapping extensions (resp. labellings) to sets of extensions (resp. labellings), is there an af with designated input and output arguments realizing this function under a given semantics? In this paper, we answer this question as follows: – For the stable, preferred, semi-stable, stage, complete, ideal, and grounded semantics we exactly characterize all realizable two-valued I/O specifications. – For the preferred and grounded labellings we exactly characterize all realiz- able three-valued I/O specifications. Answering this question is essential in many aspects. First, it adds to the analysis and comparison of semantics (see e.g. [5, 3]), by providing an absolute characterization of their functional expressiveness, which holds independently of how the abstract argumentation framework is instantiated. Second, it lays foundations towards a theory of dynamic and modular argumentation. More specifically, a functional characterization provides a common ground for dif- ferent representations of the same sub-framework, e.g. to devise a summarized version of a sub-framework, or to give an argumentation-based view of the same framework at different levels of abstraction, as in metalevel argumentation [12]. One may also translate a different formalism to an af or vice versa, or provide an argument-free representation of a given af for human/computer interaction issues: in all of these cases, it is important to know whether an input/output be- havior is realizable under a given argumentation semantics. Finally, our results are important in the dynamic setting of strategic argumentation, where a player may exploit the fact that for some set of arguments certain labellings are achiev- able (or non achievable) independently of the labelling of other arguments, or more generally she/he may exploit knowledge on the set of realizable dependen- cies. For example, an agent may desire to achieve some goal, i.e., ensure that a certain argument is justified. Considering arguments brought up by other agents as input arguments, our results enable to verify whether the goal is achievable and provide one particular way for the agent to bring up further arguments in order to succeed. The paper is organized as follows. After providing the necessary background in Section 2, Section 3 introduces the notion of I/O-gadget to represent a sub- framework, and tackles the above problem with extension-based two-valued spec- ifications. Labelling-based three-valued specifications are investigated in Sec- tion 4 and Section 5 concludes the paper. 2 Background We assume a countably infinite domain of arguments A. An argumentation framework (af) is a pair F = (A, R) where A ⊆ A and R ⊆ A × A. We assume that A is non-empty and finite. For an af F = (A, R) and a set of arguments 44 Proceedings of the KI 2015 Workshop on Formal and Cognitive Reasoning S ⊆ A, we define SF+ = {a ∈ A | ∃s ∈ S : (s, a) ∈ R}, SF⊕ = S ∪ SF+ , and SF− = {a ∈ A | ∃s ∈ S : (a, s) ∈ R}. Given F = (A, R), a set S ⊆ A is conflict-free (in F ), if there are no ar- guments a, b ∈ S : (a, b) ∈ R. An argument a ∈ A is defended (in F ) by a set S ⊆ A if ∀b ∈ A : (b, a) ∈ R ⇒ b ∈ SF+ . A set S ⊆ A is admissible (in F ) if it is conflict-free and defends all of its elements. We denote the set of conflict-free and admissible sets in F as cf(F ) and ad(F ), respectively. An extension-based semantics σ associates to any F = (A, R) the (possibly empty) set σ(F ) including subsets of A called σ-extensions. In this paper we focus on complete, grounded, preferred, ideal, stable, stage and semi-stable semantics, with extensions defined as follows: – S ∈ co(F ) iff S ∈ ad(F ) and a ∈ S for all a ∈ A defended by S; – S ∈ gr(F ) iff S is the least element in co(F ); – S ∈ pr(F ) iff S ∈ ad(F ) and �T� ∈ ad(F ) s.t. T ⊃ S; � – S ∈ id(F ) iff S ∈ ad(F ), S ⊆ pr(F ) and �T ∈ ad(F ) s.t. T ⊆ pr(F ) and T ⊃ S; – S ∈ st(F ) iff S ∈ cf(F ) and SF⊕ = A; – S ∈ sg(F ) iff S ∈ cf(F ) and �T ∈ cf(F ) s.t. TF⊕ ⊃ SF⊕ ; – S ∈ se(F ) iff S ∈ ad(F ) and �T ∈ ad(F ) s.t. TF⊕ ⊃ SF⊕ . Given F = (A, R) and a set O ⊆ A, the restriction of σ(F ) to O, denoted as σ(F )|O , is the set {E ∩ O | E ∈ σ(F )}. Given a set of arguments A, a labelling L is a function assigning each ar- gument a ∈ A exactly one label among t, f and u, i.e. L : A �→ {t, f, u}. If the arguments A = {a1 , . . . , an } are ordered, then we denote a labelling of A as a sequence of labels, e.g. the labelling tuf of arguments {a1 , a2 , a3 } maps a1 to t, a2 to u, and a3 to f. We denote the set of all possible labellings of A as L(A). Likewise, given an af F , we denote the set of all possible labellings of (the arguments of) F as L(F ). Given a labelling L and an argument a, L(a) denotes the labelling of a wrt. L; finally in(L), out(L), and undec(L) denotes the arguments labeled to t, f, and u by L, respectively. Definition 1. Given a set of arguments A and labellings L1 , L2 thereof, L1 � L2 iff in(L1 ) ⊆ in(L2 ) and out(L1 ) ⊆ out(L2 ). Moreover we call L1 and L2 – comparable if L1 � L2 or L2 � L1 – compatible if in(L1 ) ∩ out(L2 ) = out(L1 ) ∩ in(L2 ) = ∅ Note that if L1 and L2 are comparable then they are also compatible. An argumentation semantics can be defined in terms of labellings rather than of extensions, i.e. the labelling-based version of a semantics σ associates to F a set Lσ (F ) ⊆ L(F ), where any labelling L ∈ Lσ (F ) corresponds to an extension S ∈ σ(F ) as follows: an argument a ∈ A is labeled to t iff a ∈ S, is labeled to f iff a ∈ SF+ , is labeled to u if neither of the above conditions holds. Given F and a set O ⊆ A, the restriction of Lσ (F ) to O, denoted as Lσ (F )|O , is the set {L ∩ (O × {t, f, u}) | L ∈ Lσ (F )}. The following well-known result can be deduced e.g. from the semantics account given in [7]. Proposition 1. For an af F , Lpr (F ) = max� (Lco (F )). 45 Proceedings of the KI 2015 Workshop on Formal and Cognitive Reasoning 3 Extension-based I/O-gadgets An I/O-gadget represents a (partial) af where two sets of arguments are identi- fied as input and output arguments, respectively, with the restriction that input arguments do not have any ingoing attacks. Definition 2. Given a set of input arguments I ⊆ A and a set of output argu- ments O ⊆ A with I ∩ O = ∅, an I/O-gadget is an af F = (A, R) such that I, O ⊆ A and IF− = ∅. The injection of a set J ⊆ I to F simulates the input J in the way that all arguments in J are accepted (none of them has ingoing attacks since F is an I/O-gadget) and all arguments in (I \ J) are rejected (each of them is attacked by the newly introduced argument z, which has no ingoing attacks). Definition 3. Given an I/O-gadget F = (A, R) and a set of arguments J ⊆ I, the injection of J to F is the af �(F, J) = (A ∪ {z}, R ∪ {(z, i) | i ∈ (I \ J)}), where z is a newly introduced argument. An I/O-specification describes a desired input/output behaviour by assigning to each set of input arguments a set of sets of output arguments. Definition 4. A two-valued3 I/O-specification consists of two sets I, O ⊆ A O and a total function f : 2I �→ 22 . In order for an I/O-gadget F to satisfy f, the injection of each J ⊆ I to F must have f(J) as its σ-extensions restricted to the output arguments. So, informally, with input J applied the set of outputs under σ should be exactly f(J). Definition 5. Given I, O ⊆ A, a semantics σ and an I/O-specification f, the I/O-gadget F satisfies f under σ iff ∀J ⊆ I : σ(�(F, J))|O = f(J). The question we want to address is which conditions f must fulfill to be satis- fiable by some I/O-gadget and how an I/O-gadget doing so can be constructed. Definition 6. Given an I/O-specification f, let Y = {yi | i ∈ I} and X = {xSJ | J ⊆ I, S ∈ f(J)}. The canonical I/O-gadget is defined as C(f) = (I ∪ O ∪ Y ∪ X ∪ {w}, {(i, yi ) | i ∈ I}∪ {(yi , xSJ ) | xSJ ∈ X, i ∈ J}∪ {(i, xSJ ) | xSJ ∈ X, i ∈ (I \ J)}∪ {(x1 , x2 ) | x1 , x2 ∈ X, x1 �= x2 }∪ {(xi , w) | xi ∈ X} ∪ {(w, w)}∪ {(xSJ , o) | J ⊆ I, S ∈ f(J), o ∈ (O \ S)}). 3 In the following we omit this specification. 46 Proceedings of the KI 2015 Workshop on Formal and Cognitive Reasoning Intuitively, xSJ shall enforce output S for input J. Moreover, w ensures that any stable extension of (an injection to) C(f) must contain an argument in X. The following theorem shows that any I/O-specification is satisfiable under stable semantics. Theorem 1. Every I/O-specification f is satisfied by C(f) under st. Proof. Let I, O ⊆ A and f be an arbitrary I/O-specification. We have to show that st(�(C(f), J))|O = f(J) holds for any J ⊆ I. Consider such a J ⊆ I. First let S ∈ f(J). We show that E = {z} ∪ J ∪ {yi | i ∈ (I \ J)} ∪ {xSJ } ∪ S ∈ st(�(C(f), J)), thus S ∈ st(�(C(f), J))|O . E is conflict-free in �(C(f), J) since z only attacks the arguments (I \ J), an yi with i ∈ (I \ J) is only attacked by i∈/ E, xSJ is only attacked by other x ∈ X, i ∈ (I \ J) and yj with j ∈ J, and arguments in S are only attacked by arguments from X but not from xSJ . E is stable in �(C(f), J) since xSJ attacks w, all other x ∈ X and all o ∈ (O \ S); z attacks all i ∈ (I \ J); each yj with j ∈ J is attacked by j. It remains to show that there is no S � ∈ st(�(C(f), J))|O with S � ∈ / f(J). Towards a contradiction assume there is some S � ∈ st(�(C(f), J))|O with S � ∈ / f(J). Hence there must be some E � ∈ st(�(C(f), J)) with S � ⊂ E � . Since w attacks � itself, w ∈/ E � , thus by construction of C(f) there must be some xSJ � ∈ (X ∩ E � ) � attacking w, and xSJ � must attack all o ∈ (O \S � ). Since S � ∈/ f(J) by assumption, it must hold that J � �= J. Now note that z ∈ E � and j ∈ E � for all j ∈ J, since they are not attacked by construction of �(C(f), J). Now if J � ⊂ J then there is � some j ∈ (J \ J � ) attacking xSJ � , a contradiction to conflict-freeness of E � . On the other hand if J �⊆ J there is some j � ∈ (J � \ J) which is attacked by z. Therefore � � also yj � ∈ E � , which attacks xSJ � , again a contradiction. � As to stage, preferred and semi-stable semantics, any I/O-specification is satisfiable, provided that a (possibly empty) output is prescribed for any input. Proposition 2. Every I/O-specification f such that ∀J ⊆ I, f(J) �= ∅ is satisfied by C(f) under σ ∈ {sg, pr, se}. Proof (Sketch). Note that ∀J ⊆ I, stable, preferred, stage and semi-stable ex- tensions coincide in �(C(f), J), thus the result follows from Theorem 1. � Theorem 2. An I/O-specification f is satisfiable under σ ∈ {sg, pr, se} iff ∀J ⊆ I, f(J) �= ∅. Proof. ⇐: by Proposition 2. ⇒: Follows directly by the fact that in any af, particularly in any injection of some extension to an I/O-gadget, a σ-extension always exists. � Example 1. Consider the I/O-specification f with I = {i, j} and O = {o, p, q} defined as follows: f(∅) = {∅}; f({i}) = {{o, q}}; f({j}) = {{o, p, q}, {p, q}}; and f({i, j}) = {{o, p, q}, {o, p}}. The canonical I/O-gadget C(f) is depicted below4 (without the dotted part): 4 {c,d} Argument names such as x{a,b} are abbreviated by xcd ab . 47 Proceedings of the KI 2015 Workshop on Formal and Cognitive Reasoning j yj yi i z xop ij xopq ij x∅∅ xoq i xpq j xopq j w q p o Let σ be a semantics in {st, sg, se, pr}. One can verify that for every possible input J ⊆ I, the injection of J to C(f), has exactly f(J) as σ-extensions restricted to O. As an example let J = {j}. �(C(f), {j}) adds the argument z attacking {p,q} {o,p,q} i to C(f). Now σ(�(C(f), {j})) = {{z, j, yi , x{j} , p, q}, {z, j, yi , x{j} , o, p, q}}, hence σ(�(C(f), {j}))|O = {{p, q}, {o, p, q}} = f({j}). Also for complete, grounded and ideal semantics we are able to identify a necessary and sufficient condition for satisfiability. While we show sufficiency of these conditions in more detail, their necessity is by the well-known facts that the intersection of all complete extensions is always a complete extension too and ideal and grounded semantics always yield exactly one extension. Definition 7.� An I/O-specification f is closed iff for each J ⊆ I it holds that f(J) �= ∅ and f(J) ∈ f(J). Proposition 3. Every closed I/O-specification f is satisfied by C(f) under co. Proof. Let J ⊆ I and S = f(J). By construction of �(C(f), J), E ∗ = {z} ∪ J ∪ {yi | i ∈ (I \ J)} is contained in all complete extensions, while the elements of (I \ J) ∪ {yi | i ∈ J} are attacked by E ∗ and thus by all complete extensions. � All xSJ � with J � �= J are attacked by J or some yi with i ∈ (I \ J), thus they are attacked by E ∗ , while all xSJ with S ∈ S attack each other and the other attacks they receive come from elements attacked by E ∗ in turn. Two cases can then be distinguished. If |S| = 1 then by construction of �(C(f), J) there is just one xSJ defended by E ∗ , thus the only complete extension is E ∗ ∪ {xSJ } ∪ S. If, on the other hand, |S| > 1, any xSJ with S ∈ S can be included, giving rise to the complete extension E ∗ ∪ {xSJ� } ∪ S, or none of xSJ can be included, giving rise to the complete � extension E ∪ S since an xSJ attacks all o ∈ (O \ S). Taking into ∗ account that S ∈ S, in both cases we have that co(�(F, J))|O = f(J). � Theorem 3. An I/O-specification f is satisfiable under co iff f is closed. Proposition 4. Every I/O-specification f with |f(J)| = 1 for each J ⊆ I is satisfied by C(f) under gr and id. Proof (Sketch). This follows the same idea as the proof of Proposition 3. Since |f(J)| = 1, �(C(f), J) has only one complete extension for each J ⊆ I, which is also grounded and ideal. � Theorem 4. An I/O-specification f is satisfiable under gr and id iff |f(J)| = 1 for each J ⊆ I. 48 Proceedings of the KI 2015 Workshop on Formal and Cognitive Reasoning 4 Labelling-based I/O-gadgets In the previous section we have dealt with I/O-specifications mapping extensions to sets of extensions. In general, there are two reasons why an argument does not belong to an extension, i.e. either because it is attacked by the extension or because it is undecided due to insufficient justification. This distinction impacts on the justification status of arguments, since attacks from undecided arguments can prevent attacked arguments to belong to an extension, while attacks from out arguments are ineffective. In order to take into account this distinction, we first provide a labelling-based counterpart of the notions introduced in Section 3. Definition 8. A 3-valued I/O-specification consists of two sets I, O ⊆ A and a total function f : L(I) �→ 2L(O) . Definition 9. Given an I/O-gadget F = (A, R) and a labelling L of I, the labelling-injection of L to F is the af �(F, L) = (A ∪ {z}, R ∪ {(z, a) | L(a) = f} ∪ {(b, b) | L(b) = u}), where z is a newly introduced argument. Definition 10. Given I, O ⊆ A, a semantics σ and a 3-valued I/O-specification f, the I/O-gadget F satisfies f under σ iff ∀L ∈ L(I) : Lσ (�(F, L))|O = f(L). By definition of stable labellings it is clear that in order to be satisfied under st, a 3-valued I/O-specification must only be non-empty for labellings with each argument labeled to t or f. Theorem 5. A 3-valued I/O-specification f is satisfiable under st iff for each L ∈ L(I) it holds that – if ∃i ∈ I : L(i) = u then f(L) = ∅, and – otherwise K(o) �= u for all K ∈ f(L) and o ∈ O. Proof. ⇒: If ∃i ∈ I : L(i) = u then for any I/O-gadget F , �(F, L) contains a self-attacking argument otherwise unattacked, hence Lst (�(F, L)) = ∅. In the other case, by definition of stable extension it is clear that each o ∈ O must be labelled either t or f by any stable labelling. ⇐: Follows from Theorem 1. If ∃i ∈ I : L(i) = u then st(�(C(f), L)) = ∅, otherwise the labelling-injection coincides with the normal injection. � In order to characterize those 3-valued I/O-specifications which are satisfi- able under the other semantics we need the concept of monotonicity. Definition 11. A 3-valued I/O-specification f is monotonic iff for all L1 and L2 such that L1 � L2 it holds that ∀K1 ∈ f(L1 )∃K2 ∈ f(L2 ) : K1 � K2 . The intuitive meaning of monotonicity is the following: if K1 is an output for input L1 , then for every input which is more informative than L1 there must be an output more informative than K1 . First a rather obvious observation: Proposition 5. For every 3-valued I/O-specification f which is satisfiable under gr, |f(L)| = 1 for all L ∈ L(I). 49 Proceedings of the KI 2015 Workshop on Formal and Cognitive Reasoning The following was shown in Proposition 7 of [1] for complete semantics. Proposition 6. Every 3-valued I/O-specification which is satisfiable under {gr, pr} is monotonic. Proof (Sketch). Let f be a 3-valued I/O-specification and suppose it is satisfied by the I/O-gadget F under gr. Moreover let L1 � L2 be labellings of I. Proposi- tion 7 of [1] says that ∀K2 ∈ Lco (�(F, L2 ))|O ∃K1 ∈ Lco (�(F, L1 ))|O : K1 � K2 and ∀K1 ∈ Lco (�(F, L1 ))|O ∃K2 ∈ Lco (�(F, L2 ))|O : K1 � K2 . By the facts that |f(L1 )|=|f(L2 )|=1 (cf. Proposition 5) and Lpr (F ) = max� (Lco (F )) for each AF F (cf. Proposition 1), the result follows for gr and pr, respectively. � In Propositions 5 and 6 we have given necessary conditions for 3-valued I/O- specifications to be satisfiable under gr and pr. In the following we show that these conditions are also sufficient in the sense that we can find a satisfying I/O-gadget. The constructions of these I/O-gadgets will depend on the given 3-valued I/O-specification and on the semantics, but they will share the same input and output part. The semantics-specific part, denoted by Xfσ and Rfσ in the following definition, will be given later. Definition 12. Given a 3-valued I/O-specification f we define I � = {i� | i ∈ I}, O� = {o� | o ∈ O}, RI = {(i, i� ) | i ∈ I} and RO = {(o� , o� ), (o� , o) | o ∈ O}. The 3-valued canonical I/O-gadget for semantics σ is defined as Dσf = (I ∪ I � ∪ Xfσ ∪ O� ∪ O, RI ∪ Rfσ ∪ RO ). with Rfσ ⊆ ((I ∪ I � ) × Xfσ ) ∪ (Xfσ × Xfσ ) ∪ (Xfσ × (O� ∪ O)). Now we turn to the semantics-specific constructions. For grounded semantics we need the concept of determining input labellings. An input labelling L is determining for output argument o if L is a minimal (w.r.t. �) input labelling where o gets a concrete value (t or f) according to f. With abuse of notation, in the following we may identify a set including a single labelling with the labelling itself. Definition 13. Given a 3-valued I/O-specification f with |f(L)| = 1 for all L ∈ L(I) and an argument o ∈ O, a labelling L of I is determining for o, if f(L)(o) �= u and ∀L� � L : f(L� )(o) = u. We denote the set of labellings which are determining for o as df (o). Example 2. Let f be the following 3-valued I/O-specification with I = {i1 , i2 } and O = {o1 , o2 }: f(uu) = {uu}; f(tu) = {tu}; f(ut) = {ut}; f(uf) = {uf}; f(fu) = {uu}; f(tt) = {tt}; f(tf) = {tf}; f(ft) = {ut}; and f(ff) = {tf} We have the following sets of determining labellings: df (o1 ) = {tu, ff} and df (o2 ) = {ut, uf}. Consider, for instance, the input labelling ff. We have f(ff) = tf. In order to check if ff is determining for o1 we have to look at all input labellings being less committed than ff. Now we observe f(uf) = uf, f(fu) = f(uu) = uu. In all of these desired output labellings o1 has value u, so ff is determining for o1 . On the other hand ff is not determining for o2 , since f(uf)(o2 ) = f. 50 Proceedings of the KI 2015 Workshop on Formal and Cognitive Reasoning Definition 14. Given a 3-valued I/O-specification f with |f(L)=1| for all L ∈ L(I), the gr-specific part of Dgr f is given by Xfgr ={xL o | o ∈ O, L ∈ df (o)}, and Rfgr ={(i, xL L gr � L L gr o ) | xo ∈ Xf , L(i) = f} ∪ {(i , xo ) | xo ∈ Xf , L(i) = t}∪ � gr gr {(xL L L L o , o ) | xo ∈ Xf , f(L)(o) = t} ∪ {(xo , o) | xo ∈ Xf , f(L)(o) = f}. For every o ∈ O and each labelling L which is determining for o, there is the argument xL o . This argument can be labelled t if L is the labelling of I and intuitively enforces the labelling of o to be as given by f(L) . The next results, requiring two preliminary lemmata, characterize satisfiabil- ity of grounded semantics. Lemma 1. Let f be a 3-valued I/O-specification which is monotonic and s.t. |f(L)| = 1 for each L ∈ L(I). Let o ∈ O and L, L� ∈ L(I) such that f(L)(o) = t and f(L� )(o) = f. Then L and L� are not compatible. Lemma 2. Given a 3-valued I/O-specification f which is monotonic and s.t. |f(L)| = 1 for each L ∈ L(I), let o ∈ O and L, L� ∈ L(I) such that L is determining for o. Then Lgr (�(Dgr � L f , L ))(xo ) is – t iff L � L� ; – f iff L and L� are not compatible; and – u iff L �� L� but L and L� are compatible. Proposition 7. Every 3-valued I/O-specification f which is monotonic and s.t. |f(L)| = 1 for each L ∈ L(I), is satisfied by Dgr f under gr. Proof. Consider some input labelling L. We have to show Lgr (�(Dgr f , L))|O = f(L). To this end let o ∈ O. Assume f(L)(o) = u. Then, since f is monotonic, f(L� )(o) = u for all L� � L. Therefore, there is no L� � L with L� ∈ df (o). By Lemma 2 we get that for all L�� L�� L�� ∈ df (o) it holds that Lgr (�(Dgrf , L))(xo ) �= t. Since such xo are the only gr potential attackers of o and o� , Lgr (�(Df , L))(o) = u. Next assume f(L)(o) = t. Then there is some L� � L with L� ∈ df (o) and L� L� f(L� )(o) = t. By Lemma 2 we get Lgr (�(Dgr f , L))(xo ) = t. Moreover, xo attacks o� , hence Lgr (�(Dgr � f , K))(o ) = f. Towards a contradiction assume there is some L�� L�� xo attacking o with Lgr (�(Dgr f , L))(xo ) ∈ {t, u}. Then, by Lemma 2, L and �� gr L are compatible. However, by construction of Df , f(L�� )(o) = f, f(L)(o) = t and, by Lemma 1 L�� and L are not compatible. Finally assume f(L)(o) = f. Then there is some L� � L with L� ∈ df (o) L� L� and f(L� )(o) = f. By Lemma 2 we get Lgr (�(Dgr f , L))(xo ) = t. Moreover, xo attacks o, hence Lgr (�(Dgr f , L))(o) = f. � Example 3. Again consider the 3-valued I/O-specification f from Example 2. We have seen the determining labellings there. The I/O-gadget Dgr f is depicted be- gr low. Consider for example the labelling-injection of fu to Df , which is indicated 51 Proceedings of the KI 2015 Workshop on Formal and Cognitive Reasoning by the dotted part of the figure. We get Lgr (�(Dgr f , fu))|O = uu, satisfying the I/O-specification. One can check that this holds for all possible labelling-injec- tions, hence Dgr f satisfies f under the grounded semantics. z i1 i�1 i�2 i2 xtu o1 xut o2 xuf o2 xff o1 o1 o�1 o�2 o2 Theorem 6. A 3-valued I/O-specification f is satisfiable under gr iff f is mono- tonic and for each L ∈ L(I), |f(L)| = 1. Definition 15. Given a 3-valued I/O-specification f, the pr-specific part of Dpr f is given by Xfpr ={xL K | L ∈ L(I), K ∈ f(L)}, and Rfpr ={(i, xL L pr � L L pr K ) | xK ∈ Xf , L(i) = f} ∪ {(i , xK ) | xK ∈ Xf , L(i) = t}∪ � pr pr {(xL L L L K , o ) | xK ∈ Xf , K(o) = t} ∪ {(xK , o) | xK ∈ Xf , K(o) = f}∪ � � � � � {(xL L K , xK � ) | ¬(L�L ∧K�K ) ∧ ¬(L�L ∧K�K )}. Every input-output-combination is represented by an argument in Dpr f . We first show a technical lemma, giving sufficient conditions on the labelling-status of the arguments in Xfpr to get the desired labelling of the output arguments. Lemma 3. Given a 3-valued I/O-specification f and an input labelling L ∈ L(I). The following holds for each preferred labelling P of �(Dpr L f , L): If P (xK ) = � pr � K � ∈ Xf , K � K ⇒ P (xK � ) �= t and (K �� K ∧ K �� K ) ⇒ � � � t and for all xL L L� P (xK � ) = f, then P |O = K. We proceed by showing that Dpr satisfies every monotonic function under the preferred semantics. Proposition 8. Every 3-valued I/O-specification f which is monotonic is sat- isfied by Dpr f under pr. Proof. Consider an arbitrary input labelling L ∈ L(I). We have to show that Lpr (�(Dpr f , L))|O = f(L). � pr � Similar to Lemma 2 one can check that those xL K � ∈ Xf with L � L are pr pr the only arguments in Xf which can be t in a preferred labelling of �(Df , L). pr Now the arguments xL K with K ∈ f(L) form a clique in �(Df , L). Moreover each of these xK defends itself, hence there is a preferred labelling of �(Dpr L f , L) L for each K ∈ f(L) identified by xK . Let PK be the preferred labelling with 52 Proceedings of the KI 2015 Workshop on Formal and Cognitive Reasoning � � � PK (xL L K ) = t where K ∈ f(L). All xK � with K ��K ∧ K ��K are attacked by xL , K L� L� hence PK (xK � ) = f. Assume K � K. If L �� L, then xK � is again attacked by � � L� L� L and PK (xK � ) = f. If L � L, PK (xK � ) �= t since it is attacked by some i or � xK � i (i ∈ I) which is u in PK . Therefore, by Lemma 3, PK |O = K. It remains to show that there is no other preferred labelling besides these PK with K ∈ f(L). Towards a contradiction, assume that there is a preferred labelling P � where no xL K with K ∈ f(L) is t. By our initial considerations, those � xLK � with L � � L are the only x-arguments which can be t in P � . It cannot be the case that none of them is t, since P � would not be preferred. Then there is at � K � which is t in P , with L � L, and without loss of generality we can � � least an xL L�� assume that there is no xK �� which is t and L� � L�� . Now, since f is monotonic there has to be a K ∈ f(L) such that K � � K. We prove that no x-argument � attacking xL K is t in P . �� K �� with L � L. Note �� First, the only x-arguments that can be t are those xL � K � does not attack xK , since L � L∧K � K. � � that, according to Definition 15, xL L L�� L� If an attacker xK �� is attacked in turn by xK � then it is f, otherwise either L�� � L� ∧ K �� � K � or L� � L�� ∧ K � � K �� . The first case is impossible, since we �� would have L�� � L ∧ K �� � K, entailing that xL L K �� does not attack xK . In the � L L�� other case, by the assumption on xK � it holds that xK �� is not t. Now, xL K defends itself against all x-arguments and none of them is t, more- over by construction of �(Dpr � f , L), all attackers from I and I are f. But then, �� � L consider the labelling P obtained from P by assigning to xK the label t, and �� � �� by assigning to all the attackers of xL K the label f. P is admissible and P � P , � contradicting the maximality of P . � Theorem 7. A 3-valued I/O-specification f is satisfiable under pr iff f is mono- tonic. As to remaining semantics, note that Propositions 7 and 8 apply to ideal and semi-stable semantics, respectively, since for each L the grounded labelling of �(Dgrf , L) coincides with the ideal labelling, and the preferred labellings of pr �(Df , L) coincide with semi-stable labellings. However, this does not allow to derive a complete characterization, since there are non-monotonic 3-valued I/O- specifications, satisfiable by ideal and semi-stable semantics, respectively. 5 Conclusions To the best of our knowledge, this is the first characterization of the input/output expressive power of argumentation semantics. In [10], expressiveness has been studied as the capability of enforcing sets of extensions. The problem faced in this paper differs in two aspects: on the one hand, we have to enforce a set of extensions for any input rather than a single set of extensions, on the other hand we can exploit non-output arguments that are not seen outside a sub- framework. Moreover we also consider labellings besides extensions. A labelling- based investigation exploiting hidden arguments is carried out in [11], but still in the context of an ordinary af rather than an I/O-gadget. 53 Proceedings of the KI 2015 Workshop on Formal and Cognitive Reasoning We restricted our considerations to total I/O-specifications, where the output is defined for each input. One can also think of situations where we do not care about the output for some inputs, i.e. the interest lies in the satisfiability of a partial function. We did not tackle these issues here, but plan to do so as part of future work. Further future work includes the 3-valued I/O-characterization of complete semantics, being the only transparent semantics [1] for which this was left open. Moreover, the investigation of further semantics such as CF2 [4] would be of interest. Another issue is the construction of I/O-gadgets from compact I/O- specifications where the function is not explicitly stated but, for instance, de- scribed as a Boolean (or three-valued) circuit. We conjecture that I/O-gadgets can then be composed from simple building blocks along the lines of the given circuit. A related question in this direction is the identification of minimal I/O- gadgets satisfying a given specification. References 1. Baroni, P., Boella, G., Cerutti, F., Giacomin, M., van der Torre, L., Villata, S.: On the Input/Output behaviour of argumentation frameworks. Artif. Intell. 217, 144–197 (2014) 2. Baroni, P., Caminada, M., Giacomin, M.: An introduction to argumentation se- mantics. Knowledge Engineering Review 26(4), 365–410 (2011) 3. Baroni, P., Giacomin, M.: On principle-based evaluation of extension-based argu- mentation semantics. Artif. Intell. 171(10-15), 675–700 (2007) 4. Baroni, P., Giacomin, M., Guida, G.: SCC-Recursiveness: A general schema for argumentation semantics. Artif. Intell. 168(1-2), 162–210 (2005) 5. Caminada, M., Amgoud, L.: On the evaluation of argumentation formalisms. Artif. Intell. 171(5-6), 286–310 (2007) 6. Caminada, M., Carnielli, W.A., Dunne, P.E.: Semi-stable semantics. Journal of Logic and Computation 22(5), 1207–1254 (2012) 7. Caminada, M., Gabbay, D.M.: A logical account of formal argumentation. Studia Logica 93(2), 109–145 (2009) 8. Diller, M., Haret, A., Linsbichler, T., Rümmele, S., Woltran, S.: An extension- based approach to belief revision in abstract argumentation. In: Proc. IJCAI. pp. 2926–2932. AAAI Press (2015) 9. Dung, P.M.: On the acceptability of arguments and its fundamental role in non- monotonic reasoning, logic programming and n-person games. Artif. Intell. 77(2), 321–357 (1995) 10. Dunne, P.E., Dvořák, W., Linsbichler, T., Woltran, S.: Characteristics of multiple viewpoints in abstract argumentation. In: Proc. KR. pp. 72–81. AAAI Press (2014) 11. Dyrkolbotn, S.K.: How to argue for anything: Enforcing arbitrary sets of labellings using AFs. In: Proc. KR. pp. 626–629. AAAI Press (2014) 12. Modgil, S., Bench-Capon, T.J.M.: Metalevel argumentation. Journal of Logic and Computation 21(6), 959–1003 (2011) 13. Verheij, B.: Two approaches to dialectical argumentation: admissible sets and ar- gumentation stages. In: Proc. NAIC. pp. 357–368 (1996) 54