=Paper=
{{Paper
|id=Vol-1444/paper4
|storemode=property
|title=On the Functional Completeness of Argumentation Semantics
|pdfUrl=https://ceur-ws.org/Vol-1444/paper4.pdf
|volume=Vol-1444
|dblpUrl=https://dblp.org/rec/conf/ki/GiacominLW15
}}
==On the Functional Completeness of Argumentation Semantics==
https://ceur-ws.org/Vol-1444/paper4.pdf
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