Sub-Frameworks and Local Semantics
Abstract
In many situations, evaluating the status of arguments globally is inefficient. In this chapter, we introduce a basic theory for evaluating the status of arguments locally: given a subset of arguments, their status is computed in a sub-framework which may (or may not) be conditioned by other sub-frameworks. For an unconditioned sub-framework, the definition of its semantics is the same as the one for Dung’s argumentation framework. On the contrary, for a conditioned sub-framework in which the status of some arguments may be affected by that of some external arguments, the definition of its semantics is different.
Keywords
conditioned sub-frameworks; induced sub-graphs; local semantics; partially assigned sub-frameworks; partially labelled sub-frameworks; unconditioned sub-frameworks
4.1 Introduction
In the previous two chapters, we only dealt with the semantics of a whole argumentation framework. In this book, we call it the global semantics of an argumentation framework. However, in many situations, it is better to focus on the semantics of a part of an argumentation framework, called the local semantics of the argumentation framework. For instance, when an argumentation framework changes by the addition (or the removal) of a set of arguments and/or a set of attacks, only the status of affected arguments is necessary to be determined [1]; when querying the status of some specific arguments, we may only pay attention to the set of relevant arguments [2]; and, for some argumentation frameworks, computing the status of arguments locally might dramatically reduce the computational complexity [3].
Given an argumentation framework and a subset of arguments within it, in order to define the local semantics of the argumentation framework with respect to this subset, we introduce a notion of sub-frameworks. Since the statuses of different arguments in an argumentation framework affect each other with respect to attack relation, a sub-framework might depend on (be conditioned by) some other sub-frameworks, which might in turn depend on some other sub-frameworks, and so on.
For a sub-framework which is conditioned by some other sub-frameworks, the definition of its semantics is not similar to the one for a Dung’s argumentation framework (as presented in Section 2.3). Furthermore, from the perspective of computation, the approaches and algorithms for a Dung’s argumentation framework should be modified to adapt to the characteristics of the sub-frameworks.
According to the above considerations, in this chapter, we focus on the following four basic issues:
• Dependence relation between deferent sub-frameworks;
• Semantics of sub-frameworks, which is regarded as the local semantics of a corresponding argumentation framework;
Related contents of this chapter and the subsequent chapters are originally presented in [1–3].
4.2 Notion of Sub-Frameworks
4.2.1 Informal Idea
Since an argumentation framework can be regarded as a directed graph, the notion of a sub-framework is similar to that of an induced subgraph of a directed graph. According to graph theory, given a graph 
, a subgraph of 
is a graph whose vertex set is a subset of that of 
, and whose adjacency relation is a subset of that of 
related to this subset. Furthermore, a subgraph 
of a graph 
is said to be induced if for any pair of vertices 
and 
of 
is an edge of 
if and only if 
is an edge of 
.
Example 4.1
Let 
be an argumentation framework. The corresponding defeat graph is shown in Figure 4.1. Let us consider the following subgraphs.
is 
.
is 
.
is 
.
.Now, an important problem arises: Can every subgraph in Example 4.1 be regarded as a sub-framework in which the status of arguments can be evaluated locally? First, the arguments in 
or 
are not attacked by any arguments outside the subgraph. It is intuitively feasible to evaluate the status of arguments locally. In other words, the status of arguments within the subgraph is not affected by the arguments outside the sub-framework, and therefore could be evaluated independently. Second, in 
, the argument 
is attacked by the argument 
, which is outside the subgraph. It is obvious that the status of the arguments 
and 
could not be evaluated locally in 
. In other words, when the arguments in an induced subgraph are attacked by some external arguments, we should take these external arguments into consideration. So, in this book, we will consider the following two classes of sub-frameworks.
If the arguments in a sub-framework are not attacked by any external arguments, then the sub-framework is called an unconditioned sub-framework. Otherwise, it is called a conditioned sub-framework. Hence, an unconditioned sub-framework is simply an induced subgraph of the corresponding defeat graph, while a conditioned sub-framework is composed of an induced subgraph and a conditioning subgraph. Here, the conditioning subgraph includes a set of nodes, each of which has at least a direct edge to a node of the induced subgraph. In Example 4.1, the conditioning sub-graph related to 
is 
.
4.2.2 Formal Definition
Let 
be an argumentation framework and 
be a subset. According to Formula 2.1 in Definition 2.1, the set of outside parents of the arguments in 
is 
. In this book, we call 
the set of conditioning arguments of 
.
First, when 
, the sub-framework induced by 
is unconditioned. In this case, the sub-framework is represented as 
, in which 
.
Second, when 
, the sub-framework induced by 
is conditioned by the arguments in 
. In this case, in terms of [1], the sub-framework induced by 
is represented as 
, where 
is a conditioning subgraph. Here, 
is the set of interactions from the arguments in 
to the arguments in 
.
In this book, for simplicity, we regard 
as a special case of 
(when 
and 
). So, all sub-frameworks are uniformly called sub-frameworks, and represented as 
, in which 
and 
could be empty. Formally, we have the following definition.
Definition 4.1
Sub-framework
Let 
be an argumentation framework, and 
be a set of arguments. Let 
and 
. A sub-framework of 
induced by 
is a tuple:
(4.1)
For simplicity, when 
and 
is also denoted as 
.
In addition, according to Definition 4.1, it is not required that the interactions from the arguments in 
to the arguments in 
should be empty. However, when they are not empty, although 
is still viewed as a sub-framework, there exists another sub-framework which is in turn conditioned by the arguments in 
. As a result, the two sub-frameworks are dependent on each other. The notion of dependence relation between different sub-frameworks will be formulated in Definition 4.2.
Example 4.2
Let 
be an argumentation framework (Figure 4.2(1)). Let 
and 
. It follows that 
and 
. The sub-frameworks induced by 
and 
respectively are illustrated in Figures 4.2(2) and (3).
and its sub-frameworks. Argument 
with a circle indicates that its status should be evaluated in the external sub-framework 
.4.2.3 Dependence Relation Between Different Sub-Frameworks
Now, let us discuss the relations between different sub-frameworks. Given a sub-framework 
, when 
, it is restricted by some other sub-framework(s), which may be in turn restricted by some other sub-framework(s), and so on. Consider the following example:
Example 4.3
The argumentation framework in Figure 4.3(1) could be decomposed into three sub-frameworks, illustrated in Figures 4.3(2), (3) and (4), indicated by 
and 
respectively. We may observe that 
is directly restricted by 
, and indirectly restricted by 
and 
itself.1
and its sub-frameworks.In this book, if a sub-framework 
is directly or indirectly restricted by another sub-framework 
, then we say that 
is dependent on 
. Formally, we have the following definition.
Definition 4.2
Dependence relation between sub-frameworks
Let 
be an argumentation framework, and 
be subsets of 
. 
is dependent on 
, if and only if 
and 
such that there is a path from 
to 
with respect to 
. For convenience, 
is called a conditioning sub-framework of 
.
Since a conditioned sub-framework 
may depend on some other sub-frameworks, before the status of arguments in 
is evaluated, we hope that the status of arguments in 
can be determined in advance. In this book, we only deal with a set of sub-frameworks over which there is a partial order.
4.3 Semantics of Sub-Frameworks
Given a sub-framework 
of an argumentation framework 
, if 
, then 
is an unconditioned sub-framework. In this case, 
. In this book, the definitions of the semantics of 
are the same as the ones presented in Section 2.3
On the other hand, when 
is a conditioned sub-framework. In this case, before the status of arguments in 
is evaluated, the status of arguments in 
should be determined in advance. Since 
, there exists 
, such that 
and 
. Hence, it is possible that the status of arguments in 
could be evaluated independently in an unconditioned sub-framework 
. Given a labelling or an extension of 
, the status of each argument in 
can be uniquely identified. According to the status of the arguments in 
, the status of arguments in 
is then evaluated.
Based on the above ideas, we introduce as follows the semantics of a conditioned sub-framework from the perspective of a labelling-based approach and of an extension-based approach, respectively.
4.3.1 Labellings of a Conditioned Sub-Framework
Let 
and 
be sub-frameworks of 
, and 
. According to each labelling of 
, each argument in 
has a certain status (IN, OUT or UNDEC). After the status of arguments in 
is labelled, the sub-framework 
is called a partially labelled sub-framework (PLSF, for short). Formally, we have the following definition.
Definition 4.3
Partially labelled sub-framework
Let 
and 
be sub-frameworks of 
, such that 
. Let 
be a labelling of 
. We call 
a partially labelled sub-framework, denoting that the labels of arguments in 
conform to 
.
Given a partially labelled sub-framework 
, since the labels of the arguments in 
conform to 
, we only need to assign new labels to the arguments in 
. Formally, a labelling of a partially labelled sub-framework is defined as follows.
Definition 4.4
Labelling of a partially labelled sub-framework
Based on Definition 4.3, a labelling of 
is defined as a total function
such that for all 
.
According to Definition 4.4, since the labels of arguments in 
conform to 
, whether a label assigned to an argument in 
is legal depends partially on 
.
Definition 4.5
Legal/illegal labelling of a PLSF
Based on Definition 4.3, let 
be a labelling of 
. For all 
,
• 
is legally IN in 
with respect to 
if and only if 
is labelled IN in 
and for all 
, if 
then 
is labelled OUT in 
; and for all 
, if 
then 
is labelled OUT in 
(and so in 
);
• 
is legally OUT in 
with respect to 
if and only if 
is labelled OUT in 
and there exists 
, such that 
and 
is labelled IN in 
; or there exists 
, such that 
and 
is labelled IN in 
(and so in 
);
• 
is legally UNDEC in 
with respect to 
if and only if 
is labelled UNDEC in 
and there exists no 
, such that 
and 
is labelled IN in 
or 
, and it is not the case that: for all 
, if 
then 
is labelled OUT in 
or 
;
• For 
IN, OUT, UNDEC
is illegally 
in 
with respect to 
if and only if 
is labelled 
in 
, but it is not legally 
in 
with respect to 
.
Example 4.4
Let us consider the two sub-frameworks in Example 4.2. Let 
and 
be two labellings of 
. So, for the sub-framework 
, the corresponding two partially labelled sub-frameworks are 
(in which Argument 
is OUT according to 
) and 
(in which Argument 
is also OUT according to 
), as illustrated in Figure 4.4. Now, with respect to 
, let 
. According to Definition 4.5, Argument 
is legally IN in 
with respect to 
because it is only attacked by Argument 
, which is labelled OUT in 
(and also in 
), while Argument 
is illegally IN because it is attacked by Argument 
which is labelled IN in 
.
.Based on the notion of legal labelling of a partially labelled sub-framework, under admissible, complete, preferred, grounded, stable, semi-stable, ideal, and eager semantics, the labelling(s) of a partially labelled sub-framework can be defined as follows.
Definition 4.6
Labelling-based semantics of a PLSF
Based on Definition 4.3, let 
be a labelling of 
.
• 
is called an admissible labelling with respect to 
, if and only if the following two conditions hold:
– 
is an admissible labelling; and
– each argument in 
that is labelled IN in 
is legally IN in 
with respect to 
, and each argument in 
that is labelled OUT in 
is legally OUT in 
with respect to 
.
• 
is called a complete labelling with respect to 
, if and only if the following two conditions hold:
– 
is a complete labelling; and
– 
is an admissible labelling with respect to 
and each argument in 
that is labelled UNDEC in 
is legally UNDEC in 
with respect to 
.
• 
is called a preferred labelling with respect to 
, if and only if the following two conditions hold:
– 
is a preferred labelling; and
– 
is a complete labelling with respect to 
, and 
is maximal (with respect to set-inclusion).
• 
is called a grounded labelling with respect to 
, if and only if the following two conditions hold:
– 
is a grounded labelling; and
– 
is a complete labelling with respect to 
, and 
is minimal (with respect to set-inclusion).
• 
is called a stable labelling with respect to 
, if and only if the following two conditions hold:
is a stable labelling; and– 
is a complete labelling with respect to 
, and 
.
• 
is called a semi-stable labelling with respect to 
, if and only if the following two conditions hold:
– 
is a semi-stable labelling; and
– 
is a complete labelling with respect to 
, and 
is minimal (with respect to set-inclusion).
• 
is called an ideal labelling with respect to 
, if and only if the following two conditions hold:
is an ideal labelling; and– 
is the biggest admissible labelling with respect to 
that is smaller than or equal to each preferred labelling with respect to 
.
• 
is called an eager labelling with respect to 
, if and only if the following two conditions hold:
is an eager labelling; and– 
is the biggest admissible labelling with respect to 
that is smaller than or equal to each semi-stable labelling with respect to 
.
According to Definition 4.6, the labelling 
is partially determined by the labelling 
. In Example 4.4, 
is an admissible labelling with regard to 
, but it is not an admissible labelling with regard to 
. This is because 
is an admissible labelling, while 
is not.
4.3.2 Extensions of a Conditioned Sub-Framework
Let 
and 
be sub-frameworks of an argumentation framework 
, and 
. From the perspective of the extension-based approach, the status of arguments in 
is determined by an extension, rather than a labelling. According to the notion of the status (accepted, rejected or undecided) of arguments, we may assign a status to each argument in 
. This process is called the status assignment of arguments.
Definition 4.7
Status assignment of arguments
Let 
be an argumentation framework, and 
be a set of arguments. For all 
, we may get a partition of 
:
,
, and
.We call 
a status assignment of 
with respect to 
, denoted as 
.
According to Definition 4.7, with respect to each extension 
of 
, we have a status assignment of 
, denoted as 
. It is obvious that if 
has more than one extension, then for each extension of 
, there is a corresponding status assignment of 
.
After the status of arguments in 
is assigned with respect to 
, the sub-framework 
is called a partially assigned sub-framework (PASF, for short), denoted as 
.
Definition 4.8
Partially assigned sub-framework
Let 
and 
be sub-frameworks of an argumentation framework 
, such that 
. Let 
be a conflict-free set, 
is a partially assigned sub-framework, denoting that the status of arguments in 
is assigned with respect to 
.
Given a partially assigned sub-framework 
, in which 
is an extension of 
under a semantics 
. Then, we say that a set 
of arguments is an extension of 
with respect to 
under the semantics 
if the following two conditions hold. First, the status of arguments in 
is assigned with respect to 
. Second, the status of argument in 
is evaluated according to the criterion specified by 
. Formally, we have the following definition.
Definition 4.9
Extension-based semantics of a PASF
Let 
be an unconditioned sub-framework of an argumentation framework 
, and 
be a conflict-free set of arguments. Let 
be a partially assigned sub-framework of 
. Let 
be a status assignment of 
with respect to 
. Let 
be a set of arguments.
• 
is conflict-free if and only if 
, such that 
.
• An argument 
is acceptable with respect to 
and 
, if and only if the following two conditions hold:
– 
, if 
, then 
, such that 
, or 
, such that 
(i.e., 
is accepted with respect to 
) and 
; and
– 
, if 
, then 
(i.e., 
is rejected with respect to 
).
• 
is admissible with respect to 
if and only if the following two conditions hold:
is admissible; and– 
is conflict-free, and each argument in 
is acceptable with respect to 
and 
.
• 
is a complete extension of 
with respect to 
if and only if the following two conditions hold:
– 
is a complete extension; and
– 
is admissible with respect to 
and each argument in 
that is acceptable with respect to 
and 
is in 
.
• 
is a preferred extension of 
with respect to 
if and only if the following two conditions hold:
– 
is a preferred extension; and
– 
is a maximal (with respect to set-inclusion) complete extension of 
with respect to 
.
• 
is a grounded extension of 
with respect to 
if and only if the following two conditions hold:
– 
is a grounded extension; and
– 
is the minimal (with respect to set-inclusion) complete extension of 
with respect to 
.
• 
is a stable extension of 
with respect to 
if and only if the following two conditions hold:
is a stable extension; and
is attacked by 
.• 
is a semi-stable extension of 
with respect to 
if and only if the following two conditions hold:
– 
is a semi-stable extension; and
– 
is a complete extension of 
with respect to 
, such that 
is maximal (with respect to set-inclusion).
• 
is ideal if and only if the following two conditions hold:
is an ideal extension; and– 
is the greatest (with respect to set-inclusion) admissible set with respect to 
and it is contained in every preferred set of arguments of 
with respect to 
.
• 
is an eager extension if and only if the following two conditions hold:
is an eager extension; and– 
is the greatest (with respect to set-inclusion) admissible set (with respect to 
) that is a subset of each semi-stable extension of 
with respect to 
.
In this definition, it is clear that if 
is admissible, then 
is conflict-free. Otherwise, 
, such that 
is attacked by an argument in 
. As a result, 
is not acceptable with respect to 
and 
. Contradiction.
Example 4.5
Let us consider again the sub-frameworks in Example 4.2. Under preferred semantics, 
has two extensions 
and 
. The status assignment of 
with respect to 
and 
respectively is as follows:
Then, we get two partially assigned sub-frameworks 
and 
(Figure 4.5).
According to Definition 4.9, under preferred semantics, 
has one extension 
, while 
has two extensions 
and 
. Here, the acceptability of arguments in each partially assigned sub-framework is related to the status of the arguments whose status is evaluated externally. For instance, in 
is acceptable with respect to 
and 
in that for the argument 
in 
that attacks 
, there exists 
in 
, such that 
, and for the argument 
in 
that attacks 
, there exists 
in 
, such that 
is accepted with respect to 
and 
.
.4.4 Computation of the Semantics of a Sub-Framework
As presented in the previous section, the semantics of a sub-framework could be formulated by the labelling-based approach or the extension-based approach. From the perspective of implementation, we may use the approaches mentioned in Chapter 3, with a slight modification.
In this section, we introduce two modified labelling-based algorithms for computing the preferred labellings and the grounded labelling of a partially labelled sub-framework, respectively.
As presented in Section 3.3, Modgil and Caminada’s algorithms (or briefly, MC algorithms) are developed for a Dung’s argumentation framework. For a partially labelled sub-framework 
, the MC algorithms should be modified such that the preferred labellings (or the grounded labelling) of a partially labelled sub-framework can be generated.
First, the algorithm for computing the preferred labelling of a partially labelled sub-framework is shown in Algorithm 4.1. Compared to the MC algorithm for computing preferred labellings, the modified algorithm is characteristic of the following three aspects.
First, since the labels of arguments in 
should conform to 
, the initial labelling of this algorithm is 
, in which all arguments in 
are labelled IN, while the labels of arguments in 
are assigned according to 
.
Second, only the labels of arguments in 
should be evaluated (to decide whether they are legal) and changed (by performing transition steps).
Third, when evaluating the legality of labels of arguments in 
, the labelling 
should be taken into consideration. Due to this reason, the notions of illegally IN, super-illegally IN and transition step are different from the ones in the MC algorithm. Since the notion of illegally IN has been defined in Definition 4.5, we need only to present the other two notions as follows (Definitions 4.10 and 4.11).
Definition 4.10
Super-illegally IN in a labelling of a PLSF
Let 
and 
be sub-frameworks of an argumentation framework 
, such that 
. Let 
be a labelling of 
under a semantics 
. Let 
be a labelling of 
. An argument 
that is illegally IN in 
with respect to 
, is also super-illegally IN in 
with respect to 
if and only if:
that is legally IN in 
with respect to 
or UNDEC in 
with respect to 
; or
that is labelled IN or UNDEC in 
.Example 4.6
Continue Example 4.4. Let 
. With respect to 
, let 
. According to Definition 4.10, Argument 
is super-illegally IN in 
with respect to 
, in that it is attacked by Argument 
in 
that is labelled IN in 
.
Definition 4.11
Transition step on an argument of a PLSF
Let 
and 
be sub-frameworks of an argumentation framework 
, such that 
. Let 
be a labelling of 
under a semantics 
. Let 
be a labelling of 
and 
be an argument that is illegally IN in 
with respect to 
. A transition step on 
in 
consists of the following:
is changed from IN to OUT;
, if 
is illegally OUT in 
with respect to 
, then the label of 
is changed from OUT to UNDEC.
Second, the algorithm for computing the grounded labelling of a partially labelled sub-framework is shown in Algorithm 4.2. Compared to the MC algorithm for computing the grounded labelling [4], there is only one difference, i.e., in Algorithm 4.2, the initial labelling is 
, rather than 
. This means that the labels of arguments in 
conform to 
.
4.5 Conclusions
In this chapter, we have defined two classes of sub-frameworks: unconditioned and conditioned. An unconditioned sub-framework is not dependent on any other sub-frameworks. Its semantics is the same as that of Dung’s argumentation framework introduced in Chapter 2. On the other hand, a conditioned sub-framework is restricted by some external arguments. After the status of all external arguments has been determined, we get a partially labelled (respectively, assigned) sub-framework. The labellings and extensions of a partially labelled (respectively, assigned) sub-framework are defined subsequently. Finally, we have introduced in brief two algorithms for computing the preferred labellings and the grounded labelling of a partially labelled sub-framework, respectively.
The notion of sub-frameworks have also been introduced in [5,6]. Given an argumentation framework 
and a subset 
, in [5], a sub-framework induced by 
is called the restriction of 
to 
. However, the notion of a partially labelled (assigned) sub-framework has not been formally described in the existing literature. One important advantage of introducing the notion of a conditioned subframework is that given a subset of arguments that might be affected by some other arguments, their status could be computed locally.
References
1. Liao B, Jin L, Koons RC. Dynamics of argumentation systems: a division-based method. Artificial Intelligence. 2011;175(11):1790–1814.
2. Liao B, Huang H. Partial semantics of argumentation: basic properties and empirical results. Journal of Logic and Computation. 2013;23(3):541–562.
3. Liao B. Toward incremental computation of argumentation semantics: a decomposition-based approach. Annals of Mathematics and Artificial Intelligence. 2013;67(3–4):319–358.
4. Modgil S, Caminada M. Proof theories and algorithms for abstract argumentation frameworks. Argumentation in Artificial Intelligence 2009;105–129.
5. Baroni P, Giacomin M, Guida G. SCC-recursiveness: a general schema for argumentation semantics. Artificial Intelligence. 2005;168(1–2):162–210.
6. Baumann R. Splitting an argumentation framework. In: Proceedings of the 11th International Conference on Logic Programming and Nonmonotonic Reasoning. 2011;40–53.
1According to the example, when an argumentation framework contains cycles, different sub-frameworks in which some arguments belong to a cycle may restrict each other.