We propose a new semantics of Dung's argumentation frameworks 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 labeling assigns one of three labels in, out, undec to each argument, and arguments labeled in are acceptable. Both extension and labeling assign 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 clarify that the argument is acceptable in other complete labelings. Allocation assigns three-valued logical expressions to each argument. Since expressions contain variables for parameterizing the acceptability of arguments, 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 argumentation framework. In this paper, we also propose a local form of allocation, facilitating discussion of semantics as part of the framework.
Argumentation is a useful technique for handling problems requiring conflict resolution. In the 20 years since Dung's proposal, computational argumentation has been the focus of enthusiastic research across various fields in AI, including defeasible 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 arguments and attack relations between arguments. This framework may be represented 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 arguments, the veracity of which has been agreed or proven. Much theoretical scholarship has focused on the issues inherent in arriving at definitions and calculations 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 assigning definitions to acceptable sets: an extension-based method and a labelingbased 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 another viewpoint for arguments in some acceptance sets. For example, if an argument 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 logical 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 allocation, 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.
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(A ) = out for all arguments A such that (A , A) ∈ Att.
• L(A) = out iff there exists an argument A such that (A , A) ∈ Att and L(A ) = in. • L(A) = undec iff there exists an argument A such that (A , A) ∈ Att and L(A ) = undec and there are no arguments A such that (A , A) ∈ Att and
Complete labeling L is grounded iff {A|L(A) = in} is smallest in those complete labelings. We use L g 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, L 1 , L 2 and L 3 :
• L 1 (A) = undec for all arguments A. This is a grounded labeling.
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.
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.
Here, we define the three-valued logical expressions (henceforth, expressions for short) as follows:
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.
We also define the equivalence between expressions as p ≡ q ⇔ ∀v,
This equivalence relation is clearly reflexive, symmetric, and transitive.
Lemma 1. The following specifications are satisfied.
Any expression p is either equivalent with T or F , or there is an equivalent expression without any occurrence of T or F .
They are easily proven by computation or induction on expressions.
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. Definition 3. An allocator E is complete iff the following statements are satisfied.
Note that the former may be treated as a special instance of the latter. For example, (a) in figure 1 has an complete allocator
There are, of course, an infinite number of allocators that E(3) ≡ T but E(3) = T . For the purposes of this paper, however, equivalent allocators are irrelevant.
The following theorem demonstrates that allocation constitutes a generalization of labeling.
Theorem 1. For any complete labeling L, the allocator E such that
An allocator mapping only logical constants (T , F or U ) is termed a constant allocator. The inverse of the above theorem is also valid. • When v(a) = 1, they are 1, −1, −1, 1, respectively. This result corresponds to L 2 , as described in example 1. • When v(a) = −1, they are −1, 1, −1, 1, respectively. This result corresponds to L 3 . • When v(a) = 0, they are all 0. This result corresponds to L 1 .
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 corresponding 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.
We also use similar notation v[C/x] for valuation v, variable x and logical constant
Lemma 3. Let x be a variable and C be a logical constant. If
For any complete allocator, a variable may be replaced with one of the constants.
Theorem 3. For the complete allocator E, we write
where C is a logical constant. Consequently, for any complete allocator E, E x C 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 is equivalent to another allocator E, substituting some variables with constants, E is said to be instantiated from E. Theorem 4. For any complete allocator E and valuation v, a constant allocator
There are some arguments to which any complete allocator allocates expressions equivalent to logical constants. For example, the argumentation framework ({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 L g be a grounded labeling of a framework and E be a complete allocator. If L g (A) = in, then E(A) ≡ T . Also, if L g (A) = out, then E(A) ≡ F .
Instantiation raises the following question regarding inverse direction: can two allocators be instantiated from a complete allocator? The following theorem provides a positive answer to this question. Theorem 6. Let E 1 and E 2 be complete allocators and a be a fresh variable. The allocator E, such that
And otherwise E(A) = E 1 (A), and from theorem 5
= out. This corresponds to L g ; 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, described 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 challenging. However, grounded labeling is obtained by a specific valuation. Lemma 4. When E is a general allocator, E v0 , where v 0 (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, E v1 , where v 1 (x) = 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) = 0 for any variable x.
Unfortunately, the general allocator produced by theorem 6 is frequently larger than desired. As the proof demonstrates, E 1 , E 2 and the allocator corresponding to L g are instantiated from the composed allocator described in theorem 6. This means that each composition instantiates to another complete labeling for each introduced variable. For example, the argumentation framework shown in figure 2 has nine complete labelings. The method requires seven variables 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 general allocator E is constructed using only two variables, as 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 enumeration of complete labelings, which is not processed in polynomial time (unless P = NP ) [14]. To implement allocation, an algorithm for constructing general allocators without enumeration of complete labelings is required.
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 functionalities for abstraction outside of the blocks. Additionally, merging blocks is required, 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 framework. The term "allocators" here applies only to specific blocks, not the global framework, and use term local allocators.
Let the block be a subset of Arg. First, the arguments are selected attacking arguments 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. When we discuss the local allocation and allocation defined in section 3.2 simultaneously, 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 E l for block B is complete iff the following conditions are satisfied.
• For any variable argument A, E l (A) = a for some variable a and E l (A) = E l (A ) for any other variable argument A .
The difference between the completeness of local allocators and that of global allocators is the allocation of variable arguments to variables. As such, the complete 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 E l (a) = a, E l (1) = a ∨ b, E l (2) = ¬a ∧ ¬b, and
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.
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 a l and b l for {1, 2, 3}, and a r and b r for {4, 5, 6}. To construct a global allocator from these, we need to remove a l and a r . However, it is difficult to remove them since a l relates to (a r ∨ b r ) ∧ ¬a r ∧ ¬b r and a r relates (a l ∨ b l ) ∧ ¬a l ∧ ¬b l .
To avoid this, we restrict the acyclic splitters.
Definition 8. We define attacks on a splitter as B 1 attacking B 2 iff B 1 = B 2 and there exist A ∈ B 1 and A ∈ B 2 , such that (A, A ) ∈ Att. A splitter is acyclic iff the graph, whose nodes are blocks and arcs are attacks on the splitter, is acyclic.
Proof. For argument A ∈ B 1 , it is evident that the conditions for completeness hold, since its attackers are also in B 1 . For argument
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.
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 semantics (as general allocators). We have also proposed a process of local allocation, 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. Although our method allows only attacks for such relationships, by the definition of the completeness (Def. 3), it enables us to discuss acceptability between arguments, 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 logical formulas. Besnard et al. proposed a methodology to encode argumentation frameworks and set operations to logical formulas [5]. Arieli and Caminada proposed 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 acceptability 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 completeness 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 purposes 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 E 1 and E 2 ). 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 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.
This work was supported by JSPS KAKENHI Grant Number JP17H06103.