Abstract
As a useful reasoning model, higher-order argumentation frameworks (HO-AF) have been studied in many works. This paper contributes to the theory of HO-AFs in three aspects. First, the acceptability of attacks depending on a set of argument is explored, and credulously accepted attacks w.r.t. a set of arguments are formally characterised by introducing regular renovation sets. Second, a new semantics, named regular semantics (r-semantics) is established for HO-AFs. Every complete (or conflict-free, admissible) set in Modgil’s semantics is complete (or conflict-free, admissible) in r-semantics. Some maximality-based r-semantics are just the argument part of the corresponding semantics of Baroni et al. Third, an efficient method is put forward to calculate these maximality-based Baroni’s semantics through r-semantics.
1 Introduction
The theory of argumentation frameworks (AF) [14] has been widely applied in artificial intelligence [19, 25, 27], such as multi-agent systems, decision making, non-monotonic reasoning, etc. Dung’s original framework has been extended in various forms, such as bipolar AFs [6–8, 11, 12], weighted AFs [1, 15, 24], probabilistic AFs [21, 22, 26], fuzzy AFs [18, 29–31], and so on. This paper is a further study of higher-order argumentation frameworks (HO-AFs) [9], which extend Dung’s AFs by allowing attacks on attacks.
HO-AFs have been proven to be a useful reasoning model adopted in many fields. For example, in [3], the notion of higher-order attacks is first introduced to demonstrate the strength of attacks and temporal dynamics. In [23], the preference-based AFs are studied by Modgil’s extended AFs (M-EAF), where the preference relation is transferred into attacks on attacks. In [4] and [5], coalitions are discussed based on HO-AFs.
In the literature, semantics of HO-AFs are generally built in two forms. The extensions in [2, 13] and [16] include both arguments and attacks. The extensions in [17, 20, 23] just contain arguments. Each of these two ways has its advantages. For instance, the semantics in [2, 13] and [16] choose more extensions. And the semantics in [17] and [23] can be calculated more efficiently by just checking the subsets of arguments.
These works provide theories covering many issues in HO-AFs. There are still some interesting problems in abstract HO-AFs.
(1) In [17], for each argument set |$S$|, the attacks inductively defended (i-defended) by |$S$| are called sceptically accepted w.r.t. |$S$|. Similarly to the “extension-dependent” validity in [10], this acceptability of attacks can be called “arguments-dependent”. For every complete set in [2, 9] and [16], if it includes |$S$|, then it contains (hence, accepts) these sceptically accepted attacks. However, there are also some attacks in the semantics in [2, 9] and [16], which are not sceptically accepted. Are these attacks ”arguments-dependent”? The first goal of this paper is to formally discuss the “argument-dependence” of these attacks.
(2) When calculating a semantics in [2, 9] and [16], since it includes both arguments and attacks, subsets of arguments and attacks should be checked. But for a semantics in [17] and [23], it only needs to check subsets of arguments, because the semantics only contain arguments. If a semantics in [2, 9] and [16] is transformed into a semantics including arguments only, then its calculation becomes more efficient. The second goal of this paper is to build such a semantics without attacks.
In this paper, by introducing the regular renovation sets, we first formally define a kind of accepted attacks, named credulously accepted attacks, w.r.t. an argument set. Then, a semantics of HO-AFs, named regular semantics (r-semantics), is built based on these credulously accepted attacks. The relations to the semantics in [23] and in [2] are discussed. Particularly, for a maximality-based semantics in [2], such as preferred sets, arg-preferred sets1 and stable sets, its argument part is a suitable semantics in r-semantics (r-para-preferred sets, r-preferred sets and r-stable sets, correspondingly), and its attack part is exactly composed of the credulously accepted attacks w.r.t. its argument part. Therefore, these maximality-based semantics in [2, 9] and [16], can be efficiently calculated by computing the corresponding sets in r-semantics.
This work develops the HO-AF theory in two aspects. In theory, it formally studies the credulously accepted attacks w.r.t. a set of arguments and establishes the r-semantics based on these attacks. This is an interesting supplement to the HO-AF theory. In practice, the preferred sets, the arg-preferred sets and the stable sets in [2, 9] and [16] are transformed into r-semantics, so they can be calculated efficiently.
The contents are organised as follows: The next section presents some basic terminology. Section 3 introduces the regular renovation sets and formally defines the credulously accepted attacks. Section 4 establishes the r-semantics. Section 5 discusses the relationship between r-semantics and some existing HO-AF semantics. Section 6 concludes. In addition, the proofs are presented in Appendix.
2 Terminology
In previous works, several HO-AFs have been introduced. In this paper, the attacks in an HO-AF are restricted to be on finite levels. On one hand, infinity may cause unexpected problems in theory, especially for credulous reasoners. On the other hand, in practice, HO-AFs within finite level attacks can cover most situations. Hence, in order to prevent the interference of the infinite level attacks, this paper uses the next defined HO-AFs [16, 17], which excludes infinite level attacks.
An HO-AF is a pair |$(Ar, \mathcal{R})$|, where |$Ar$| is a set of arguments and |$\mathcal{R}=\cup _{k=0}^{n}\mathcal{R}_{k}$|, for some |$n\in \mathbb{N}$|, recursively defines the attacks:
|$\mathcal{R}_{0}\subseteq Ar\times Ar$|,
|$\mathcal{R}_{k+1}\subseteq Ar\times \mathcal{R}_{k}$|, for all |$0\leq k< n$|.
In [16], an HO-AF in this definition is called a level |$(0, n)$| HO-AF, and an attack |$\alpha $| in |$R_{k}, k\leq n$|, is called a level |$(0, k)$| attack. In this paper, for convenience, |$\alpha \in \mathcal{R}_{k}$| is called a level |$k$| attack. Without special statement, when we mention an HO-AF in this paper, it is always a level |$(0,n)$| HO-AF.
For an attack |$\alpha \in \mathcal{R}$|, |$trg(\alpha )$| stands for the target element of |$\alpha $|, while |$src(\alpha )$| is its source argument. Obviously, |$src(\alpha )\in Ar$|, but |$trg(\alpha )\in Ar\cup \mathcal{R}$|.
An attack |$\alpha $| directly attacks an element |$\chi \in Ar\cup \mathcal{R}$|, iff |$\chi = trg(\alpha )$|. |$\alpha $| indirectly attacks an attack |$\beta $|, iff |$trg(\alpha )=src(\beta )$|. Moreover, |$\alpha \rightarrow _{R} \chi $| [2] means that |$\alpha $| directly or indirectly attacks |$\chi $|.
For a set |$S\subseteq Ar\cup \mathcal{R}$|, we redefine two symbols |$S^{+}$| and |$S^{-}$|. In the literature, they are sets of arguments. In this paper, they are sets of attacks: |$S^{+}=\{\alpha \in \mathcal{R}\colon src(\alpha )\in S\}$| and |$S^{-}=\{\alpha \in \mathcal{R}\colon trg(\alpha )\in S\}$|. Particularly, for an element |$\chi \in Ar\cup \mathcal{R}$|, |$\chi ^{-}=\{\alpha \in \mathcal{R}\colon trg(\alpha )=\chi \}$|. Obviously, |$\forall \alpha ,\beta \in \mathcal{R}$|, |$\beta \in \alpha ^{-}$| iff |$trg(\beta )=\alpha $|.
The HO-AF semantics are built similar to Dung’s semantics in [14]. The semantics are based on two key notions of acceptability and conflict-freeness. For example, admissible extensions are self-defended conflict-free sets and preferred extensions are maximal admissible extensions. Complete extensions are fixed points of the characteristic function. The difference is that in different papers, the acceptability and conflict-freeness are defined in different ways.
Consider the HO-AF in Figure 1, where |$Ar=\{A,B,C\}$| and |$\mathcal{R}=\{\alpha =(A,B), \beta =(B,C), \beta ^{\prime}=(B,\alpha ))\}$|.
A simple HO-AF.
In [23], the attack |$\alpha $| defeats |$B$|. Hence, |$\alpha $| recursively defends itself. Therefore, |$A$| defends |$C$| through |$\alpha $|. As a result, |$\{A,C\}$| is complete in [23]. Similarly, |$\{A,B\}$| is complete.
In [17], |$\alpha $| is not i-defended in finite steps. Hence, |$A$| cannot defend |$C$|. The complete sets in [17] are |$\{A\}$| and |$\{A,B\}$|.
In [2], an attack can work independently. Hence, |$\{B,\alpha \}$| is not conflict-free in [2]. And |$\alpha $| itself can defends |$C$| and |$\alpha $|. The complete sets in [2] are |$\{A\}$|, |$\{A,C,\alpha \}$| and |$\{A,B,\beta ,\beta ^{\prime}\}$|.
In [10] and [16], an attack is effective, only when it cooperates with its source argument. Hence, |$\{B,\alpha \}$| is conflict-free in [10] and [16], but |$\{A,B,\alpha \}$| is not. Neither |$A$| nor |$\alpha $| can defend |$C$| or |$\alpha $|, but |$\{A,\alpha \}$| can defend |$C$| and |$\alpha $|. The complete sets there are |$\{A,\beta ,\beta ^{\prime}\}$|, |$\{A,C,\alpha ,\beta ,\beta ^{\prime}\}$| and |$\{A,B,\beta ,\beta ^{\prime}\}$|.
3 Regular renovation sets and credulously accepted attacks
In the previous works, the validity of attacks depends on extensions [10]. In [9, 10, 16, 17] and [23], when an attack acts as a defender, it should defeat its target. In this case, it cooperates with its source element. Hence, its validity is related to its source argument. In [17], the sceptically accepted attacks are defined as the attacks which are i-defended within finite steps w.r.t. a set of arguments. For instance, consider the HO-AF in Example 1. The attacks |$\beta $| and |$\beta ^{\prime}$| are not attacked, i.e., they are i-defended within 0-steps w.r.t. any argument set including |$B$|. In the view of any sceptical reasoner, these i-defended attacks are accepted (or defended) w.r.t. the argument set [17]. However, the relationship between the attack |$\alpha $| and the argument set |$\{A\}$| is different. |$\alpha $| is recursively defended by the attacks in |$A^{+}=\{\alpha \}$|. But this recursive process continues endlessly, and cannot stop within finite steps. Therefore, a credulous reasoner may admit this acceptability, but a sceptical reasoner cannot. This section will formally study these credulously accepted attacks, like |$\alpha $|.
Before, it is necessary to clarify which attacks are credulously accepted w.r.t. a set of arguments. In this paper, credulously accepted attacks are required to play two roles. On one hand, they should be able to break the conflict-freeness. On the other hand, they can effectively defend other arguments and/or attacks. By studying the previous works, we put forward the next three conditions to credulously accepted attacks, where |$\alpha $| is a credulously accepted attack w.r.t. an argument set |$S$|.
Condition 1. |$\alpha $| should be recursively defended by |$S$| (or |$S^{+}$|). The attacks, which are not recursively defended by |$S$|, cannot be accepted. This condition is widely used in HO-AFs.
Condition 2. |$src(\alpha )\in S$|, i.e., |$\alpha \in S^{+}$|. In [17], the sources of all the i-defended attacks are in |$S$|. In [23], the sources of the attacks in each reinstatement set are in |$S$|. In [10] and [16], when an attack has impact on conflict-freeness or acceptability, it should cooperate with its source argument. For instance, in Example 1, |$\beta $| is in the complete set |$\{A,C,\alpha ,\beta \}$|. But |$\beta $| cannot effectively attack or defend anything, because its source |$B$| is not in |$\{A,C\}$|. In [2], though an attack can effectively attack some elements independently to its source, the source argument of every attack in a complete set is valid.
Condition 3. |$trg(\alpha )\notin S$|, i.e., |$\alpha \notin S^{-}$|. For a credulously accepted attack |$\alpha $|, from Condition 2, |$src(\alpha )\in S$|. If |$trg(\alpha )$| is also in |$S$|, then |$\alpha $| and |$src(\alpha )$|, |$trg(\alpha )$| are all accepted. It contradicts the conflict-freeness in [2, 13] and [16]. Therefore, the attacks, whose targets are in |$S$|, cannot be accepted.
The first and the second conditions can be represented by borrowing the notion of renovation sets from [20] and [28].
In an HO-AF |$(Ar,~\mathcal{R})$|, let |$S\subseteq Ar$| be a set of arguments. A set |$R_{S}\subseteq S^{+}$| is called a renovation set (abbreviated as R-set) w.r.t. |$S$|, iff |$\forall \beta \in R_{S}^{-}$| |$\exists \gamma \in R_{S}$| s.t. |$\gamma \rightarrow _{R}\beta $|.
Particularly, when an attack |$\alpha \in R_{S}$| is attracted special attention, |$R_{S}$| is called an R-set of |$\alpha $| w.r.t. |$S$|, denoted by |$R_{S}^\alpha $|.
In order to formally represent attacks which also satisfy the third condition, we introduce the regular R-sets.
In an HO-AF |$(Ar,~ \mathcal{R})$|, suppose |$S\subseteq Ar$| is a set of arguments. An R-set |$R_{S}$| is called regular w.r.t. |$S$|, iff |$\forall \alpha \in R_{S}$|, |$trg(\alpha )\notin S$|.
With the regular R-sets, credulously accepted attacks can be formally defined as follows:
Suppose |$S$| is an argument set in an HO-AF. An attack |$\alpha $| is called credulously accepted w.r.t. |$S$|, if and only if there is a regular R-set |$R_{S}$| such that |$\alpha \in R_{S}$|.
Obviously, credulously accepted attacks in this definition satisfy all the three conditions.
When the argument set |$S$| is obvious, without ambiguity, we just say an attack is credulously accepted.
Consider the HO-AF in Example 1.
The attack |$\alpha $| can recursively defend itself. Hence, |$\{\alpha \}$| is an R-set w.r.t. any set including |$A$|. The attacks |$\beta , \beta ^{\prime}$| are not directly attacked. Hence, they defend themselves, and |$\{\beta , \beta ^{\prime}\}$| is an R-set w.r.t. any set including |$B$|.
The set |$\{\alpha \}$| is a regular R-set w.r.t. |$\{A\}$| and |$\{A,C\}$|. Hence, |$\alpha $| is credulously accepted w.r.t. |$\{A\}$| and |$\{A,C\}$|.
On the other hand. |$\{\alpha \}$| is not regular w.r.t. |$\{A,B\}$|, because |$trg(\alpha )=B$|. Hence, |$\alpha $| is not credulously accepted w.r.t. |$\{A,B\}$|.
|$\{\beta , \beta ^{\prime}\}$| is a regular R-set w.r.t. |$\{A,B\}$|. Hence, these two attacks are credulously accepted w.r.t. |$\{A,B\}$|.
From this example, sceptically accepted attacks [17], e.g., |$\beta $| and |$\beta ^{\prime}$| w.r.t. |$\{A,B\}$|, are special credulously accepted.
Next, some useful properties of R-sets will be presented. The union of some R-sets w.r.t. |$S$| is still an R-set w.r.t. |$S$|. Accordingly, the union of all regular R-sets w.r.t. |$S$| is obviously a regular R-set w.r.t. |$S$|. Then, we introduce the next notion.
Suppose |$S$| is a set of arguments in an HO-AF. The union of all the regular R-sets w.r.t. |$S$| is called the greatest regular R-set w.r.t. |$S$|, denoted by |$R_{S}^{gr}$|.
Obviously, |$R_{S}^{gr}$| is the set of all the attacks which are credulously accepted w.r.t. |$S$|.
In an HO-AF |$(Ar,~ \mathcal{R})$|, suppose |$S\subseteq Ar$| and |$\alpha \in \mathcal{R}$|. Then, |$\alpha \in R_{S}^{gr}$|, if and only if there is some regular R-set |$R_{S}^\alpha $| of |$\alpha $| w.r.t. |$S$|.
Suppose |$S\subseteq Ar$| is a set of arguments in an HO-AF |$(Ar,~ \mathcal{R})$|. Then, we have |$\forall \alpha ,\beta \in R_{S}^{gr}$|, |$trg(\alpha )\neq \beta $|.
Complete R-sets are introduced in [28]. Here we introduce sufficient R-sets. These two kinds of R-sets will be applied to study the relationship to existing HO-AF semantics.
Let |$(Ar,~ \mathcal{R})$| be an HO-AF and |$S\subseteq Ar$|. An R-set |$R_{S}\subseteq \mathcal{R}$| is called complete w.r.t. |$S$|, iff |$R_{S}=\{\alpha \in S^{+} \colon \forall \beta \in \alpha ^{-}\ \exists \gamma \in R_{S} \ s.t. \ \gamma \rightarrow _{R}\beta \}$|.
Let |$(Ar,~ \mathcal{R})$| be an HO-AF and |$S\subseteq Ar$|. An R-set |$R_{S}\subseteq \mathcal{R}$| is called sufficient w.r.t. |$S$|, iff |$\forall \alpha \in S^{-}$| |$\exists \beta \in R_{S}$| s.t. |$\beta \rightarrow _{R} \alpha $|.
Intuitively, a complete R-set cannot recursively defend more attacks in |$S^{+}$|. A sufficient R-set |$R_{S}$| recursively defends every argument in |$S$|.
Consider the HO-AF in Example 1. The empty set |$\emptyset $| is an R-set, which is both complete and regular w.r.t. |$\{A,C\}$|. However, for |$\beta \in{\{C\}^{-}}$|, |$\nexists \alpha \in \emptyset $| such that |$\alpha \rightarrow _{R}\beta $|. Hence, |$\emptyset $| is not a sufficient R-set w.r.t. |$\{A,C\}$|.
The set |$\{\beta ^{\prime}\}$| is a sufficient regular R-set w.r.t. |$\{A, B\}$|.
However, since |$\beta $| is not attacked, every complete set w.r.t. a set including |$B$| should contain |$\beta $|. Hence, |$\{\beta ^{\prime}\}$| is not complete w.r.t. |$\{A, B\}$|.
The set |$\{\beta ,\beta ^{\prime}\}$| is the unique sufficient complete regular R-set w.r.t. |$\{A,B\}$|.
The set |$\{\alpha \}$| is the unique sufficient complete regular R-set w.r.t. |$\{A,C\}$| or |$\{A\}$|.
4 r-semantics for an HO-AF
In this section, a new credulous semantics will be established based on the credulously accepted attacks. Since the key tool is the regular R-sets, the new semantics is named as the r-semantics of HO-AFs.
4.1 Conflict-free sets and acceptability
In [17], an argument set |$S$| is conflict-free, if and only if there are no sceptically accepted attacks between arguments in |$S$|. Similarly, we can define r-conflict-free sets using credulously accepted attacks. But in this case, there are some unnatural conflict-free sets. For example, in the HO-AF, where |$Ar=\{A,B,C\}$| and |$\mathcal{R}=\{(A,B),(C,(A,B))\}$|. The set |$\{A,B\}$| without |$C$|, which refutes the attack |$(A,B)$|, is still conflict-free. To avoid such situations, we strengthen the conflict-free sets as follows:
In an HO-AF |$(Ar, \mathcal{R})$|, |$S\subseteq Ar$| is called r-conflict-free, iff for any attack between arguments in |$S$|, there exists a credulously accepted attack w.r.t. |$S$| attacking it, i.e., |$\forall \alpha \in S^{+}\cap S^{-}$| |$\exists \beta \in R_{S}^{gr}$| s.t. |$trg(\beta )=\alpha $|.
Consider the HO-AF in Example 1. The r-conflict-free sets are |$\emptyset $|, |$\{A\},\ \{A,B\},\ \{A,C\},\ \{B\}$| and |$\{C\}$|.
The next proposition shows that for an r-conflict-free set |$S$|, there are no credulously accepted attacks between arguments in |$S$|.
In an HO-AF |$(Ar, \mathcal{R})$|, let |$S$| be an r-conflict-free set. For any |$(A,B)\in \mathcal{R}$| with |$A,B\in S$|, |$(A,B)\notin R_{S}^{gr}$|.
Similar to [17], the acceptability is still defined by attacking the attackers directly or indirectly. The difference is the application of credulously accepted attacks.
In an HO-AF |$(Ar,\mathcal{R})$|, an element |$\chi \in Ar\cup \mathcal{R}$| is regularly defended (r-defended) by a set |$S\subseteq Ar$|, iff |$\forall \beta \in \chi ^{-}$| |$\exists \alpha \in R_{S}^{gr}$| s.t. |$\alpha \rightarrow _{R} \beta $|.
For convenience, a regular R-set |$R_{S}$| is also said to r-defend an element |$\chi \in Ar\cup \mathcal{R}$|, if |$\forall \beta \in \chi ^{-}$| |$\exists \alpha \in R_{S}$| s.t. |$\alpha \rightarrow _{R} \beta $|.
Consider the HO-AF in Example 1. The set |$\{A\}$| r-defends the arguments |$A, C$| and the attacks |$\alpha $|, |$\beta $| and |$\beta ^{\prime}$|.
The set |$\{A,B\}$| (or |$\{B\}$|) r-defends |$A,B$|, |$\beta $| and |$\beta ^{\prime}$|, but it does not r-defend |$\alpha $|.
Note that the set |$\{A,C\}$| r-defends |$\beta $| and |$\beta ^{\prime}$|, because they are not directly attacked. But |$\beta ,\beta ^{\prime}$| are not in |$R_{\{A,C\}}^{gr}=\{\alpha \}$|, because |$src(\beta )=src(\beta ^{\prime})=B\notin \{A,C\}$|.
The next lemma seems to be a variation of the Fundamental Lemma. It will be applied to prove the Fundamental Lemma.
In an HO-AF |$(Ar,\mathcal{R})$|, suppose |$S\subseteq Ar$| and |$A\in Ar$|. If |$S$| r-defends |$A$|, then each regular R-set |$R_{S}$| w.r.t. |$S$| is also a regular R-set w.r.t. |$S_{1}=S\cup \{A\}$|.
Based on the acceptability, the characteristic function can be defined.
R-admissibility is defined as follows:
In an HO-AF |$(Ar,\mathcal{R})$|, an r-conflict-free set |$S\subseteq Ar$| is r-admissible, iff it r-defends each argument in it, i.e., |$S\subseteq F_{r}(S)$|.
Consider the HO-AF in Example 1. The r-admissible sets are |$\emptyset $|, |$\{A\},\ \{A,B\},\ \{A,C\}$| and |$\{B\}.$| The set |$\{C\}$| is not r-admissible.
In addition, |$\{A\}\subseteq \{A,B\}$|, but |$F_{r}(\{A\})=F_{r}(\{A,C\})=\{A,C\}$| is not a subset of |$F_{r}(\{A,B\})=\{A,B\}=F_{r}(\{B\})$|.
This example shows that the characteristic function |$F_{r}$| is not monotonic. But for the r-admissible sets, the Fundamental Lemma holds.
In an HO-AF |$(Ar,\mathcal{R})$|, suppose |$S\subseteq Ar$| is an r-admissible set and |$A,A^{\prime}\in Ar$| are r-defended by |$S$|. Then,
|$S_{1}=S\cup \{A\}$| is r-admissible; and
|$A^{\prime}$| is r-defended by |$S_{1}$|.
For r-admissible sets, the next lemma holds.
Let |$S\subseteq Ar$| be a set of arguments in an HO-AF |$(Ar,\mathcal{R})$|. If |$S$| is an r-admissible set, then its greatest regular R-set |$R_{S}^{gr}$| is both sufficient and complete w.r.t. |$S$|.
4.2 Extensions
Similar to previous works, extension-based semantics can be defined based on r-conflict-freeness and r-acceptability.
In an HO-AF |$(Ar, \mathcal{R})$|, an r-conflict-free set |$S\subseteq Ar$| is called
r-complete (r-CE), iff |$F_{r}(S)=S$|;
r-preferred (r-PE), iff it is a maximal r-admissible set;2
r-stable (r-SE), iff |$\forall A\in Ar\setminus S$| |$\exists \alpha \in R_{S}^{gr}$| such that |$trg(\alpha )=A$|.
Note, Definition 6 introduces complete R-sets, which are sets of attacks. And here, in Definition 12, we defined r-complete sets, which are sets of arguments.
Consider the HO-AF in Example 1. The r-complete sets are |$\{A,B\}$| and |$\{A,C\}$|. They are also r-preferred and r-stable. Different from previous semantics, the next example shows that an r-stable set may not be r-preferred.
Consider the HO-AF in Figure 2, where |$Ar=\{A_{1},A_{2},B_{1},B_{2}\}$| and |$\mathcal{R}=\{\alpha _{1}=(A_{1},B_{1}),\alpha _{2}=(A_{2},B_{2}), \beta _{1}=(B_{1},\alpha _{2}),\beta _{2}=(B_{2},\alpha _{1})\}$|.
An HO-AF for Example 7.
The sets |$\{A_{1},A_{2}\}$| and |$\{A_{1},A_{2},B_{1},B_{2}\}$| are r-stable.
The unique r-preferred set is |$\{A_{1},A_{2},B_{1},B_{2}\}$|.
Hence, |$\{A_{1},A_{2}\}$| is r-stable, but not r-preferred.
In order to identify sets like |$\{A_{1},A_{2}\}$| in this example, we introduce the next kind of extensions.
In an HO-AF |$(Ar, \mathcal{R})$|, an r-complete set |$S\subseteq Ar$| is called r-para-preferred (r-PP), iff its greatest R-set is maximal, i.e., there is no r-complete set |$S^{\prime}$| s.t. |$R_{S}^{gr}\subsetneq R_{S^{\prime}}^{gr}$|.
Obviously, |$\{A_{1},A_{2}\}$| is r-para-preferred, because |$\{\alpha _{1},\alpha _{2}\}$| is maximal.
Note, the r-completeness in the definition of r-para-preferred sets cannot be replaced by r-admissibility.
Consider the HO-AF in Example 1.
The r-admissible set |$\{A\}$| is not r-complete. Hence, it is not r-para-preferred, though |$R_{\{A,C\}}^{gr}=\{\alpha \}$| is maximal.
The r-admissible set |$\{B\}$| is not r-complete, because it r-defends |$A$|. Hence, it is not r-para-preferred, though |$R_{\{B\}}^{gr}=\{\beta ,\beta ^{\prime}\}$| is maximal.
In the classical AF=|$(\{A\},\{(A,A)\})$|, which is also a special HO-AF of level 0, the empty set |$\emptyset $| is both r-preferred and r-para-preferred, but it is not r-stable. In that AF, there is no r-stable set.
The next result follows immediately from the Fundamental Lemma.
Let |$(Ar, \mathcal{R})$| be an HO-AF. 1. The set of all r-admissible sets forms a complete partial order w.r.t. set inclusion. 2. For each r-admissible set |$S$|, there exists an r-preferred |$S^{\prime}$| such that |$S\subseteq S^{\prime}$|.
Since |$\emptyset $| is an r-admissible set of every HO-AF, then Theorem 1 implies that
Every HO-AF possesses at least one r-preferred set.
Similar to the semantics in [23], the least r-complete set does not always exist (see Example 8). Hence, the r-grounded set should not be defined to be the least r-complete set. Here, we establish the r-grounded set by the characteristic functions in finitary HO-AFs, where an HO-AF |$(Ar, \mathcal{R})$| is called finitary, if for all |$\chi \in Ar\cup \mathcal{R}$|, |$\chi ^{-}$| is finite. For the characteristic functions |$F_{r}$|, denote |$F^{1}_{r}(S)=F_{r}(S)$| and |$F_{r}^{n+1}(S)=F_{r}(F_{r}^{n}(S))$|, |$\forall n\geq 1$|.
Suppose |$(Ar, \mathcal{R})$| is a finitary HO-AF and |$\emptyset $| is the empty set. The set |$G_{r}=\cup _{n=1}^\infty F_{r}^{n}(\emptyset )$| is called r-grounded.
Consider the HO-AF in Example 1. The r-grounded set is |$G_{r}=\{A,C\}$|, Because |$F_{r}(\emptyset )=\{A\}$|, and |$F_{r}(\{A\})=\{A,C\}=F_{r}(\{A,C\})$|.
The r-complete set |$\{A,B\}$| is not r-grounded, because |$B$| is not r-defended by |$\{A\}$|.
Obviously, in an HO-AF, the r-grounded set is unique. In this example, |$\{A,C\}$| is not a subset of the r-complete set |$\{A,B\}$|. Hence, the r-grounded set is not the least r-complete one.
The relations among these kinds of r-semantics are similar to previous semantics and shown in the next theorem.
The next relations are valid. But not vice versa.
(1) Every r-admissible set (r-AD) is r-conflict-free (r-CF).
(2) Every r-complete set is r-admissible.
(3) Every r-para-preferred set is r-complete.
(4) Every r-preferred set is r-para-preferred.
(5) Every r-stable set is r-para-preferred.
(6) The r-grounded set (r-GE) is a minimal r-complete set.
The relationship in this theorem can be shown intuitively in Figure 3. In this figure, r-PE|$\Rightarrow $|r-PP means that each r-preferred set is r-para-preferred. Others are similar.
The relationship between the r-semantics in Theorem 2.
5 Relation to previous semantics
In this section, r-semantics will be compared with some existing HO-AF semantics. The m-semantics [23] and the semantics in [2] (bcgg-semantics) will be compared in detail. Other semantics will be briefly discussed in Subsection 5.4.
5.1 Relation to the semantics of Modgil
A Modgil’s extended argumentation framework (an M-EAF) [23] is a tuple |$(Ar, \mathcal{R}_{0}, \mathcal{R}_{1})$|, where |$Ar$| is a set of arguments, |$\mathcal{R}_{0}\subseteq Ar\times Ar$|, |$\mathcal{R}_{1}\subseteq Ar\times \mathcal{R}_{0}$|, and satisfying a special condition:
Obviously, each M-EAF is an HO-AF |$(Ar, \mathcal{R})$| satisfying |$\mathcal{R}=\mathcal{R}_{0}\cup \mathcal{R}_{1}$| and the special condition.
In an M-EAF, for |$S\subseteq Ar$|, an argument |$A$| defeats|$^{S}$| an argument |$B$|, denoted by |$A\rightarrow ^{S} B$|, iff |$(A,B)\in \mathcal{R}_{0}$| and |$\nexists C\in S$| s.t. |$(C,(A,B))\in \mathcal{R}_{1}$|. Denote |$Defeat^{S}=\{(A,B)\colon A\rightarrow ^{S} B, ~\forall A,B\in Ar\}$|.
A set |$S\subseteq Ar$| is m-conflict-free, iff |$\forall A,B\in S$|: if |$(A, B) \in \mathcal{R}_{0}$|, then |$(B, A)\notin \mathcal{R}_{0}$| and |$\exists C \in S$| s.t. |$(C, (A, B)) \in \mathcal{R}_{1}$|. In this definition, the condition |$(B,A)\notin \mathcal{R}_{0}$| is taken from the representation of the preference AFs. Here, in order to compare to the r-semantics conveniently in abstract M-EAFs, it is translated into another form: A set |$S\subseteq Ar$| is m-conflict-free, iff |$\forall A,B\in S$|, |$(A,B)\notin Defeat^{S}$| and
A set |$R_{S}=\{X_{1}\rightarrow ^{S} Y_{1},...,~ X_{n}\rightarrow ^{S} Y_{n}\}$| is called a reinstatement set for |$A\rightarrow ^{S} B$| w.r.t. |$S$|, iff the next three conditions hold:
1. |$A\rightarrow ^{S} B\in R_{S}$|; 2. for |$i=1,...,n$|, |$X_{i}\in S$|; 3. |$\forall X\rightarrow ^{S} Y\in R_{S}$|, |$\forall Y^\prime $| s.t. |$(Y^\prime ,(X,Y))\in \mathcal{R}_{1}$|, there is an |$X^\prime \rightarrow ^{S} Y^\prime \in R_{S}$|.
Consequently, |$S\subseteq Ar$| m-defends |$A\in Ar$|, iff |$\forall B$| s.t. |$B\rightarrow ^{S} A$| |$\exists C\in S$| s.t. |$C\rightarrow ^{S} B$| and there is a reinstatement set for |$C\rightarrow ^{S} B$|. The m-characteristic function |$F_{m}\colon 2^{Ar}\longrightarrow 2^{Ar}$| is defined as |$\forall S\subseteq Ar$|, |$F_{m}(S)=\{A\in Ar\colon A$| is m-defended by |$S\}$|.
In an M-EAF |$(Ar, \mathcal{R})$|, an m-conflict-free set |$S\subseteq Ar$| is
m-admissible, iff |$S\subseteq F_{m}(S)$|;
m-preferred, iff it is a maximal m-admissible set;
m-complete, iff |$S = F_{m}(S)$|;
m-grounded, iff |$S=\cup _{n=1}^\infty F_{m}^{n}(\emptyset )$| and the M-EAF is finitary;
m-stable, iff |$\forall A\notin Ar\subseteq S$| |$\exists B\in S$| s.t. |$B\rightarrow ^{S} A$|.
To compare the two semantics, we first represent the defeat|$^{S}$| by R-sets.
In an M-EAF |$(Ar,\mathcal{R})$|, suppose |$S\subseteq Ar$| is a set of arguments and |$A,B$| are two arguments. |$(A,B)\notin Defeat^{S}$|, iff either |$(A,B)\notin \mathcal{R}$| or |$R_{S}^{gr}\cap{(A, B)}^{-}\neq \emptyset $|.
Equivalently, |$(A,B)\in Defeat^{S}$|, iff |$(A,B)\in \mathcal{R}$| and |$R_{S}^{gr}\cap{(A, B)}^{-} = \emptyset $|.
The next example shows the difference between m-conflict-freeness and the r-conflict-freeness.
Consider the M-EAF in Figure 4, which is taken from [23], where |$Ar=\{A,B,C,D\}$| and |$\mathcal{R}=\{(A,B),(B,A),(C,D),(D,C),$| |$(A,(C,D)),$| |$(B,(D,$| |$C)),$| |$(C,(B,A)),(D,(A,B))\}$|.
An M-EAF for Example 10.
The set |$\{A,B,C,D\}$| is r-conflict-free. But it is not m-conflict-free, because both |$(A,B)$| and |$(B,A)$| are in |$\mathcal{R}_{0}$|.
Actually, except the set with arguments attacking each other, the two conflict-freeness coincides.
In an M-EAF |$(Ar,\mathcal{R})$|, an argument set |$S\subseteq Ar$| is m-conflict-free, iff it is r-conflict-free and the condition (M) holds.
Next lemma shows the relationship between reinstatement sets and regular R-sets.
In an M-EAF |$(Ar,\mathcal{R})$|, suppose |$S\subseteq Ar$| is r-conflict-free and |$R_{S}\subseteq S^{+}$|. |$R_{S}$| is a regular R-set of |$\alpha _{0}\in \mathcal{R}_{0}$| w.r.t. |$S$|, iff |$R_{S}\cap \mathcal{R}_{0}$| is a reinstatement set for |$\alpha _{0}$| w.r.t. |$S$|.
Equivalently, for any |$\alpha _{0}\in \mathcal{R}_{0}$|, |$\alpha _{0}\in R_{S}^{gr}$|, iff there is a reinstatement set for |$\alpha _{0}$| w.r.t. |$S$|.
Suppose |$S$| is an r-conflict-free set in an M-EAF |$(Ar,\mathcal{R})$|. |$S$| m-defends an argument |$A$|, iff |$S$| r-defends |$A$|.
From Theorems 3 and 4, we directly obtain the next theorem.
In an M-EAF |$(Ar,\mathcal{R})$|, suppose that |$S\subseteq Ar$| satisfies the condition (M). Then, |$S$| is
m-admissible iff it is r-admissible;
m-complete iff it is r-complete;
m-grounded iff it is r-grounded;
m-stable iff it is r-stable;
m-preferred if it is r-preferred.
From this theorem, every m-complete (m-admissible) set is an r-complete (r-admissible) set. Together with that each m-conflict-free set is r-conflict-free (Theorem 3), we can say that r-semantics well covers m-semantics.
Note that the converse of the last item in this theorem does not hold. For example, in the M-EAF in Figure 4, the m-preferred set is |$\emptyset $|, but it is not r-preferred. In fact, an m-preferred set is maximal among the r-admissible sets which satisfy condition (M), while an r-preferred set is maximal among all the r-admissible sets.
Generally speaking, the difference between the two semantics lies in the condition (M). Therefore, we can say that r-semantics well covers m-semantics. M-semantics is a credulous semantics based on credulously accepted attacks in M-EAFs.
5.2 Relation to the semantics of Baroni et al.
In this subsection, we will show the relation between r-semantics and bcgg-semantics [2] in a level |$(0,n)$| HO-AF. Before that, let us introduce some symbols and recall the bcgg-semantics.
For |$S\subseteq Ar\cup \mathcal{R}$|, denote:
|$S_{A}=S\cap Ar$|, the set of arguments in |$S$|;
|$S_{R}=S\cap \mathcal{R}$|, the set of attacks in |$S$|;
|$S_{c}=S_{R}\cap S_{A}^{+}$|, the set of attacks in |$S$| whose sources are in |$S_{A}$|;
|$S_{a}=S_{R}\setminus S_{c}$|, the set of attacks in |$S$| whose sources are not in |$S_{A}$|;3
|$src(S_{R})=\{src(\alpha )\in Ar\colon \alpha \in S_{R}\}$|, the source arguments of attacks in |$S_{R}$|.
In an HO-AF |$(Ar, \mathcal{R})$|, a set |$S \subseteq Ar \cup \mathcal{R}$| is bcgg-conflict-free, iff there are no |$\alpha , \chi \in S$| s.t. |$\alpha \rightarrow _{R}\chi $|. And obviously, the next lemma is valid.
In an HO-AF |$(Ar, \mathcal{R})$|, suppose |$S$| is an r-conflict-free set and |$R_{S}$| is a regular R-set w.r.t. |$S$|. Then, |$S\cup R_{S}$| is bcgg-conflict-free.
In an HO-AF |$(Ar, \mathcal{R})$|, |$\chi \in Ar \cup \mathcal{R}$| is bcgg-defended by |$S\subseteq Ar\cup \mathcal{R}$|, iff for each |$\alpha \in \chi ^{-}$|, there is |$\beta \in S$| s.t. |$\beta \rightarrow _{R} \alpha $|.
In an HO-AF |$(Ar, \mathcal{R})$|, a bcgg-conflict-free set |$S\subseteq Ar\cup \mathcal{R}$| is
bcgg-admissible, iff it bcgg-defends each element in it;
bcgg-preferred, iff it is a maximal bcgg-admissible set;
bcgg-arg-preferred, iff it is bcgg-preferred and |$S_{A}$| is maximal, i.e., for any bcgg-preferred set |$S^{\prime}$|, |$S_{A}$| is not properly contained in |$S^{\prime}_{A}$|.
bcgg-complete, iff it is bcgg-admissible and includes every argument it bcgg-defends;
bcgg-grounded, iff it is the least bcgg-complete extension;
bcgg-stable, iff |$\forall \chi \notin S$| |$\exists \alpha \in S_{R}$| s.t. |$\alpha \rightarrow _{R} \chi $|.
The next lemma shows some properties of bcgg-admissible sets.
Suppose |$S\subseteq Ar\cup \mathcal{R}$| is bcgg-admissible in an HO-AF |$(Ar, \mathcal{R})$|.
(1) If an attack |$\alpha $| is bcgg-defended by |$S$|, then |$src(\alpha )$| is bcgg-defended by |$S$|.
(2) |$S_{R}$| is a sufficient regular R-set w.r.t. |$S_{A}\cup src(S_{R})$|.
(3) If |$\chi \in Ar\cup \mathcal{R}$| is bcgg-defended by |$S_{R}$|, then |$\chi $| is r-defended by |$S_{R}$|.
(4) |$S_{A}\cup src(S_{R})$| is r-conflict-free.
(5) If |$\chi \in Ar\cup S_{A}^{+}$| is r-defended by |$S_{R}$|, then |$\chi $| is bcgg-defended by |$S_{R}$|.
Based on this lemma, some theorems to represent the relationship between r-semantics and bcgg-semantics are obtained.
Suppose |$S\subseteq Ar\cup \mathcal{R}$| is a set of arguments and attacks in an HO-AF |$(Ar, \mathcal{R})$|. |$S$| is bcgg-admissible, iff |$S^{\prime}=S_{A}\cup src(S_{R})$| is r-admissible and |$S_{R}$| is a sufficient regular R-set w.r.t. |$S^{\prime}$|.
In general, for a bcgg-admissible set, |$S_{c}\subseteq S_{R}$|. But for a bcgg-complete set |$S$|, obviously from Lemma 9 (1), |$S_{R}=S_{c}$|.
In an HO-AF |$(Ar, \mathcal{R})$|, if |$S_{A}\subseteq Ar$| is an r-complete set, then |$S_{A}\cup R_{S_{A}}^{gr}$| is a bcgg-complete set. But not vice versa.
Consider the HO-AF in Example 1. The set |$S=\{A\}$| is bcgg-complete, where |$S_{A}=\{A\}$| and |$S_{R}=\emptyset $|. But |$\{A\}$| is not r-complete, because it r-defends |$\{C\}$|.
It is well known that i-semantics represent the argument part of grounded bcgg-grounded sets [17]. The next theorems show that r-semantics represent the argument part of maximality-based bcgg-semantics well.
In an HO-AF |$(Ar, \mathcal{R})$|, |$S\subseteq Ar\cup \mathcal{R}$| is a bcgg-preferred set, iff |$S_{A}$| is an r-para-preferred set and |$S_{R}=R_{S_{A}}^{gr}$|.
In an HO-AF |$(Ar, \mathcal{R})$|, |$S\subseteq Ar\cup \mathcal{R}$| is a bcgg-arg-preferred set, iff |$S_{A}$| is an r-preferred set and |$S_{R}=R_{S_{A}}^{gr}$|.
In an HO-AF |$(Ar, \mathcal{R})$|, |$S\subseteq Ar\cup \mathcal{R}$| is a bcgg-stable set, iff |$S_{A}$| is r-stable and |$S_{R}=R_{S_{A}}^{gr}$|.
In general, the r-grounded set is not the argument part of the bcgg-grounded set.
Consider the HO-AF in Example 1. The set |$S=\{A\}$| is bcgg-grounded, where |$S_{A}=\{A\}$| and |$S_{R}=\emptyset $|. But the r-grounded set is |$\{A,C\}\neq S_{A}$|.
5.3 An algorithm
From Theorems 8, 9 and 10, there is a one-to-one correspondence between r-para-preferred (r-preferred or r-stable, respectively) sets and bcgg-preferred (bcgg-arg-preferred or bcgg-stable, respectively) sets. For each bcgg-preferred set, its argument part |$S_{A}$| is just an r-para-preferred set and its attack part |$S_{R}$| is the greatest regular R-set w.r.t. |$S_{A}$|.
This indicates a novel algorithm for these maximality-based bcgg-semantics. The bcgg-preferred sets can be calculated efficiently by computing the corresponding r-para-preferred sets together with their greatest regular R-sets.
For a set |$S$| of arguments, from the definition of R-set, every R-set w.r.t. |$S$| is a subset of |$S^{+}$|. From the definition of regular R-set, each regular R-set w.r.t. |$S$| contains no elements in |$S^{-}$|. Therefore, as a special regular R-set, |$R_{S}^{gr}$| is a subset of the set |$S^{+}\setminus S^{-}$|. And it can be calculated by checking the subsets of |$S^{+}\setminus S^{-}$|. The complexity is no more than |$2^{S^{+}\setminus S^{-}}$|.
The set of all the r-complete set can be calculated by checking subsets of the argument set |$Ar$|. An algorithm is given by Table 1. When neglecting the computation of |$R_{S}^{gr}$|, the complexity is no more than |$2^{Ar}$|. And if the computation of |$R_{S}^{gr}$| is considered, then the complexity is no more than |$2^{Ar}\times 2^{S^{+}\setminus S^{-}}=2^{Ar\cup (S^{+}\setminus S^{-})}$|.
An algorithm for complete sets in an HO-AF
| step 1: | Take |$S \in 2^{Ar}$| and |$CS=\emptyset $|; |
|---|---|
| step 2: | Calculate |$R_{S}^{gr}$|; |
| step 3: | If |$F(S)=S$|, |
| let |$CS=CS\cup \{S\}$|; | |
| step 4: | Let |$2^{Ar}\setminus \{S\}$|; |
| step 5: | If |$2^{Ar}\neq \emptyset $|, |
| Turn to step 1; | |
| else Output |$CS$|, end; |
| step 1: | Take |$S \in 2^{Ar}$| and |$CS=\emptyset $|; |
|---|---|
| step 2: | Calculate |$R_{S}^{gr}$|; |
| step 3: | If |$F(S)=S$|, |
| let |$CS=CS\cup \{S\}$|; | |
| step 4: | Let |$2^{Ar}\setminus \{S\}$|; |
| step 5: | If |$2^{Ar}\neq \emptyset $|, |
| Turn to step 1; | |
| else Output |$CS$|, end; |
An algorithm for complete sets in an HO-AF
| step 1: | Take |$S \in 2^{Ar}$| and |$CS=\emptyset $|; |
|---|---|
| step 2: | Calculate |$R_{S}^{gr}$|; |
| step 3: | If |$F(S)=S$|, |
| let |$CS=CS\cup \{S\}$|; | |
| step 4: | Let |$2^{Ar}\setminus \{S\}$|; |
| step 5: | If |$2^{Ar}\neq \emptyset $|, |
| Turn to step 1; | |
| else Output |$CS$|, end; |
| step 1: | Take |$S \in 2^{Ar}$| and |$CS=\emptyset $|; |
|---|---|
| step 2: | Calculate |$R_{S}^{gr}$|; |
| step 3: | If |$F(S)=S$|, |
| let |$CS=CS\cup \{S\}$|; | |
| step 4: | Let |$2^{Ar}\setminus \{S\}$|; |
| step 5: | If |$2^{Ar}\neq \emptyset $|, |
| Turn to step 1; | |
| else Output |$CS$|, end; |
When the set |$CS$| of r-complete sets is output by the algorithm above, the r-para-preferred sets, the r-preferred sets and r-stable sets can be chosen in |$CS$|. Consequently, the bcgg-preferred sets, bcgg-arg-preferred sets and bcgg-stable sets are the corresponding r-semantics together with |$R_{S}^{gr}$|. The complexity is around |$2^{Ar\cup (S^{+}\setminus S^{-})}$|.
Note 1: In addition to the traversal method discussed, there are more methods to calculate the bcgg-preference set, such as the SCC method, the labelling method, etc. In our opinion, most of these methods may also hold for computing r-preferred sets, when |$R_{S}^{gr}$| has been calculated. Hence, the approach to calculate bcgg-preferred sets through r-para-preferred sets is still efficient.
Note 2: The computation of |$R_{S}^{gr}$| is a separate process. Due to its special attribute, the computation may be further simplified. If so, the computation of r-complete sets will be more efficient. For example, taking account of its maximality, for each argument set |$S$|, |$R_{S}^{gr}$| can be calculated as follows: Since any regular R-set |$R_{S}$| is included in |$R_{S}^{gr}$|, when |$R_{S}$| is checked to be a regular R-set, any set not including |$R_{S}$| cannot be |$R_{S}^{gr}$|. Hence, |$R_{S}^{gr}$| can be found in the set |$\{S\subseteq S^{+}\setminus S^{-}| R_{S}\subseteq S\}$|.
This paper concentrates on the way to calculate bcgg-semantics by transforming it into r-semantics. The research on other algorithms, such as efficient algorithms of |$R_{S}^{gr}$|, SCC-recursive method, etc., is left for the future.
5.4 Discussion
In the literature, HO-AFs have been studied in many papers. In this subsection, we will briefly discuss the relationship to some closely related works.
In [20] and [28], the concept of R-sets is introduced and is applied to discuss the relation between the argument parts and the attack parts of the extensions in [2, 10, 16] and [17]. This paper is a natural continuation of them. The r-semantics is established based on R-sets, where the Fundamental Lemma is valid. This shows that the concept of R-sets is a meaningful tool to build HO-AF semantics.
In [23], m-semantics is built in M-EAFs for the preference-based argumentation. In Subsection 5.1, the relation between r-semantics and m-semantics is discussed. In an M-EAF, each m-complete (or m-conflict-free, m-admissible) set is an r-complete (or r-conflict-free, r-admissible, correspondingly) set satisfying the condition (M). Therefore, in the field of completeness, conflict-freeness and admissibility, r-semantics covers m-semantics.
In [17], the i-semantics is introduced as a credulous semantics based on sceptically accepted attacks. Here, the r-semantics is a credulous semantics based on credulously accepted attacks. Hence, an r-preferred set covers the most credulously accepted arguments, while the i-grounded set selects the most sceptically accepted arguments.
In [2], bcgg-semantics is put forward to accommodate various kinds of representation and reasoning needs related to recursive attacks. In Subsection 5.2, we present a one-to-one correspondence between r-para-preferred sets and the bcgg-preferred sets (Theorem 8). In [17], the i-grounded sets are proven to be the argument parts of the bcgg-grounded sets. Hence, in the range of the bcgg-semantics, the maximality-based r-semantics correspond to the maximality-based bcgg-semantics, and the i-grounded sets correspond to the least bcgg-semantics.
There are also some HO-AF semantics, including both arguments and attacks [10, 16]. Although these semantics are built for different motivations and in different methods, for each semantics, its argument part is the same as the corresponding bcgg-semantics [28]. The difference is that these semantics accepts the appendant attacks, but the bcgg-semantics just accepts the core attacks. Therefore, from the relationship between bcgg-semantics and r-semantics, the maximality-based semantics in these works can also be represented and calculated by the corresponding r-semantics.
6 Conclusion
The notion of HO-AFs is a useful reasoning tool. This paper is a further study of HO-AF semantics. Firstly, we introduce the concept of regular R-sets and formally represent the credulously accepted attacks. Then, r-conflict-freeness and r-acceptability are defined by credulously accepted attacks. Consequently, the regular HO-AF semantics are established as a credulous semantics based on credulously accepted attacks, including r-admissible sets, r-complete sets, r-preferred sets, r-para-preferred sets, etc. Moreover, we show that r-semantics well covers the m-semantics by adding the condition (M). And r-para-preferred (r-preferred and r-stable) sets precisely represent the argument part of bcgg-preferred (bcgg-arg-preferred and bcgg-stable sets, respectively).
This work is a development in HO-AFs. In theory, it formally defines credulously accepted attacks and builds a new semantics. On one hand, the new semantics covers m-semantics in the sense of completeness, admissibility and conflict-freeness. On the other hand, the argument parts of some maximality-based semantics in [2, 10] and [16] are just the maximality-based r-semantics. Consequently, in practice, these maximality-based semantics in [2, 10] and [16] can be calculated efficiently by being transformed into r-semantics.
In the future, the labelling theory of HO-AFs can be discussed based on credulously accepted attacks. And an argument-based HO-AF semantics, which can represent the argument part of the bcgg-complete sets, can be explored. Moreover, HO-AFs with support relation can be investigated by the R-set method.
Acknowledgements
This work is supported by the National Natural Science Foundation of China (11601288) and the Natural Science Foundation of Shandong (ZR2016AQ21).
Footnotes
In this paper, without special illustrations, the maximality is always w.r.t. set inclusion.
In [28], attacks in |$S_{c}$| are called core attacks of |$S$|. And attacks in |$S_{a}$| are called appendant attacks.
References
A Proofs for lemmas in Section 3
Lemma 1 is obvious from the definition of greatest regular R-sets.
Suppose |$S\subseteq Ar$| is a set of arguments in an HO-AF |$(Ar,~ \mathcal{R})$|. |$\forall \alpha ,\beta \in R_{S}^{gr}$|, |$trg(\alpha )\neq \beta $|.
Assume |$trg(\alpha )=\beta $|. Since |$R_{S}^{gr}$| is an R-set of |$\beta $| w.r.t. |$S$|, there exists some attack |$\beta _{0}\in R_{S}^{gr}$|, such that |$\beta _{0}\rightarrow _{R} \alpha $|. Because |$R_{S}^{gr}$| is regular, |$trg(\beta _{0})\notin S$|. For |$src(\alpha )\in S$|, |$trg(\beta _{0})\neq src(\alpha )$|. Hence, |$trg(\beta _{0})=\alpha $|.
B Proofs for lemmas and theorems in Section 4
B.1 Proofs for lemmas in Subsection 4.1
In an HO-AF |$(Ar, \mathcal{R})$|, let |$S$| be an r-conflict-free set. For any |$(A,B)\in \mathcal{R}$| with |$A,B\in S$|, |$(A,B)\notin R_{S}^{gr}$|.
Assume |$(A,B)\in R_{S}^{gr}$|. Because of the r-conflict-freeness, there is some |$\alpha \in R_{S}^{gr}$| such that |$trg(\alpha )=(A,B)$|. It contradicts Lemma 2. Therefore, |$(A,B)\notin R_{S}^{gr}$|.
In an HO-AF |$(Ar,\mathcal{R})$|, suppose |$S\subseteq Ar$| and |$A\in Ar$|. If |$S$| r-defends |$A$|, then each regular R-set |$R_{S}$| w.r.t. |$S$| is also a regular R-set w.r.t. |$S_{1}=S\cup \{A\}$|.
Obviously, |$R_{S}$| is an R-set w.r.t. |$S_{1}$|.
Assume |$R_{S}$| is not regular w.r.t. |$S_{1}$|. Then, there is some attack |$\alpha \in R_{S}$| s.t. |$trg(\alpha )\in S_{1}$|. Because |$R_{S}$| is regular w.r.t. |$S$|, |$trg(\alpha )\notin S$|. Hence, |$trg(\alpha )=A$|.
Since |$A$| is r-defended by |$S$|, there is some |$\beta \in R_{S}^{gr}$| s.t. |$\beta \rightarrow _{R} \alpha $|. Because both |$\beta \in R_{S}^{gr}$| and |$\alpha \in R_{S}\subseteq R_{S}^{gr}$|, by Lemma 2, |$trg(\beta )\neq \alpha $|. Hence, |$trg(\beta )=src(\alpha )$|.
On the other hand, |$\beta \in R_{S}^{gr}$| implies |$src(\alpha )=trg(\beta )\notin S$|. But |$\alpha \in R_{S}$| implies |$src(\alpha )\in S$|. Contradiction.
Therefore, |$R_{S}$| is a regular R-set w.r.t. |$S_{1}$|.
In an HO-AF |$(Ar,\mathcal{R})$|, suppose |$S\subseteq Ar$| is an r-admissible set and |$A,A^{\prime}\in Ar$| are r-defended by |$S$|. Then,
|$S_{1}=S\cup \{A\}$| is r-admissible; and
|$A^{\prime}$| is r-defended by |$S_{1}$|.
1. From Lemma 3, |$S_{1}$| r-defends each argument in it. The left is to show its r-conflict-freeness. From the r-conflict-freeness of |$S$|, it is only necessary to consider two cases: |$(A,B)\in \mathcal{R}$| or |$(B,A)\in \mathcal{R}$|, |$\forall B\in S$|.
Case 1: |$(B,A)\in \mathcal{R}$|. For |$A$| is r-defended by |$S$|, there is some |$\alpha \in R_{S}^{gr}$| s.t. |$\alpha \rightarrow _{R} (B,A)$|. Because the regularity of |$R_{S}^{gr}$|, |$trg(\alpha )\neq B$|. Hence, |$trg(\alpha )=(B,A)$|.
Case 2: |$(A,B)\in \mathcal{R}$|. Since the r-admissibility of |$S$|, there is some |$\alpha \in R_{S}^{gr}$| s.t. |$\alpha \rightarrow _{R} (A,B)$|. If |$trg(\alpha )= A$|, by the first case, there is some |$\beta \in R_{S}^{gr}$| s.t. |$trg(\beta )=\alpha $|. It contradicts Lemma 2. Hence, |$trg(\alpha )=(A,B)$|.
Therefore, |$S_{1}$| is r-conflict-free. Hence, it is r-admissible.
2. It is directly obtained by Lemma 3.
Let |$S\subseteq Ar$| be a set of arguments in an HO-AF |$(Ar,\mathcal{R})$|. If |$S$| is an r-admissible set, then its greatest regular R-set |$R_{S}^{gr}$| is both sufficient and complete w.r.t. |$S$|.
Suppose |$S$| is an r-admissible set. Then, |$R_{S}^{gr}$| r-defends every argument in |$S$|. Hence, it is a sufficient R-set w.r.t. |$S$|.
Assume |$\alpha \in S^{+}\setminus R_{S}^{gr}$| is r-defended by |$R_{S}^{gr}$|. Let |$R_{S}=R_{S}^{gr}\cup \{\alpha \}$|. Then, |$R_{S}$| is also an R-set w.r.t |$S$| and |$R_{S}^{gr}\subsetneq R_{S}$|. Let us show |$R_{S}$| is regular w.r.t. |$S$|. It is only necessary to show |$trg(\alpha )\notin S$|.
Assume |$trg(\alpha )\in S$|. Because |$S$| is r-conflict-free, there is some |$\beta \in R_{S}^{gr}$| s.t. |$trg(\beta )=\alpha $|. Since |$\alpha $| is r-defended by |$S$|, there is some |$\alpha ^{\prime}\in R_{S}^{gr}$| s.t. |$\alpha ^{\prime}\rightarrow _{R}\beta $|. There are two cases:
Case 1: |$trg(\alpha ^{\prime})=\beta $|. Because both |$\alpha ^{\prime}$| and |$\beta $| are in |$R_{S}^{gr}$|, it contradicts Lemma 2.
Case 2: |$trg(\alpha ^{\prime})=src(\beta )$|. For |$src(\beta )\in S$|, it contradicts the regularity of |$R_{S}^{gr}$|.
Therefore, |$trg(\alpha )\notin S$|, and |$R_{S}^{gr}$| is complete w.r.t. |$S$|.
B.2 Proofs for theorems in Subsection 4.2
Theorem 1 is obvious from the Fundamental Lemma, and Corollary 1 is directly implied from Theorem 1.
The next relations are valid. But not vice versa.
(1) Every r-admissible set is r-conflict-free.
(2) Every r-complete set is r-admissible.
(3) Every r-para-preferred set is r-complete.
(4) Every r-preferred set is r-para-preferred.
(5) Every r-stable set is r-para-preferred.
(6) The r-grounded set is a minimal r-complete set.
(1), (2) and (3) are obvious from definitions of the semantics. We next prove (4), (5) and (6).
(4) Suppose |$S\subseteq Ar$| is an r-preferred set.
Assume |$S$| is not r-complete, for example, it r-defends an argument |$A\in Ar\setminus S$|. From the Fundamental Lemma, |$S^{\prime}=S\cup \{A\}$| is also r-admissible. It contradicts the maximality of |$S$|. Hence, |$S$| is r-complete.
If there is some other r-complete |$S^{\prime}$| s.t. |$R_{S}^{gr}\subsetneq R_{S^{\prime}}^{gr}$|, then each element r-defended by |$S$| is r-defended by |$S^{\prime}$|. Particularly, every element in |$S$| is r-defended by |$S^{\prime}$|. Because |$S^{\prime}$| is r-complete, we have |$S\subseteq S^{\prime}$|. For |$R_{S}^{gr}\neq R_{S^{\prime}}^{gr}$|, we have |$S\neq S^{\prime}$|. Hence, |$S\subsetneq S^{\prime}$|. It contradicts the fact that |$S$| is r-preferred. Therefore, |$R_{S}^{gr}$| is maximal.
As a result, |$S$| is an r-complete set where |$R_{S}^{gr}$| is maximal, i.e., |$S$| is r-para-preferred.
(5) Suppose |$S\subseteq Ar$| is an r-stable set.
First, let us show |$S$| is r-admissible, i.e., |$S$| r-defends each argument |$A$| in it. Assume |$\beta \in A^{-}$|. If |$src(\beta )\in S$|, then from the r-conflict-freeness of |$S$|, there is an attack |$\alpha \in R_{S}^{gr}$| s.t. |$trg(\alpha )=\beta $|. If |$src(\beta )\in Ar\setminus S$|, then from the r-stability of |$S$|, there is an attack |$\alpha \in R_{S}^{gr}$| s.t. |$trg(\alpha )=src(\beta )$|. Hence, in both case, |$A$| is r-defended by |$S$|, i.e., |$S$| is r-admissible.
Second, let us show |$S$| is r-complete. Assume |$S$| is not r-complete. Then, |$S$| r-defends some argument |$B\in Ar\setminus S$|. For the r-stability of |$S$|, there is some |$A\in S$| s.t. |$(A,B)\in R_{S}^{gr}$|. On the other hand, because |$S$| r-defends |$B$|, there is an attack |$\alpha \in R_{S}^{gr}$| s.t. |$\alpha \rightarrow _{R} (A,B)$|. From the regularity of |$R_{S}^{gr}$|, |$trg(\alpha )\neq A\in S$|. From Lemma 2, |$trg(\alpha )\neq (A,B)$|. Contradiction. Therefore, |$S$| is r-complete.
Finally, let us show the maximality of |$R_{S}^{gr}$|. If not, there exists some r-complete set |$S^{\prime}\subseteq Ar$| s.t. |$R_{S}^{gr}\subsetneq R_{S^{\prime}}^{gr}$|. Consider |$\alpha \in R_{S^{\prime}}^{gr}\setminus R_{S}^{gr}$|. If |$src(\alpha )\notin S$|, then from the r-stability of |$S$|, there is some |$\beta \in R_{S}^{gr}\subsetneq R_{S^{\prime}}^{gr}$| s.t. |$trg(\beta )=src(\alpha )\in S^{\prime}$|. It contradicts the regularity of |$R_{S^{\prime}}^{gr}$|. Hence, |$src(\alpha )\in S$|. It follows that |$\forall \alpha \in R_{S^{\prime}}^{gr}$|, |$src(\alpha )\in S$|. As a result, |$R_{S^{\prime}}^{gr}$| is also a regular R-set w.r.t. |$S$|. From the definition of |$R_{S}^{gr}$|, we have |$R_{S^{\prime}}^{gr}\subseteq R_{S}^{gr}$|. Contradiction.
Therefore, |$S$| is r-para-preferred.
(6) From Lemma 4, |$Gr=\cup _{n=0}^\infty F^{n}_{r}(\emptyset )$| is r-admissible. Because |$F_{r}(\cup _{n=0}^\infty F^{n}_{r}(\emptyset ))=\cup _{n=1}^\infty F^{n}_{r}(\emptyset )\subseteq \cup _{n=0}^\infty F^{n}_{r}(\emptyset )=Gr$|, |$Gr$| is r-complete.
Assume |$G_{r}$| is not minimal. Then there is some r-complete set |$S\subsetneq G_{r}$|.
Since |$\forall n\in \mathbb{N}$|, |$F^{n}(\emptyset )$| is r-admissible and |$F(F^{n}(\emptyset ))=F^{n+1}(\emptyset )$|, we have |$F^{n}(\emptyset )\subseteq F^{n+1}(\emptyset )$|. Because |$S\subsetneq G_{r}$|, there exists |$m\in \mathbb{N}$| such that |$S\subseteq F^{m}(\emptyset )$|.
On the other hand, |$S$| obviously r-defends every element in |$F^{1}(\emptyset )$|. Then there exists some |$k\in \mathbb{N}$| such that |$S_{k}=F^{k}(\emptyset )\subseteq S$| but |$S_{k+1}=F^{k+1}\nsubseteq S$|.
If |$R_{S_{k}}^{gr}\subseteq R_{S}^{gr}$|, then every element in |$S_{k+1}$| is r-defended by |$S$|. Contradiction. Hence, there is some |$\alpha \in R_{S_{k}}^{gr}\setminus R_{S}^{gr}$|.
From the definition of greatest R-sets, there is some |$\beta _{1}\in R_{S}^{gr}$| such that |$\beta _{1}\rightarrow _{R} \alpha $|. From |$S_{k}\subseteq S$| and the regularity of |$R_{S}^{gr}$|, |$trg(\beta _{1})=\alpha $|. Similarly, there is some |$\alpha _{1}\in R_{S_{k}}^{gr}$| such that |$trg(\alpha _{1})=\beta _{1}$|. This process continues endless. It contradicts the definition of level |$(0,n)$| HO-AF.
Therefore, |$G_{r}$| is minimal among all r-complete sets.
C Proofs for lemmas and theorems in Section 5
C.1 Proofs for lemmas and theorems in Subsection 5.1
In an M-EAF |$(Ar,\mathcal{R})$|, suppose |$S\subseteq Ar$| is a set of arguments and |$A,B$| are two arguments. |$(A,B)\notin Defeat^{S}$|, iff either |$(A,B)\notin \mathcal{R}$| or |$R_{S}^{gr}\cap (A,B)^{-}\neq \emptyset $|.
Equivalently, |$(A,B)\in Defeat^{S}$|, iff |$(A,B)\in \mathcal{R}$| and |$R_{S}^{gr}\cap (A,B)^{-}\neq \emptyset $|.
(Necessity) Suppose |$(A,B)\notin Defeat^{S}$|. If |$(A,B)\notin \mathcal{R}$|, then |$(A,B)\notin Defeat^{S}$|. Otherwise, there is |$C\in S$| s.t. |$(C,(A,B))\in \mathcal{R}$|. Let |$\alpha =(C,(A,B))$|. Obviously, |$\alpha \in \mathcal{R}_{1}$| and |$\{\alpha \}$| is not directly attacked by any argument. Hence, it is r-defended by every argument set.
(Sufficiency) If |$(A,B)\notin \mathcal{R}$|, then it is trivial that |$(A,B)\notin Defeat^{S}$|. Otherwise, let |$C=src(\alpha )\in S$|. Then, |$\alpha = (C,(A,B))$| kicks |$(A,B)$| out of |$Defeat^{S}$|.
In an M-EAF |$(Ar,\mathcal{R})$|, an argument set |$S\subseteq Ar$| is m-conflict-free, iff it is r-conflict-free and the condition (M) holds.
Suppose |$S$| is an m-conflict-free set. Then condition (M) is obvious.
For any arguments |$A,B\in S$|, if |$(A,B)\in \mathcal{R}$|, then there is some |$\alpha \in \mathcal{R}_{1}\cap S^{+}$| such that |$trg(\alpha )=(A,B)$|. From Lemma 6, |$\alpha \in R_{S}^{gr}$|. Hence, |$S$| is r-conflict-free.
The inverse direction is similar.
In an M-EAF |$(Ar,\mathcal{R})$|, suppose |$S\subseteq Ar$| is r-conflict-free and |$R_{S}\subseteq S^{+}$|. |$R_{S}$| is a regular R-set of |$\alpha _{0}\in \mathcal{R}_{0}$| w.r.t. |$S$|, iff |$R_{S}\cap \mathcal{R}_{0}$| is a reinstatement set for |$\alpha _{0}$| w.r.t. |$S$|.
Equivalently, for any |$\alpha _{0}\in \mathcal{R}_{0}$|, |$\alpha _{0}\in R_{S}^{gr}$|, iff there is a reinstatement for |$\alpha _{0}$| w.r.t. |$S$|.
(Sufficiency) Suppose |$R_{S}\cap \mathcal{R}_{0}$| is a reinstatement set for |$\alpha _{0}$| w.r.t. |$S$|. Obviously, |$R_{S}\cap \mathcal{R}_{0}\subseteq Defeat^{S}$|.
For |$\alpha \in R_{S}\cap \mathcal{R}_{1}$|, it is not attacked. Hence, |$R_{S}$| is an R-set of it. For |$\alpha \in R_{S}\cap \mathcal{R}_{0}$|, |$R_{S}\cap \mathcal{R}_{0}$| (hence, |$R_{S}$|) is obvious an R-set of |$\alpha $| w.r.t. |$S$|. In a word, |$R_{S}$| is an R-set w.r.t. |$S$|. For |$\alpha _{0}\in R_{S}$|, |$R_{S}$| is an R-set of |$\alpha _{0}$| w.r.t. |$S$|.
Assume |$R_{S}$| is not regular, i.e., |$\exists \alpha \in R_{S}$| s.t. |$trg(\alpha )\in S$|. Because |$S$| is r-conflict-free, there is an attack |$\beta \in R_{S}^{gr}$| s.t. |$trg(\beta )=\alpha $|, i.e., |$\exists \beta \in R_{S}^{gr}\cap \alpha ^{-}$|. By Lemma 6, |$\alpha \notin Defeat^{S}$|. It contradicts |$R_{S}\cap \mathcal{R}_{0}\subseteq Defeat^{S}$|. Hence, |$trg(\alpha )\notin S$| and |$R_{S}$| is regular.
(Necessity) Suppose |$R_{S}$| is a regular R-set of |$\alpha _{0}\in \mathcal{R}_{0}$| w.r.t. |$S$| and |$\alpha $| is an attack in |$R_{S}\cap \mathcal{R}_{0}$|. Obviously, |$\alpha _{0}\in R_{S}\cap \mathcal{R}_{0}$| and |$src(\alpha )\in S$|.
Assume |$\alpha \notin Defeat^{S}$|, i.e., there is some |$C\in S$| s.t. |$(C,\alpha )\in \mathcal{R}_{1}$|. Then, |$\{(C, \alpha )\}$| is a regular R-set of |$(C,\alpha )$|. Together with the fact that |$R_{S}$| is a regular R-set of |$\alpha $|, it contradicts Lemma 2. Hence, |$\alpha \in Defeat^{S}$| and |$R_{S}\cap \mathcal{R}_{0}\subseteq Defeat^{S}$|.
Suppose |$Y$| is an argument satisfying that |$(Y,\alpha )\in \mathcal{R}_{1}$|. Because |$R_{S}$| is an R-set, there is some |$\beta \in R_{S}$| s.t. |$\beta \rightarrow _{R} (Y,\alpha )$|. If |$trg(\beta )=(Y,\alpha )$|, then |$level(\beta )\geq 2$|, and |$\beta $| is out of the M-EAF. Hence, |$trg(\beta )=Y$| and |$\beta \in R_{S}\cap \mathcal{R}_{0}\subseteq Defeat^{S}$|.
In a summary, |$R_{S}\cap \mathcal{R}_{0}$| satisfies all the three conditions in the definition of reinstatement sets. Hence, it is a reinstatement set for |$\alpha _{0}$| w.r.t. |$S$|.
Suppose |$S$| is an r-conflict-free set in an M-EAF |$(Ar,\mathcal{R})$|. |$S$| m-defends an argument |$A$|, iff |$S$| r-defends |$A$|.
(Necessity) Suppose |$S$| m-defends |$A$| and |$(B,A)\in \mathcal{R}$|.
If |$(B,A)\notin Defeat^{S}$|, by Lemma 6, there is some |$\alpha \in R_{S}^{gr}$| s.t. |$trg(\alpha )=(B,A)$|.
If |$(B,A)\in Defeat^{S}$|, because |$S$| m-defends |$A$|, there is some |$\alpha \in Defeat^{S}$| s.t. |$trg(\alpha )=A$| and there is a reinstatement set of |$\alpha $|. By Lemma 7, |$\alpha \in R_{S}^{gr}$| and |$trg(\alpha )=A$|.
(Sufficiency) Suppose |$S$| r-defends |$A$| and |$(B,A)\in Defeat^{S}$|. It is also directly obtained that |$S$| m-defends |$A$| by Lemma 7.
In an M-EAF |$(Ar,\mathcal{R})$|, suppose that |$S\subseteq Ar$| satisfies the condition (M). Then, |$S$| is
m-admissible iff it is r-admissible;
m-complete iff it is r-complete;
m-grounded iff it is r-grounded;
m-stable iff it is r-stable;
m-preferred if it is r-preferred.
All the items are directly obtained from Theorems 3 and 4. Here, we give a proof for the first one—the admissibility.
Suppose |$S$| is an r-admissible set that satisfies condition (M). From Theorem 3, |$S$| is m-conflict-free. From Theorem 4, |$S$| m-defends each element in it. Hence, |$S$| is m-admissible.
The inverse is similar.
C.2 Proofs for lemmas and theorems in Subsection 5.2
Lemma 8 is obvious.
Suppose |$S\subseteq Ar\cup \mathcal{R}$| is bcgg-admissible in an HO-AF |$(Ar, \mathcal{R})$|.
(1) If an attack |$\alpha $| is bcgg-defended by |$S$|, then |$src(\alpha )$| is bcgg-defended by |$S$|.
(2) |$S_{R}$| is a sufficient regular R-set w.r.t. |$S_{A}\cup src(S_{R})$|.
(3) If |$\chi \in Ar\cup \mathcal{R}$| is bcgg-defended by |$S_{R}$|, then |$\chi $| is r-defended by |$S_{R}$|.
(4) |$S_{A}\cup src(S_{R})$| is r-conflict-free.
(5) If |$\chi \in Ar\cup S_{A}^{+}$| is r-defended by |$S_{R}$|, then |$\chi $| is bcgg-defended by |$S_{R}$|.
(1) Suppose |$\alpha $| is bcgg-defended by |$S$|. Then, |$\forall \beta $| with |$\beta \rightarrow _{R} \alpha $|, there exists some |$\gamma \in S$| s.t. |$\gamma \rightarrow _{R} \beta $|. Particularly, if |$trg(\beta )=src(\alpha )$|, then |$\gamma \rightarrow _{R} \beta $|. It means |$src(\alpha )$| is bcgg-defended by |$S$|.
(2) From the bcgg-admissibility of |$S$|, |$S_{R}$| is an R-set w.r.t. |$S_{A}\cup src(S_{R})$|. From (1) and the bcgg-admissibility of |$S$|, |$S_{R}$| is sufficient w.r.t. |$S_{A}\cup src(S_{R})$|. Next, we show the regularity of |$S_{R}$| w.r.t. |$S_{A}\cup src(S_{R})$|.
For any attack |$\alpha \in S$|, from the bcgg-conflict-freeness of |$S$|, |$trg(\alpha )\notin S_{A}$|. Assume |$trg(\alpha )\in src(S_{R})$|. Then, |$\exists \beta \in S$| s.t. |$src(\beta )=trg(\alpha )$|. Hence, |$\alpha \rightarrow _{R}\beta $|. contradicts the bcgg-conflict-freeness of |$S$|. Hence, |$trg(\alpha )\notin S_{A}\cup src(S_{R})$|, i.e., |$S_{R}$| is regular w.r.t. |$S_{A}\cup src(S_{R})$|.
(3) It is obvious from (2) and the bcgg-admissibility of |$S$|.
(4) It is obvious from (3) and the second paragraph in the proof of (2). Obvious from (3), |$S_{A}$| r-defends every element in it. Suppose |$(A,B)\in \mathcal{R}$| for |$A,B\in S_{A}\cup src(S_{R})$|.
If |$B\in S_{A}$|, then from the bcgg-admissibility of |$S$|, there is an attack |$\alpha \in S_{R}$| such that |$\alpha \rightarrow _{R} (A,B)$|. From the m-conflict-freeness of |$S$|, |$trg(\alpha )\neq A$|. Hence, |$trg(\alpha )=(A,B)$|. Because |$\alpha $| is bcgg-defended by |$S_{R}$|, from (3) |$\alpha $| is r-defended by |$S_{A}$|. Hence, |$S_{A}$| is r-conflict-free.
If |$B\in src(S_{R})$|, then from the bcgg-admissibility of |$S$|, there is an attack |$\alpha \in S_{R}$| such that |$\alpha \rightarrow _{R} (A,B)$|. If |$trg(\alpha )=A$|, it contradicts the bcgg-conflict-freeness of |$S$|. Hence, |$trg(\alpha )=(A,B)$|. From (3), |$S_{A}$| is r-conflict-free.
(5) Suppose |$\chi \in Ar\cup S_{A}^{+}$| is r-defended by |$S_{R}$|. For any |$\beta \rightarrow _{R} \chi $|, there are two cases. If |$trg(\beta )=\chi $|, because |$\chi $| is r-defended by |$S_{R}$|, there exists |$\alpha \in S_{R}$| s.t. |$\alpha \rightarrow _{R} \beta $|. If |$trg(\beta )=src(\chi )\in S_{A}$|, because the bcgg-admissibility of |$S$|, there is some |$\alpha \in S_{R}$| s.t. |$\alpha \rightarrow _{R}\beta $|. Therefore, |$\chi $| is bcgg-defended by |$S$|.
Suppose |$S\subseteq Ar\cup \mathcal{R}$| is a set of arguments and attacks in an HO-AF |$(Ar, \mathcal{R})$|. |$S$| is bcgg-admissible, iff |$S^{\prime}=S_{A}\cup src(S_{R})$| is r-admissible and |$S_{R}$| is a sufficient regular R-set w.r.t. |$S^{\prime}$|.
(Necessity) Suppose |$S\subseteq Ar\cup \mathcal{R}$| is bcgg-admissible. From Lemma 9 (2), |$S_{R}$| is a sufficient regular R-set w.r.t. |$S^{\prime}=S_{A}\cup src(S_{R})$|.
From Lemma 9 (4), |$S^{\prime}$| is r-conflict-free. From Lemma 9 (3), the bcgg-admissibility of |$S$| implies that |$S^{\prime}$| r-defends each element in |$S^{\prime}$|. Therefore, |$S^{\prime}$| is r-admissible.
(Sufficiency) Suppose |$S^{\prime}$| is r-admissible and |$S_{R}$| is a sufficient regular R-set w.r.t. |$S^{\prime}$|. Obviously, |$src(S_{R})\subseteq S^{\prime}$|. For any |$S_{A}\subseteq S^{\prime}$|, let us show |$S=S_{A}\cup S_{R}$| is bcgg-admissible.
Obviously, |$S^{\prime}$| is r-conflict-free. From Lemma 8, |$S^{\prime}\cup S_{R}$| is bcgg-conflict-free. Hence, |$S\subseteq S^{\prime}\cup S_{R}$| is bcgg-conflict-free.
Next, let us show |$S_{R}$| bcgg-defends every element |$\chi \in S$|. Assume |$\alpha \rightarrow _{R}\chi $|.
If |$\chi \in S_{A}\subseteq S^{\prime}$|, then |$trg(\alpha )=\chi $|. Because |$S_{R}$| is a sufficient R-set w.r.t. |$S^{\prime}$|, there is some |$\beta \in S_{R}$| s.t. |$\beta \rightarrow _{R} \alpha $|.
If |$\chi \in S_{R}$|, then |$trg(\alpha )=\chi $| or |$trg(\alpha )=src(\chi )\in S^{\prime}$|. For |$trg(\alpha )=\chi $|, because |$S_{R}$| is an R-set, there is some |$\beta \in S_{R}$| s.t. |$\beta \rightarrow _{R} \alpha $|. For |$trg(\alpha )=src(\chi )\in S^{\prime}$|, because |$S_{R}$| is sufficient w.r.t. |$S^{\prime}$|, there is some |$\beta \in S_{R}$| s.t. |$\beta \rightarrow _{R} \alpha $|.
Therefore, |$S$| is bcgg-defended by |$S_{R}$|. Hence, |$S$| is bcgg-admissible.
In an HO-AF |$(Ar, \mathcal{R})$|, if |$S_{A}\subseteq Ar$| is an r-complete set, then |$S=S_{A}\cup R_{S_{A}}^{gr}$| is a bcgg-complete set. But not vice versa.
Suppose |$S_{A}\subseteq Ar$| is r-complete and |$R_{S_{A}}^{gr}$| is the greatest regular R-set w.r.t. |$S_{A}$|. Let us show |$S=S_{A}\cup R_{S_{A}}^{gr}$| is bcgg-complete.
From Lemma 5, |$R_{S_{A}}^{gr}$| is complete, sufficient and regular w.r.t. |$S_{A}$|.
Obviously, |$src(R_{S_{A}}^{gr})\subseteq S_{A}$|, i.e., |$S_{A}=S_{A}\cup src(R_{S_{A}}^{gr})$|. By Theorem 6, |$S$| is bcgg-admissible.
Suppose |$A$| is an argument bcgg-defended by |$S$|, i.e., for any |$\beta \in A^{-}$|, there is some |$\alpha \in R_{S_{A}}^{gr}$| s.t. |$\alpha \rightarrow _{R}\beta $|. Since |$S_{A}$| is r-complete, |$A$| is in |$S_{A}$|.
Suppose |$\alpha $| is an attack bcgg-defended by |$S$|, i.e., for any |$\beta \in \alpha ^{-}$|, there is some |$\alpha \in R_{S_{A}}^{gr}$| s.t. |$\alpha \rightarrow _{R}\beta $|. From Lemma 9 (1), |$src(\alpha )\in S_{A}$|. Because |$R_{S_{A}}^{gr}$| is complete, |$\alpha \in R_{S_{A}}^{gr}$|. Hence, |$\alpha \in S$|.
In a summary, |$S$| is a bcgg-admissible set, which includes every argument and every attack it bcgg-defends. Therefore, it is bcgg-complete.
In an HO-AF |$(Ar, \mathcal{R})$|, |$S\subseteq Ar\cup \mathcal{R}$| is a bcgg-preferred set, iff |$S_{A}$| is an r-para-preferred set and |$S_{R}=R_{S_{A}}^{gr}$|.
(Sufficiency) Suppose |$S_{A}$| is an r-para-preferred set and |$R_{S_{A}}^{gr}$| is the greatest regular R-set w.r.t. |$S_{A}$|. Let us show |$S=S_{A}\cup R_{S_{A}}^{gr}$| is bcgg-preferred.
Because |$S_{A}$| is r-para-preferred, |$S_{A}$| is r-complete. By Theorem 7, |$S$| is bcgg-complete, hence, bcgg-admissible.
Assume |$S^{\prime}\subseteq Ar\cup \mathcal{R}$| is a bcgg-admissible set satisfying |$S\subseteq S^{\prime}$|. Then, |$S_{A}\subseteq S^{\prime}_{A}$| and |$R_{S_{A}}^{gr}= S_{R}\subseteq S^{\prime}_{R}\subseteq R_{S^{\prime}_{A}}^{gr}$|.
Because |$S_{A}$| is r-para-preferred, |$R_{S_{A}}^{gr}$| is maximal. Hence, |$R_{S_{A}}^{gr}$| is not a proper subset of |$R_{S^{\prime}_{A}}^{gr}$|. Therefore, |$R_{S^{\prime}_{A}}^{gr}= R_{S_{A}}^{gr}$|.
From the bcgg-admissibility of |$S^{\prime}$| and the r-completeness of |$S_{A}$|, we have |$S^{\prime}_{A}= S_{A}$|.
As a result, |$S=S^{\prime}$|, i.e., |$S$| is a maximal bcgg-admissible set. Hence, |$S$| is bcgg-preferred.
(Necessity) Suppose |$S\subseteq Ar\cup \mathcal{R}$| is a bcgg-preferred set. Then, |$S$| is bcgg-complete and it is maximal among all bcgg-admissible sets.
From Lemma 9 (1), for any |$\alpha \in S_{R}$|, |$src(\alpha )$| is bcgg-defended by |$S_{R}$|. Because |$S$| is bcgg-complete, |$src(\alpha )\in S$|. Hence, |$S_{A}=S_{A}\cup S_{R}$|.
From Theorem 6, |$S_{A}$| is r-admissible, and |$S_{R}$| is a sufficient regular R-set w.r.t. |$S_{A}$|. Because |$S$| is maximal, |$S_{R}$| is maximal. Hence, it is the greatest regular R-set w.r.t. |$S_{A}$|, i.e., |$S_{R}=R_{S_{A}}^{gr}$|. Also from the maximality of |$S$|, |$S_{A}$| contains all the elements that are bcgg-defended by |$S_{R}$|. From Lemma 9 (3), |$S_{A}$| contains all the arguments that are r-defended by |$S_{R}$|. Therefore, |$S_{A}$| is r-complete.
Assume there is an r-complete set |$S^{\prime}_{A}\subseteq Ar$| s.t. |$S_{R}=R_{S_{A}}^{gr}\subseteq R_{S^{\prime}_{A}}^{gr}$|. From the r-completeness of |$S^{\prime}_{A}$|, we have |$S_{A}\subseteq S^{\prime}_{A}$|. Therefore, |$S=S_{A}\cup S_{R} \subseteq S^{\prime}_{A}\cup R_{S^{\prime}_{A}}^{gr}$|.
On the other hand, because |$R_{S^{\prime}_{A}}^{gr}$| is a sufficient regular R-set w.r.t. |$S^{\prime}_{A}$|, from Theorem 6, |$S^{\prime}_{A}\cup R_{S^{\prime}_{A}}^{gr}$| is a bcgg-admissible set, which includes |$S$|. From the maximality of |$S$|, we have |$S^{\prime}_{A}\cup R_{S^{\prime}_{A}}^{gr}\subseteq S$|. Therefore, |$S^{\prime}_{A}\cup R_{S^{\prime}_{A}}^{gr} = S$|. Hence, |$R_{S^{\prime}_{A}}^{gr} = S_{R}=R_{S_{A}}^{gr}$|.
Together with its r-completeness, |$S$| is r-para-preferred.
In an HO-AF |$(Ar, \mathcal{R})$|, |$S\subseteq Ar\cup \mathcal{R}$| is a bcgg-arg-preferred set, iff |$S_{A}$| is an r-preferred set and |$S_{R}=R_{S_{A}}^{gr}$|.
(Sufficiency) Suppose |$S$| is a bcgg-arg-preferred set. It is bcgg-preferred. From Theorem 8, |$S_{R}=R_{S_{A}}^{gr}$| and |$S_{A}$| is r-para-preferred, hence, r-admissible.
From Theorem 2 (4), it just needs to show |$S_{A}$| is a maximal r-para-preferred set.
Because |$S$| is arg-maximal, |$S$| is arg-maximal among all bcgg-preferred sets. Hence, |$S_{A}$| is maximal among all r-para-preferred sets. As a result, |$S_{A}$| is r-preferred.
(Necessity) The inverse is similar.
In an HO-AF |$(Ar, \mathcal{R})$|, |$S\subseteq Ar\cup \mathcal{R}$| is a bcgg-stable set, iff |$S_{A}$| is r-stable and |$S_{R}=R_{S_{A}}^{gr}$|.
Because every bcgg-stable set is bcgg-preferred, by Theorem 8, |$S_{A}$| is r-para-preferred and |$S_{R}= R_{S_{A}}^{gr}$|.
The remaining is obvious from Lemma 9 (3) and (5).
