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 question: 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.
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 [
In [
This research has been supported by the Austrian Science Fund (FWF) through projects I1102 and P25521.
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 specification, 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 realizable 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. [
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 subframework, and tackles the above problem with extension-based two-valued specifications. Labelling-based three-valued specifications are investigated in Section 4 and Section 5 concludes the paper. 2
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 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 arguments 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⊕ ⊃ S⊕.
F 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 argument 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 [
Proposition 1. For an af F , Lpr(F ) = max (Lco(F )). 3
An I/O-gadget represents a (partial) af where two sets of arguments are identified 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 arguments 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 and a total function f : 2I →22O .
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 satisfiable 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 = {xJS | 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, xJS ) | xJ ∈ X, i ∈ J }∪
S {(i, xJS ) | xJ ∈ X, i ∈ (I \ J )}∪
S {(x1, x2) | x1, x2 ∈ X, x1
=2x}∪ {(xi, w) | xi ∈ X} ∪ {(w, w)}∪ {(xJS , o) | J ⊆ I, S ∈ f(J ), o ∈ (O \ S)}). 3 In the following we omit this specification.
Intuitively, xJS 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 )} ∪ {xJS } ∪ 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, xJS 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 xS . E is J stable in (C(f), J ) since xJS 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 xS J ∈ (X ∩ E ) attacking w, and xJS must attack all o ∈ (O \ S ). Since S ∈/ f(J ) by assumption, it must hold that J = J . Now note that z ∈ Eand 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 xJS , 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 xJS , 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 ) by C(f) under σ ∈ {sg, pr, se}. = ∅ is satisfied Proof (Sketch). Note that ∀J ⊆ I, stable, preferred, stage and semi-stable extensions 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 Argument names such as x{{ca,,db}} are abbreviated by xcadb. xiojp xiojpq j q yj x∅
∅ w p yi xoq i i xpq j o
z xopq j hence σ( (C(f), {j}))|O = {{p, q}, {o, p, q}} = f({j}).
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 i to C(f). Now σ( (C(f), {j})) = {{z, j, yi, x{{jp},q}, p, q}, {z, j, yi, x{{jo},p,q}, o, p, q}},
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 xJS with J = J are attacked by J or someiywith i ∈ (I \ J ), thus they are attacked by E∗, while all xJS 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 xJS defended by E∗, thus the only complete extension is E∗ ∪ {xJS } ∪ S. If, on the other hand, |S| > 1, any xJS with S ∈ S can be included, giving rise to the complete extension E∗ ∪ {xJS } ∪ S, or none of xJS can be included, giving rise to the complete extension E∗ ∪ S since an xJS 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. 4
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) →L2(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 satisfiable 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).
The following was shown in Proposition 7 of [
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.
Proposition 7 of [
In Propositions 5 and 6 we have given necessary conditions for 3-valued I/Ospecifications 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
Dfσ = (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. Definition 14. Given a 3-valued I/O-specification f with |f(L)=1| for all L ∈ L(I), the gr-specific part of Dfgr is given by
Xgr ={xo | o ∈ O, L ∈ df(o)}, and
L f Rfgr ={(i, xoL) | xo ∈ Xfgr, L(i) = f} ∪ {(i , xoL) | xo ∈ Xfgr, L(i) = t}∪
L L {(xoL, o ) | xo ∈ Xfgr, f(L)(o) = t} ∪ {(xoL, o) | xo ∈ Xfgr, f(L)(o) = f}.
L L
For every o ∈ O and each labelling L which is determining for o, there is the argument xL. This argument can be labelled t if L is the labelling of I and o intuitively enforces the labelling of o to be as given by f(L) .
The next results, requiring two preliminary lemmata, characterize satisfiability 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( (Dfgr, L ))(xoL) is – t iff L L ; – f iff L and L are not compatible; and – u iff L Lbut 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 Dfgr under gr.
Proof. Consider some input labelling L. We have to show Lgr( (Dfgr, 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 ∈ df(o) it holds that Lgr( (Dfgr, L))(xoL ) = t. Since such oLx are the only potential attackers of o and o , Lgr( (Dfgr, L))(o) = u.
Next assume f(L)(o) = t. Then there is some L L with L ∈ df(o) and f(L )(o) = t. By Lemma 2 we get Lgr( (Dfgr, L))(xoL ) = t. Moreover, xoL attacks o , hence Lgr( (Dfgr, K))(o ) = f. Towards a contradiction assume there is some xL attacking o with Lgr( (Dfgr, L))(xoL ) ∈ {t, u}. Then, by Lemma 2, L and o L are compatible. However, by construction of Dfgr, 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) and f(L )(o) = f. By Lemma 2 we get Lgr( (Dfgr, L))(xoL ) = t. Moreover, xoL attacks o, hence Lgr( (Dfgr, 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 Dfgr is depicted below. Consider for example the labelling-injection of fu to Dfgr, which is indicated by the dotted part of the figure. We get Lgr( (Dfgr, fu))|O = uu, satisfying the I/O-specification. One can check that this holds for all possible labelling-injections, hence Dfgr satisfies f under the grounded semantics.
z i1 xtou1 o1 i1 xuot2 o1 i2 xuof2 o2 i2 xfof1 o2 t and for all xLK ∈ Xfpr, K P (xLK ) = f, then P |O = K.
Theorem 6. A 3-valued I/O-specification f is satisfiable under gr iff f is monotonic 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
Xpr ={xK | L ∈ L(I), K ∈ f(L)}, and
L f Rpr ={(i, xLK ) | xK ∈ Xfpr, L(i) = f} ∪ {(i , xLK ) | xK ∈ Xfpr, L(i) = t}∪
L L f {(xLK , o ) | xK ∈ Xfpr, K(o) = t} ∪ {(xLK , o) | xK ∈ Xfpr, K(o) = f}∪
L L {(xLK , xLK ) | ¬(L L ∧K
K ) ∧ ¬(L L ∧K
K )}.
Every input-output-combination is represented by an argument in Dfpr. 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 (Dfpr, L): If P (xLK ) = K ⇒ P (xLK ) = t and (K
K ∧ K )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 satisfied by Dfpr under pr.
Proof. Consider an arbitrary input labelling L ∈ L(I). We have to show that Lpr( (Dfpr, L))|O = f(L).
Similar to Lemma 2 one can check that those xLK ∈ Xfpr with L L are the only arguments in Xpr which can be t in a preferred labelling of (Dfpr, L).
f Now the arguments xLK with K ∈ f(L) form a clique in (Dfpr, L). Moreover each of these xLK defends itself, hence there is a preferred labelling of (Dfpr, L) for each K ∈ f(L) identified by xLK . Let PK be the preferred labelling with PK (xLK ) = t where K ∈ f(L). All xLK with K K ∧ K K are attacked by LKx, hence PK (xLK ) = f. Assume K K. If L L, then LKx is again attacked by xLK and PK (xLK ) = f. If L L, PK (xLK ) = t since it is attacked by some i or 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 xLK 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 least an xLK which is t in P , with L L, and without loss of generality we can assume that there is no xLK 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 xLK is t in P .
First, the only x-arguments that can be t are those xLK with L L. Note that, according to Definition 15, xLK does not attack xLK , since L L ∧ K K. If an attacker xLK is attacked in turn by xLK 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 xLK does not attack xLK . In the other case, by the assumption on xLK it holds that xLK is not t.
Now, xLK defends itself against all x-arguments and none of them is t, moreover by construction of (Dfpr, L), all attackers from I and I are f. But then, consider the labelling P obtained from P by assigning to xLK the label t, and by assigning to all the attackers of xLK 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 monotonic.
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 (Dfgr, L) coincides with the ideal labelling, and the preferred labellings of (Dfpr, L) coincide with semi-stable labellings. However, this does not allow to derive a complete characterization, since there are non-monotonic 3-valued I/Ospecifications, satisfiable by ideal and semi-stable semantics, respectively. 5
To the best of our knowledge, this is the first characterization of the input/output
expressive power of argumentation semantics. In [
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 [