=Paper=
{{Paper
|id=Vol-2171/paper_6
|storemode=property
|title=Expressing the Characteristics of an Argumentation Framework
|pdfUrl=https://ceur-ws.org/Vol-2171/paper_6.pdf
|volume=Vol-2171
|authors=Sosuke Moriguchi,Kazuko Takahashi
|dblpUrl=https://dblp.org/rec/conf/comma/MoriguchiT18
}}
==Expressing the Characteristics of an Argumentation Framework==
https://ceur-ws.org/Vol-2171/paper_6.pdf
60 S. Moriguchi et al. / Expressing the Characteristics of an Argumentation Framework
Expressing the Characteristics of an
Argumentation Framework
Sosuke MORIGUCHI a,1 and Kazuko TAKAHASHI a
a
Kwansei Gakuin University, Japan
Abstract. We propose a new semantics of Dung’s argumentation frame-
works characterized by three-valued logical expressions. Semantics for
frameworks is defined based on an extension and labeling. An extension
is a subset of arguments that denotes acceptable arguments, while la-
beling assigns one of three labels in, out, undec to each argument, and
arguments labeled in are acceptable. Both extension and labeling as-
sign basic notions to semantics, such as complete, grounded, preferred,
and stable. Moreover, labeling shows that an argument might be labeled
differently in other complete labelings. However, a label does not clar-
ify that the argument is acceptable in other complete labelings. Allo-
cation assigns three-valued logical expressions to each argument. Since
expressions contain variables for parameterizing the acceptability of ar-
guments, allocation facilitates the description not only of a specific set
of acceptable arguments, but also of the relationships between such sets.
As a result, allocation determines the characteristics of the argumenta-
tion framework. In this paper, we also propose a local form of allocation,
facilitating discussion of semantics as part of the framework.
Keywords. argumentation framework, labeling, three-valued logic
1. Introduction
Argumentation is a useful technique for handling problems requiring conflict res-
olution. In the 20 years since Dung’s proposal, computational argumentation has
been the focus of enthusiastic research across various fields in AI, including de-
feasible reasoning, dialogue, and legal reasoning [4,11,15,16].
Dung proposed his abstract argumentation framework in 1995, demonstrating
its relationship with both nonmonotonic reasoning and logic programming [10].
He formalized an argumentation framework consisting of a pair of a set of argu-
ments and attack relations between arguments. This framework may be repre-
sented as a directed graph. Based on this abstraction, analyses and reasoning in
argumentation may be reduced to a simple inference procedure, represented on a
graph, with no requirement to present the thought contents of arguments.
Regarding argumentation frameworks, the acceptable set is among the most
important concepts. Intuitively, an acceptable set constitutes a set of consistent
1 Corresponding Author: Contract Assistant, Kwansei Gakuin University, 2-1 Gakuen, Sanda,
Hyogo, 669-1337 Japan; E-mail:chiguri@acm.org.
S. Moriguchi et al. / Expressing the Characteristics of an Argumentation Framework 61
arguments, the veracity of which has been agreed or proven. Much theoretical
scholarship has focused on the issues inherent in arriving at definitions and cal-
culations of acceptable sets, and comparing such sets according to the different
semantics on which they are based [2,9]. Two major approaches are useful for as-
signing definitions to acceptable sets: an extension-based method and a labeling-
based method. Dung offered an extension-based definition that is, an acceptable
set is defined as a conflict-free admissible set called an extension [10]. On the
other hand, Caminada took a labeling-based approach [8]. The labeling-based
approach assigns one of three labels in, out, undec to each argument, depending
on the rule, and the set of arguments labeled in are considered to constitute the
acceptable set.
Caminada proved a strong correlation between acceptable sets obtained using
both approaches. Both extension and labeling assign basic notions to semantics,
such as complete, grounded, preferred, and stable. Moreover, labeling gives an-
other viewpoint for arguments in some acceptance sets. For example, if an argu-
ment is labeled differently in two complete labelings, it is labeled undec in the
grounded labeling.
However, undec does not mean the argument is in some acceptable sets. An
argument attacked by only itself is labeled undec in any complete labelings. When
the arguments A and B attack each other (and the others do not), they labeled
undec in the grounded labeling, and opposite ones (in and out) in (other) complete
labelings. To grasp such behaviors, we need more expressive representations for
semantics.
In this paper, we propose a unified form expressing all of these semantic
behaviors and the calculation of any acceptable set using a three-valued logic.
Specifically, we allocate a logical expression to each argument. Three-valued log-
ical expressions allow us to directly express three values in labeling (in, out, and
undec), to abstract acceptability of an argument in the framework, and to show
relationships with other arguments. Each acceptance set is obtained by assigning
one of three values true, false and undec to each atomic term; the value of the
logical expression to an argument is then determined. We also propose local al-
location, permitting the analysis of one part of the framework independently of
the whole.
The key contributions of this paper are as follows: (a) We prove that labeling
and allocation using only logical constants coincide (section 3.2). We also prove
that allocation permits the framework to keep any complete labelings together
(section 4). (b) We demonstrate the relationship between local allocation (i.e., a
part of the framework) and global allocation (i.e., the whole of the framework)
(section 5.2).
This paper is organized as follows. In section 2, we review the basic notions of
argumentation frameworks and labeling. In section 3, we define the three-valued
logical expressions used in allocation, and offer the definitions and specifications
for allocation. In section 4, we discuss the process of assigning a general expression
to each argument. In section 5, we propose a local allocation method. Finally, we
conclude this paper in section 6.
62 S. Moriguchi et al. / Expressing the Characteristics of an Argumentation Framework
Figure 1. Two examples of argumentation frameworks. (a) Left: acyclic graph, and (b) right:
cyclic graph.
2. Argumentation Framework
We will begin by defining argumentation frameworks, in the terms used in relation
to Dung’s concepts in [10].
Definition 1. An argumentation framework comprises a pair of a set of arguments
and their attack relations (i.e., binary relation on arguments). We use (Arg, Att)
for denoting an argumentation framework.
The following is the definition of labeling (with regard to semantics) offered
by Caminada [8].
Definition 2. Labeling in terms of frameworks is a function from arguments to
labels, i.e., L : Arg → {in, undec, out}. Labeling L is complete iff the following
conditions are satisfied.
• L(A) = in iff L(A0 ) = out for all arguments A0 such that (A0 , A) ∈ Att.
• L(A) = out iff there exists an argument A0 such that (A0 , A) ∈ Att and
L(A0 ) = in.
• L(A) = undec iff there exists an argument A0 such that (A0 , A) ∈ Att and
L(A0 ) = undec and there are no arguments A00 such that (A00 , A) ∈ Att and
L(A00 ) = in.
Complete labeling L is grounded iff {A|L(A) = in} is smallest in those com-
plete labelings. We use Lg for grounded labeling. Complete labeling L is stable iff
{A|L(A) = undec} is empty, and L is preferred iff {A|L(A) = undec} is minimal
in those complete labelings.
The arguments labeled in are considered to be accepted.
Example 1. In the figure 1, we illustrate two argumentation frameworks, (a) and
(b). The left framework (a) is an acyclic framework, with only one complete
labeling, L(1) = L(3) = L(5) = in and L(2) = L(4) = out. Since the complete
labeling is unique, it also constitutes grounded labeling.
The right framework (b) incorporates a cyclic part between 1 and 2. There
are three complete labelings, L1 , L2 and L3 :
• L1 (A) = undec for all arguments A. This is a grounded labeling.
• L2 (1) = L2 (4) = in and L2 (2) = L2 (3) = out.
• L3 (2) = L3 (4) = in and L3 (1) = L3 (3) = out.
S. Moriguchi et al. / Expressing the Characteristics of an Argumentation Framework 63
From these labelings, we can see arguments 1 and 2 have always opposite
labels, and 3 and 4 are labeled undec only when 1 and 2 are labeled undec.
However, each labeling does not imply such observation.
3. Allocation of Three-valued Logical Expression
As an alternative to the labels described in section 2, we apply three-valued
logical expressions to the acceptance of arguments. We term the process by which
arguments are mapped to logical expressions allocation.
3.1. Three-valued Logical Expression
Here, we define the three-valued logical expressions (henceforth, expressions for
short) as follows:
p ::= T | F | U | x | ¬p | p∧p | p∨p
where x is a variable (an element of Var ) and T , F , and U are constants denoting
true, false, and undecided (the middle value), respectively.
We define the evaluation of the expressions under valuation for the variables
v : Var → {1, −1, 0}. Note that 1, −1, and 0 denote T , F , and U respectively.
[[T ]]v = 1, [[F ]]v = −1, [[U ]]v = 0, [[x]]v = v(x),
[[¬p]]v = −[[p]]v , [[p ∧ q]]v = min([[p]]v , [[q]]v ), [[p ∨ q]]v = max([[p]]v , [[q]]v ).
We also define the equivalence between expressions as p ≡ q ⇔ ∀v, [[p]]v =
[[q]]v . This equivalence relation is clearly reflexive, symmetric, and transitive.
Lemma 1. The following specifications are satisfied.
1. For any expression p, ¬T ≡ F , T ∧ p ≡ p ∧ T ≡ p, T ∨ p ≡ p ∨ T ≡ T ,
¬F ≡ T , F ∧ p ≡ p ∧ F ≡ F , F ∨ p ≡ p ∨ F ≡ p, ¬U ≡ U .
2. Let the valuation v0 as v0 (x) = 0 for every variable x. If p is not equivalent
with either T or F , [[p]]v0 = 0.
3. Any expression p is either equivalent with T or F , or there is an equivalent
expression without any occurrence of T or F .
4. Let valuation v1 satisfy v1 (x) 6= 0 for each variable x. If U does not occur
in p, [[p]]v1 6= 0.
5. For any expression p, if U does not occur in p, p 6≡ U .
They are easily proven by computation or induction on expressions.
3.2. Allocation
As noted above, we apply the allocation to the process of mapping each argument
to an expression, and each mapping instance is termed an allocator. Completeness
of allocation is defined in a manner similar to that for labeling.
64 S. Moriguchi et al. / Expressing the Characteristics of an Argumentation Framework
Definition 3. An allocator E is complete iff the following statements are satisfied.
• If argument A is not attacked, then E(A) = T .
• If argument
V A is attacked by other arguments, then
E(A) ≡ (A0 ,A)∈Att ¬E(A0 ).
Note that the former may be treated as a special instance of the latter.
For example, (a) in figure 1 has an complete allocator E such that E(1) =
E(3) = E(5) = T and E(2) = E(4) = F . There are, of course, an infinite number
of allocators that E(3) ≡ T but E(3) 6= T . For the purposes of this paper,
however, equivalent allocators are irrelevant.
The following theorem demonstrates that allocation constitutes a generaliza-
tion of labeling.
Theorem 1. For any complete labeling L, the allocator E such that E(A) = T
iff L(A) = in, E(A) = F iff L(A) = out, and E(A) = U iff L(A) = undec is
complete.
An allocator mapping only logical constants (T , F or U ) is termed a constant
allocator. The inverse of the above theorem is also valid.
Theorem 2. For any constant allocator E, labeling L such that L(A) = in if
E(A) = T , L(A) = out if E(A) = F , and L(A) = undec if E(A) = U is a
complete labeling.
Example 2. (b) in figure 1 has three constant allocators corresponding to complete
labelings. Simultaneously, it also has a complete allocator E such that E(1) = a,
E(2) = ¬a, E(3) = a ∧ ¬a and E(4) = a ∨ ¬a. With the valuation v, these
expressions are evaluated to v(a), −v(a), min(v(a), −v(a)) and max(v(a), −v(a)).
• When v(a) = 1, they are 1, −1, −1, 1, respectively. This result corresponds
to L2 , as described in example 1.
• When v(a) = −1, they are −1, 1, −1, 1, respectively. This result corre-
sponds to L3 .
• When v(a) = 0, they are all 0. This result corresponds to L1 .
The inherent intension of the above observation is that E abstracts these
labelings. Note that a complete allocator may allocate logical expressions with
variables to arguments only if the arguments are in cycles of attack relations (see
theorem 5).
We demonstrate the relation between E and constant allocators correspond-
ing to the labelings. We apply substitution to an expression and a valuation,
respectively, replacing the variables with constants.
Definition 4. p[C/x] for logical expression p, variable x and logical constant C are
defined as follows.
• If p is a logical constant, p[C/x] = p.
• x[C/x] = C and y[C/x] = y if y 6= x.
• (¬p)[C/x] = ¬(p[C/x]), (p ∧ q)[C/x] = p[C/x] ∧ q[C/x], (p ∨ q)[C/x] =
p[C/x] ∨ q[C/x].
S. Moriguchi et al. / Expressing the Characteristics of an Argumentation Framework 65
We also use similar notation v[C/x] for valuation v, variable x and logical con-
stant C to denote v[C/x](x) = [[C]]v and v[C/x](y) = v(y) if x 6= y.
Lemma 2. [[p[C/x]]]v = [[p]]v[C/x]
Lemma 3. Let x be a variable and C be a logical constant. If p1 ≡ p2 , then
p1 [C/x] ≡ p2 [C/x].
For any complete allocator, a variable may be replaced with one of the con-
stants.
x
Theorem 3. For the complete allocator E, we write EC (A) = E(A)[C/x] where
x
C is a logical constant. Consequently, for any complete allocator E, EC is also
complete.
Hereafter, we term a set of variables occurring in expressions allocated by
allocator E, i.e. {x|x occurs in E(A) for some A ∈ Arg}, the allocation variables
of E. Theorem 3 generates a complete allocator from another complete allocator
that has more allocation variables. With theorem 2, a complete allocator gives
some complete labelings. When a complete allocator E 0 is equivalent to another
allocator E, substituting some variables with constants, E 0 is said to be instanti-
ated from E.
Theorem 4. For any complete allocator E and valuation v, a constant allocator
Ev is defined as Ev (A) = T if [[E(A)]]v = 1, Ev (A) = F if [[E(A)]]v = −1 and
Ev (A) = U if [[E(A)]]v = 0. Then Ev is instantiated from E.
There are some arguments to which any complete allocator allocates ex-
pressions equivalent to logical constants. For example, the argumentation frame-
work ({1, 2, 3}, {(1, 2), (2, 3), (3, 1)}) has a unique complete allocator E, such that
E(A) ≡ U for A = 1, 2, 3. The following theorem shows other examples.
Theorem 5. Let Lg be a grounded labeling of a framework and E be a complete
allocator. If Lg (A) = in, then E(A) ≡ T . Also, if Lg (A) = out, then E(A) ≡ F .
4. Construction of Allocator
Instantiation raises the following question regarding inverse direction: can two
allocators be instantiated from a complete allocator? The following theorem pro-
vides a positive answer to this question.
Theorem 6. Let E1 and E2 be complete allocators and a be a fresh variable. The
allocator E, such that E(A) = a ∧ E1 (A) ∨ ¬a ∧ E2 (A) ∨ a ∧ ¬a if Lg (A) = undec
and E(A) = E1 (A) otherwise, is complete.
Proof. For valuation v,
• Let v(a) = 1. If argument A satisfies Lg (A) = undec, then [[E(A)]]v =
[[E1 (A)]]v . Otherwise, E(A) = E1 (A), V so [[E(A)]]v = [[E1 (A)]]v . Since E1
is a complete allocator, E1 (A) ≡ (A0 ,A)∈Att ¬E1 (A0 ). So [[E(A)]]v =
[[E1 (A)]]v = [[ (A0 ,A)∈Att ¬E1 (A0 )]]v = [[ (A0 ,A)∈Att ¬E(A0 )]]v .
V V
66 S. Moriguchi et al. / Expressing the Characteristics of an Argumentation Framework
• Let v(a) = −1. If argument A satisfies Lg (A) = undec, then [[E(A)]]v =
[[E2 (A)]]v . And otherwise E(A) = E1 (A), and from theorem 5 E1 (A) =
EV2 (A), so [[E(A)]]v = [[E2 (A)]]v . Applying the same process, [[E(A)]]v =
[[ (A0 ,A)∈Att ¬E(A0 )]]v .
• Let v(a) = 0. If argument A satisfies Lg (A) = undec, then [[E(A)]]v = 0.
Otherwise E(A) = E1 (A), and from theorem 5 [[E1 (A)]]v = 1 if Lg (A) = in
and [[E1 (A)]]= − 1 if Lg (A) = out. This corresponds to Lg ; according to
theorem 1 it is complete.
Therefore E is complete.
From this abstraction, we arrive at the notion of general allocators.
Definition 5. A complete allocator, such that any complete labelings are obtained
as its instantiated allocators, is called a general allocator.
We have already encountered an example of a general allocator as E, de-
scribed in example 2.
Since the number of complete labelings within a finite framework is finite,
we get a general allocator through the repeated application of the generalization
process detailed above.
Theorem 7. There is a general allocator for each finite framework.
As single framework has several general allocators, and discerning which (or
how many) constant allocators are instantiated from a general allocator is chal-
lenging. However, grounded labeling is obtained by a specific valuation.
Lemma 4. When E is a general allocator, Ev0 , where v0 (x) = 0 for any variable
x is a constant allocator corresponding to a grounded labeling.
Stable labelings are also obtained by specific valuations with conditions.
Lemma 5. When E is a general allocator that E(A) does not contain U for any
argument A, Ev1 , where v1 (x) 6= 0 for any variable x, is a constant allocator
corresponding to a stable labeling.
The means by which preferred labelings are obtained is unclear, but it is
evident that they are obtained by some valuations v such that v(x) 6= 0 for any
variable x.
Unfortunately, the general allocator produced by theorem 6 is frequently
larger than desired. As the proof demonstrates, E1 , E2 and the allocator corre-
sponding to Lg are instantiated from the composed allocator described in the-
orem 6. This means that each composition instantiates to another complete la-
beling for each introduced variable. For example, the argumentation framework
shown in figure 2 has nine complete labelings. The method requires seven vari-
ables to construct a general allocator (each process has one abstract labeling and
one grounded labeling). However, since the left part ({ 1, 2 }) and right part ({ 3,
4 }) only affect the central argument 5, without affecting one another, the a gen-
eral allocator E is constructed using only two variables, as E(1) = a, E(2) = ¬a,
E(3) = b, E(4) = ¬b and E(5) = a ∧ b.
S. Moriguchi et al. / Expressing the Characteristics of an Argumentation Framework 67
Figure 2. A framework with two cyclic parts.
Prior to the application of the method, reducing the framework down to its
strongly connected components may decrease the number of allocation variables.
However, it is unclear how allocators for such components are constructed and
whether, if indeed possible, such allocators are minimal.
Another problem of the process is that its complexity depends on the enu-
meration of complete labelings, which is not processed in polynomial time (unless
P 6= NP ) [14]. To implement allocation, an algorithm for constructing general
allocators without enumeration of complete labelings is required.
5. Local Allocation
As the size of a given framework is so big, we want to split into some blocks.
Since both extensions and labelings are global entities, there are no function-
alities for abstraction outside of the blocks. Additionally, merging blocks is re-
quired, but each block may exhibit its own preference, for example, grounded,
preferred, stable, etc. However, it is difficult to assemble the blocks according to
such preferences.
Allocation offers a solution to these problems. Variables abstract expressions
allocated to arguments. Furthermore, they facilitate assembly of the blocks by
substitution.
In this section, we propose allocations for the blocks, not for the global frame-
work. The term “allocators” here applies only to specific blocks, not the global
framework, and use term local allocators.
5.1. Variable Argument
Let the block be a subset of Arg. First, the arguments are selected attacking argu-
ments in the block. These arguments may externally affect the block’s allocation
in the block from outside. These arguments are termed variable arguments.
To abstract the acceptance of variable arguments, a local allocator provides
each with a unique variable. Here, we offer formal definitions for blocks, variable
arguments and local allocators.
Definition 6. Let B ⊆ P(Arg). If ∀B1 , B2 ∈ B, B1 6= B2 → B1 ∩ B2 = ∅ and
∀A ∈ Arg, ∃B ∈ B, A ∈ B, then B is called the splitter of the framework, and each
element of the splitter is called a block. For the block B, we define the function VA
as VA(B) = {A0 |A ∈ B ∧A0 6∈ B ∧(A0 , A) ∈ Att}. An argument in VA(B) is called
a variable argument. A local allocator El for block B is a function B ∪VA(B) → p
where p is an expression.
68 S. Moriguchi et al. / Expressing the Characteristics of an Argumentation Framework
Figure 3. Example of block. {a} is a variable argument of block {1, 2, 3}.
When we discuss the local allocation and allocation defined in section 3.2 si-
multaneously, we apply the term global allocation to the latter. The completeness
of local allocators is defined similarly to that of global allocators.
Definition 7. A local allocator El for block B is complete iff the following condi-
tions are satisfied.
• For any variable argument A, El (A) = a for some variable a and El (A) 6=
El (A0 ) for any other variable argument A0V
.
• For any argument A in block B, El (A) ≡ (A0 ,A)∈Att ¬El (A0 ).
The difference between the completeness of local allocators and that of global
allocators is the allocation of variable arguments to variables. As such, the com-
plete local allocator for all arguments (i.e., no variable arguments) is a complete
(global) allocator.
Example 3. Figure 3 is an example of block. It has three arguments {1, 2, 3}
and its variable argument is {a}. We can assign expressions to this block, like
El (a) = a, El (1) = a ∨ b, El (2) = ¬a ∧ ¬b, and El (3) = (a ∨ b) ∧ ¬a ∧ ¬b.
This allocator shows that the acceptability of 3 depends on not only external
argument a, but also internal argument 1 (or 2). This means that this block
requires a preference for 1 (or a negativity for 2) in the whole framework including
this block.
5.2. Local and Global Completeness
Here, we construct a complete global allocator from local allocators. Generally
speaking, the construction of local allocators is challenging.
For example, we assume a splitter for figure 4 as { {1, 2, 3}, {4, 5, 6} }. Each
block has a local allocator, as described in example 3. To distinguish the variables
in each allocator, we use al and bl for {1, 2, 3}, and ar and br for {4, 5, 6}. To
construct a global allocator from these, we need to remove al and ar . However, it
is difficult to remove them since al relates to (ar ∨ br ) ∧ ¬ar ∧ ¬br and ar relates
(al ∨ bl ) ∧ ¬al ∧ ¬bl .
To avoid this, we restrict the acyclic splitters.
Definition 8. We define attacks on a splitter as B1 attacking B2 iff B1 6= B2 and
there exist A ∈ B1 and A0 ∈ B2 , such that (A, A0 ) ∈ Att. A splitter is acyclic iff
the graph, whose nodes are blocks and arcs are attacks on the splitter, is acyclic.
S. Moriguchi et al. / Expressing the Characteristics of an Argumentation Framework 69
Figure 4. Cyclic attack between blocks {1, 2, 3} and {4, 5, 6}.
Lemma 6. Assume an acyclic splitter B and two blocks B1 , B2 ∈ B such that B1
is not attacked by any other blocks and B2 is not attacked by other than B1 . Then,
B 0 = B\{B1 , B2 } ∪ {B1 ∪ B2 } is also acyclic.
Next, we compose local allocators for such blocks.
Theorem 8. For the two blocks B1 and B2 , we may assume that VA(B1 )∩B2 = ∅.
If E1 and E2 are complete local allocators for B1 and B2 respectively, the following
allocator E12 is a complete local allocator for B1 ∪ B2 .
E1 (A) (A ∈ B1 ∪ VA(B1 ))
E12 (A) =
E2 (A)[A0 ∈ VA(B2 ) ∩ B1 , E1 (A0 )/E2 (A0 )] (A ∈ B2 ∪ VA(B2 ))
where p[A0 ∈ VA(B2 ) ∩ B1 , E1 (A0 )/E2 (A0 )] = p[E1 (A1 )/a1 ] . . . [E1 (An )/an ] for
all Ai ∈ VA(B2 ) ∩ B1 , E2 (Ai ) = ai .
Proof. For argument A ∈ B1 , it is evident that the conditions for com-
pleteness hold, since its attackers are also in B1 . VFor argument A ∈ B2 ,
E12 (A) = E2 (A)[A0 ∈ VA(B2 ), E1 (A0 )/E2 (A0 )] ≡ ( (A0 ,A)∈Att ¬E2 (A0 ))[A0 ∈
VA(B2 ), E1 (A0 )/E2 (A0 )] ≡ (A0 ,A)∈Att ¬(E2 (A0 )[A0 ∈ VA(B2 ), E1 (A0 )/E2 (A0 )]).
V
If (A0 , A) ∈ Att then A0 ∈ B2 or A0 ∈ VA(B2 ) ∩ B1 or A0 ∈ VA(B2 ) but
A0 6∈ B1 . The first case, it is clear that E2 (A0 )[A0 ∈ VA(B2 ), E1 (A0 )/E2 (A0 )]) =
E12 (A0 ). The second case, E2 (A0 ) = a for some variable a and E2 (A0 )[A0 ∈
VA(B2 ), E1 (A0 )/E2 (A0 )]) = a[A0 ∈ VA(B2 ), E1 (A0 )/E2 (A0 )]) = E1 (A0 ) =
E12 (A0 ). The last case is unaffected by the substitution, so E2 (A0 )[A0 ∈
VA(B2 ), E1 (A0 )/E2 (A0 )]) = a[A 0
V ∈ VA(B2 ), E1 (A
0
)/E2 (A0 )]) = a = E2 (A0 ) =
0 0
E12 (A ). Therefore E12 (A) ≡ (A0 ,A)∈Att ¬E12 (A ).
Finally, we can prove the following theorem using lemma 6 and theorem 8.
Theorem 9. For a finite framework, if a splitter is acyclic, then the assembly of
complete local allocators, as described in theorem 8, construct a complete global
allocator.
6. Conclusion
In this paper, we have proposed a new semantics for argumentation frameworks
characterized by three-valued logical expressions. Allocation offers flexibility for
the description of specific semantics (as constant allocators) and whole seman-
tics (as general allocators). We have also proposed a process of local allocation,
70 S. Moriguchi et al. / Expressing the Characteristics of an Argumentation Framework
focusing on the semantics of part of a given framework. We proved that a global
allocator can be constructed from an acyclic splitter and local allocators.
There are several researches to propose novel kinds of semantics of arguments.
Abstract dialectical frameworks (ADFs)[6,7] are generalization of argumentation
frameworks. In ADFs, acceptance of an argument gives as logical expressions with
acceptances of other arguments relating with the argument2 . Also, there is an
equational approach to describe acceptances for arguments [12]. In the equational
approach, each argument has its own numerical function, describing relationships
with other arguments. The results (acceptability) of the equations are a numeric
value of [0, 1] (and interpretable as acceptance like labels).
These approaches give flexibility of relationships between arguments. Al-
though our method allows only attacks for such relationships, by the definition
of the completeness (Def. 3), it enables us to discuss acceptability between argu-
ments, or an argument and the whole framework through the allocation variables,
which is effective to compare semantics.
There are some approaches to calculate several kinds of semantics using log-
ical formulas. Besnard et al. proposed a methodology to encode argumentation
frameworks and set operations to logical formulas [5]. Arieli and Caminada pro-
posed an approach based on signed theories and quantified boolean formulas to
calculate several kinds of labelings [1]. These approaches give a formula for each
argumentation framework to represent acceptance of arguments. Our approach
gives a formula for each argument in given framework to represent how the ac-
ceptability of the argument behaves in the framework.
Local allocation enables us to split a framework into blocks. We discussed
only acyclic splitters, but there are several researches to decompose a framework
into some parts. Baroni et al. discussed decomposability of a framework in several
semantics [3]. Variable arguments are similar to input arguments in I/O-gadgets,
proposed in [13]. Both works are not limited to acyclic. However, since they are
based on labeling (or extension) approaches, we should discuss their results are
applicable in our approach.
Our work will focus on two key areas in the immediate future.
• The completeness of an allocator is unambiguous: checking for complete-
ness is obviously more complex than it is for labeling. Since checking that
the equivalence of two-valued logical expressions is co-NP complete, the
completeness of the allocation should be at least co-NP hard. For the pur-
poses of our study, it is less important to check completeness than it is to
construct general allocators. We will soon begin developing a method for
constructing general (and local) allocators.
• The minimum number of allocation variables is unclear: for example, if
the framework has two or three complete labelings, its general allocator
can be constructed using one variable according to the method described
in section 4 (by selecting not-grounded complete labelings as E1 and E2 ).
A variable can be instantiated with T , F or U , so a framework with four
complete labelings requires at least two allocation variables to provide the
general allocator. In fact, we can construct it from two allocation variables
2 Conditions in ADFs are defined as functions, but logical expressions are enough expressive.
S. Moriguchi et al. / Expressing the Characteristics of an Argumentation Framework 71
using the same method. However, where a framework has five complete
labelings, it is unclear whether the general allocator can be constructed
from two variables.
Acknowledgment
This work was supported by JSPS KAKENHI Grant Number JP17H06103.
References
[1] Arieli, O. and Caminada, M. A QBF-based formalization of abstract argumentation se-
mantics. Journal of Applied Logic, 11(2):229–252, 2013.
[2] Baroni, P., Caminada, M. and Giacomin,G. An introduction to argumentation semantics.
The Knowledge Engineering Review, 26(4):365–410, 2011.
[3] Baroni, P., Boella, G., Cerutti, F., Giacomin, M., Torre, L. and Villata, S. On the In-
put/Output behavior of argumentation frameworks. Artificial Intelligence, 217:144–197,
2014.
[4] Bench-Capon, T. and Dunne, P. Argumentation in artificial intelligence. Artificial Intel-
ligence, 171:619–641, 2007.
[5] Besnard, P., Doutre, S. and Herzig, A.: Encoding Argument Graphs in Logic. In Proc. of
IPMU2014, (2):345-354, 2014.
[6] Brewka, G. and Woltran, S.: Abstract dialectical frameworks. In Proc. of KR2010, pp.102–
111, 2010.
[7] Brewka, G., Ellmauthaler, S., Strass, H., Wallner, J. P., and Woltran, S.: Abstract dialec-
tical frameworks revisited. In Proc. of IJCAI2013, pp.803–809, 2013.
[8] Caminada, M.: On the Issue of Reinstatement in Argumentation. In Proc. of JELIA 2006,
pp.111–123, 2006.
[9] Dunne, P., Spanring, C., Linsbichler, T. and Woltran, S.: Investigating the relationship
between argumentation semantics via signatures In Proc. of IJCAI2016, pp.1051–1057,
2016.
[10] Dung, P. M.: On the acceptability of arguments and its fundamental role in nonmono-
tonic reasoning, logic programming and n-person games. Artificial Intelligence, 77:321–
357, 1995.
[11] Garc’ia. A and Simari, G.: Defeasible logic programming: An argumentative approach.
Theory and Logic Programming, 4(1):95–138, 2004.
[12] Gabby, D. M.: Equational approach to argumentation networks. Argument and Compu-
tation, 3(2-3):87–142, 2012.
[13] Giacomin, M., Linsbichler, T. and Woltran, S.: On the Functional Completeness of Argu-
mentation Semantics. In Proc. of KR2016, pp.43–52, 2016.
[14] Kröll, M., Pichler, R. and Woltran, S.: On the Complexity of Enumerating the Extensions
of Abstract Argumentation Frameworks In Proc. of IJCAI2017, pp.1145–1152, 2017.
[15] Prakken, H.: An overview of formal models of argumentation and their application in
philosophy. Studies in logic, 4(1):65–86, 2011.
[16] Rahwan,I. and Simari,G.(eds.).: Argumentation in Artificial Intelligence. Springer, 2009.