1 Introduction
Many (if not all) realworld applications of sharing and reasoning knowledge are characterized by heterogeneous contexts, especially with the advent of the world wide web. Research in representing contexts and information flow between contexts has gained much attention recently in artificial intelligence
[11, 4, 7, 8, 5, 13] as well as in applications such as requirements engineering [10, 15, 14].Instead of finding a universal knowledge representation for all contexts, it has been increasingly recognized that it may be desirable to allow each context to choose a suitable representation tool for its own to capture its knowledge precisely. For example, in some frameworks such as Viewpionts for eliciting and analyzing software requirements developers often encourage stakeholders to use their own familiar terms and notations to express their demands so as to elicit requirements as full as possible [10, 15]. Moreover, the heterogeneous nature of contexts representations may allow different monotonic or nonmonotonic reasoning mechanisms to occur together in a given system. For example, as stated in [4], there is growing interest in combining ontologies based on description logics with nonmonotonic formalisms in semantic web applications. However, the diversity of representations of contexts in such cases brings some important challenges to accessing each individual context as well as to interlinking these contexts [5].
Nonmonotonic multicontext systems presented by Brewka and Eiter [4] can be considered as a promising way to deal with these challenges [5]
. Instead of attempting to translate all contexts with different formalisms into a unifying formalism, they leave the logics of contexts untouched and interlink contexts by modeling the intercontextual information exchange in a uniform way. To be more precise, information flow among contexts is articulated by socalled bridge rules in a declarative way. Similar to logical programming rules, each bridge rule consists of two parts, the head of the rule and the body of the rule (possibly empty). More importantly, each bridge rule allows access to other contexts in its body. This makes it capable of adding information represented by its head to a context by exchanging information with other contexts. In semantics, several equilibria representing acceptable belief states for multicontext systems are also given by Brewka and Eiter
[4].Multicontext systems can be viewed as the first step towards interlinking distributed and heterogeneous contexts effectively. The way they operating contextual knowledge bases is only limited to adding information to a context when the corresponding bridge rules are applicable [5]. To be more applicable to realworld applications, it is advisable to generalize multicontext systems from some perspectives. For example, Brewka et al have considerably generalized multicontext systems to managed multicontext systems (mMCS) by allowing flexible operations on context knowledge bases [5]. Essentially, managed multicontext systems focus on managed contexts, which are contexts together with possible operations on them.
Combining preferences and contexts is still an interesting issue in reasoning about contextual knowledge [3]. In particular, preferences on contexts have an important influence on information exchange between contexts and intercontextual knowledge integration in many realworld applications. For example, it is intuitive to revise a less reliable knowledge base by accessing more reliable ones. But we cannot use information deriving from less reliable sources to revise more reliable knowledge bases in general case. In legal reasoning, consequences of applying a law to a case can be rebutted by that of applying another law with higher level when there is a conflict, and not vise versa. In such cases, it may be advisable to take into account preferences on contexts in characterizing intercontextual information exchange in multicontext systems.
Moreover, taking into account the preference relation on contexts makes some subsets of more preferred contexts satisfying some given constraints more significant when the whole set of contexts does not satisfy the constraints. For example, in a multiparty negotiation, an agreement between the most important parties is preferred if it is difficult to achieve an agreement between all parties in many cases. In an incremental software development, only requirements with priorities higher than a given level are concerns of developers at a given stage.
To address these issues, we combine a multicontext system with a total preorder relation on its contexts to develop a preferential multicontext system (PMCS) in this paper. A preferential multicontext systems is given in the form of a sequence of sets of contexts such that the location of a set signifies its preference level. Without loss of generality, we assume that the smaller of the location of a set is, the more preferred contexts in that set are. We call each set of contexts in that sequence a stratum. Moreover, we assume that information flow cannot be from less preferred strata to more preferred ones. That is, any bridge rule of a given context does not allow any access to other strictly less preferred contexts in its body. As such, the first several strata also compose a new preferential multicontext system such that all the contexts involved in it are strictly more preferred than ones out of it. We call such a new preferential multicontext system a section of that system. We are interested in all sections as well as the whole preferential multicontext system, and then propose equilibria to represent belief sets acceptable for at least contexts in the first strata. In particular, the maximal consistent section describes a maximal section that has an equilibrium. Actually, it plays an important role in inconsistency analysis in a given preferential multicontext system, because it can be considered as maximally reliable part of that preferential multicontext system. We are more interested in finding diagnoses and inconsistency explanations compatible with maximal consistent section instead of all ones. Finally, we discuss computational complexity issues.
The rest of this paper is organized as follows. We give a brief introduction to multicontext systems in Section 2. We propose preferential multicontext systems in Section 3. In section 4, we discuss inconsistency analysis in preferential multicontext systems. We discuss complexity issues in Section 5. In section 6 we compare our work with some closely related work. Finally we conclude this paper in Section 7.
2 Preliminaries
In this section, we review the details of the definitions of multicontext systems presented by Brewka and Eiter [4] and inconsistency analysis in multicontext systems presented in [8]. The material is largely taken from [4] and [8].
The goal of multicontext systems is to combine arbitrary monotonic and nonmonotonic logics. Here a logic is referred to as a triple , where is the set of wellformed knowledge bases of , which characterizes the syntax of ; is the set of belief sets; and is a function describing the semantics of the logic by assign to each knowledge base (a set of formulas) a set of acceptable sets of beliefs [4].
Definition 2.1
[4] Let be a set of logics. A bridge rule over , , is of the form
where , is an element of some belief set of , and for each , .
Similar to logical programming rules, we call the left (resp. right) part of the head (resp. body) of the bridge rule .
Definition 2.2
[4] A multicontext system consists of a collection of contexts , where is a logic, is a knowledge base, and is a set of bridge rules over .
A multicontext system is finite if all knowledge bases and sets of bridge rules are finite [4].
Given a bridge rule , we use to denote the head of . Further, let and . Obviously, is exactly the set of contexts involved in the body of .
We use to denote the set of all bridge rules in , i.e, . For any set , we use to denote the set of all the rules in in unconditional form, i.e., . Let be a set of bridge rules, we use to denote the MCS obtained from by replacing with . For a set of sets of bridge rules, we use to denote the union of all sets in .
A belief state for is a sequence such that each . A bridge rule is applicable in a belief state iff for , and for , . We use to denote the set of all bridge rules that are applicable in belief state .
Definition 2.3
[4] A belief state of is an equilibrium iff, for , .
Essentially, an equilibrium is a belief state which contains an acceptable belief set for each context, given the belief sets for other contexts [4].
Example 2.1
Let be an MCS, where is a propositional logic, whilst both and are ASP logics. Suppose that

, ;

, ;

, .
Consider . Note that all bridge rules are applicable in , except .
Evidently, we can check is an equilibrium of .
Note that it cannot be guaranteed that there exists an equilibrium for a given multicontext system. Inconsistency in an MCS is referred to as the lack of an equilibrium [8]. We use to denote that is inconsistent, i.e., has no equilibrium. In this paper, we assume that every context to be consistent if no bridge rules apply, i.e., .
Example 2.2
Let be an MCS, where is a propositional logic, whilst both and are ASP logics. Suppose that

, ;

, ;

, .
Note that all bridge rules are applicable, except . The three applicable bridge rules in turn adds to , and then activates . So, has no equilibrium, i.e., .
To analyze inconsistency, inspired by debugging approaches used in the nonmonotonic reasoning community, T. Eiter et al have introduced two notions of explaining inconsistency, i.e., diagnoses and inconsistency explanations for multicontext systems [8]. Roughly speaking, diagnoses provide a consistencybased formulation for explaining inconsistency, by finding a part of bridge rules which need to be changed (deactivated or added in unconditional form) to restore consistency in a multicontext system, whilst inconsistency explanations provide an entailmentbased formulation for inconsistency, by identifying a part of bridge rules which is needed to cause inconsistency [8].
Definition 2.4
[8] Given an MCS , a diagnosis of is a pair , , s.t. . is the set of all such diagnosis.
Essentially, a diagnosis exactly captures a pair of sets of bridge rules such that inconsistency will disappear if we deactivate the rules in the first set, and add the rules in the second set in unconditional form [8].
Definition 2.5
[8] is the set of all pointwise subsetminimal diagnoses of an MCS , where the pointwise subset relation holds iff and .
Example 2.3
Consider again. Then
This means we need only to deactivate one of , , and , or to add unconditionally, in order to restore consistency for .
Definition 2.6
[8] Given an MCS , an inconsistency explanation of is a pair of sets of bridge rules s.t. for all where and , it holds that . By we denote the set of all inconsistency explanations of , and by the set of all pointwise subsetminimal ones.
Essentially, an inconsistency explanation captures a pair of sets of bridge rules such that the rules in the first set cause an inconsistency relevant to the MCS, and this inconsistency cannot be resolved by adding bridge rules unconditionally, unless we use at least one bridge rule in the second set [8].
Example 2.4
Consider again. Then
This means that the inconsistency in is caused by , , and together, moreover, it can be resolved by adding unconditionally.
Note that both addition and removal of knowledge can prevent inconsistency in nonmonotonic reasoning. So, a diagnosis consists of two sets of bridge rules including the set of bridge rules to be removed and that to be added unconditionally. As pointed out in [8], for scenarios where removal of bridge rules is preferred to unconditional addition of rules, we may focus on diagnoses of the form only.
Definition 2.7
[8] Given an MCS , an diagnosis of is a set s.t. . The set of all diagnoses (resp., minimal diagnoses) is (resp., ).
Similarly, we need only focus on inconsistency explanations in form of if adding rules unconditionally is less preferred.
Definition 2.8
[8] Given an MCS , an inconsistency explanation of is a set s.t. each where , satisfies . The set of all inconsistency explanations (resp., minimal inconsistency explanations) is (resp., ).
Example 2.5
Consider again. Then
More interestingly, Eiter et al have obtained the following duality relation between diagnoses and inconsistency explanations:
Theorem 2.1
This duality theorem shows that the unions of all minimal diagnoses and all inconsistency explanations coincide, i.e., diagnoses and inconsistency explanations represent dual aspects of inconsistency in an MCS [8].
3 Preferential Multicontext Systems
In this section we formally introduce a class of MCSs that allows us to consider preference information on contexts, called preferential multicontext systems, or simply PMCSs. As explained in the introduction, the motivation for such MCSs is that in many practical applications, it is often the case that some context has higher priority over another context. For example, the ontology SNOWMED CT (a context) will have higher priority over Wikipedia (another context) for medical doctors. In the setting of MCSs, an PMCS is a pair such that the following conditions are satisfied:

is an MCS that has a splitting .

is a total preorder^{1}^{1}1 A binary relation on some set is a total preorder relation if it is reflexive, transitive, and total, i.e., for all , we have that: (reflexivity), if and , then (transitivity), or (totality). on the set .
Recall that is a splitting for if for all and for all .
Informally, means that a context in is always preferred to a context in . We assume that the smaller a subscript is , the more preferred is. Then we use instead of from now on.
In an PMCS, preference information controls the information flow from one context to another context. Specifically, a context can be impacted only by more or equally preferred ones. This notion is formally defined as follows.
Definition 3.1
Let be a total preorder relation on the set of contexts .

The set of bridge rules of is compatible with the preorder relation on if for all , for all .

The set of bridge rules of is compatible with the preorder relation on if is compatible with for all .
Essentially, the compatibility of with implies that only information exchange between with some s satisfying for each may activate possible change of in .
Given an MCS and a total preorder relation on contexts in , we say that is compatible with iff is compatible with .
Definition 3.2 (Preferential multicontext system)
A preferential multicontext system (PMCS) is a pair , where is an MCS, and is a total preorder relation on contexts in such that is compatible with .
An PMCS is represented in the form of a sequence such that for , iff for some : , and . In particular, we may consider an MCS as a special PMCS , which contains only one stratum, i.e., .
Essentially, preferential multicontext systems take into account the impact of preference relation over contexts on intercontextual information exchange. Only information flow from a context to equally or less preferred ones are allowed to occur in preferential multicontext systems.
Let be an PMCS. Then the cut of for each , denoted , is defined as . Correspondingly, we call the section of . Note that the compatibility of and ensures that each section of is also an PMCS. Correspondingly, each cut of is an MCS. Informally speaking, given an PMCS, the section is exactly the PMCS consisting of the first strata in , in which all the contexts are preferred to ones in for each . This implies that the section of an PMCS exactly capture the intercontextual information exchange between contexts preferred to ones in .
A belief state for is a sequence such that is a belief state of for all , where is a concatenation operator. In particular, we use to denote .
Definition 3.3
A belief state of is an equilibrium of iff is an equilibrium of .
Example 3.1
Consider an PMCS , where and are propositional logics, and others are ASP logics. Suppose that

, ;

, ;

, ;

, ;

, .
Consider . Then all bridge rules are applicable in except . Moreover, it is easy to check that is an equilibrium of .
On the other hand, we can use a directed graph to illustrate the information flow in a (preferential) multicontext system , where , and if s.t. . For example, the information flow in is illustrated in Figure 1. Note that in such an information flow graph, there is at most one edge between any two contexts belonging to different strata, moreover, such an edge must be from a preferred context to another context.
As mentioned in [5], intercontextual information exchange among decentralized and heterogeneous contexts can cause an MCS to be inconsistent. Moreover, inconsistency in an MCS renders the system useless. However, in the case of preferential multicontext systems, inconsistency may not be considered as a totally undesirable. Allowing for preferences on contexts, we are more interested in some consistent sections of an inconsistent PMCS, which are significant in some applications. To address this issue, we generalize the notion of equilibrium to an equilibrium for an PMCS as follows.
Definition 3.4 (equilibrium)
Given an PMCS and a number . A belief state of is an equilibrium of iff is an equilibrium of the section of .
Roughly speaking, an equilibrium of a preferential multicontext system represents belief sets acceptable for at least all the contexts in the first strata of , given the belief sets for other contexts. Note that an equilibrium of must be an equilibrium for all . In particular, an equilibrium of is an equilibrium of for all . But it does not hold vice versa.
Definition 3.5 (equilibrium)
Given an PMCS and a number . A belief state of is called an equilibrium of iff

is an equilibrium of ,

but is not an equilibrium of if .
Essentially, an equilibrium of a preferential multicontext system represents belief sets acceptable for all the contexts in the first strata of , but not for at least one context in the stratum if , given the belief sets for other contexts. Evidently, any equilibrium of is an equilibrium according to this definition.
Definition 3.6 (Maximal equilibrium)
Given an PMCS and a number . A belief state of is called a maximal equilibrium of iff

is an equilibrium of ,

For any equilibrium of , .
Actually, a maximal equilibrium of a preferential multicontext system is indeed an equilibrium of that system if that system is consistent, otherwise, it represents belief sets acceptable for contexts in a section which cannot keep consistent if we add the next stratum to it.
Example 3.2
Consider an PMCS
where , , and are propositional logics, and others are ASP logics. Suppose that

, ;

, ;

, ;

, ;

, ;}

, .
Evidently, all bridge rules are applicable except . Moreover, applying , , and in turn adds to , and then activates . On the other hand, applying , , and in turn adds to , and then results in both and occurring in . So, has no equilibrium, i.e., . Moreover, it also implies that its section also has no equilibrium, i.e., .
However, both the section and section of are consistent. Obviously, we can check

is an equilibrium, but not an equilibrium; So, it is an equilibrium.

is an equilibrium;

is a maximal equilibrium of .
An occurrence of inconsistency in a multicontext system makes that system useless. However, considering preferences in preferential multicontext systems makes things better. The section corresponding to a maximal equilibrium may be interesting and useful in the presence of inconsistency, because it fully captures the meaningful information exchange among contexts involved in this section.
4 Inconsistency Analysis
Now an interesting question arises: how to measure the degree of inconsistency for an PMCS? Note that the value points out the stratum where we first meet inconsistency if a given inconsistent PMCS has a maximal equilibrium. In particular, if we abuse the notation and say that has a maximal equilibrium if it has no maximal equilibrium for any given . Then is exactly the inconsistency rank for stratified knowledge bases presented in [1, 2] in essence. To bear this in mind, we present the following inconsistency measure.
Definition 4.1
Given an PMCS . The degree of inconsistency of , denoted , is defined as
if has the maximal equilibrium, where .
Actually, the degree of inconsistency of is a slight adaptation of the inconsistency rank such that

;

iff is consistent;

iff .
Note that the first two properties are called Normalization and Consistency, respectively [12]. The third property says that an PMCS has the upper bound iff there is no consistent section.
Example 4.1
Consider again. Note that
because it has an maximal equilibrium as illustrated above.
The measure allows us to have a sketchy picture on the inconsistency in . In many applications, we need to find more information about the inconsistency. For example, we need to know which contexts and bridge rules of a given PMCS are involved in the inconsistency in order to restore consistency of the PMCS.
Note that any two contexts are considered equally preferred in inconsistency handling in the case of multicontext systems. However, preferences over contexts play an important role in dealing with inconsistency among these contexts, especially in making some tradeoff decisions on resolving inconsistency when we take into account preferences. Generally, the more preferred contexts are considered more reliable when an inconsistency occurs in a preferential multicontext system, moreover, remaining unchanged is preferred to any action of revision for such contexts. For example, in requirements engineering, when two requirements with different priority levels contradict each other, a less preferred requirement will be revised to accommodate itself to another one in most cases.
Given an PMCS, each section actually splits the whole set of contexts into two parts, i.e., itself and a set of other strictly less preferred contexts. Moreover, each consistent section fully captures information exchange among contexts which are strictly preferred to ones not included in that section. Generally, such a section may be considered as one of plausible parts of that PMCS. Allowing for this, we are more interested in a section that contains more preferred strata as much as possible. Moreover, any changes of bridge rules for restoring consistency should not affect information exchange among contexts in such a section. In this sense, identifying a consistent section with the maximal number of strata is central to inconsistency analysis in a preferential multicontext system.
Definition 4.2 (Maximal consistent section)
Given an PMCS , the section of , is called a maximal consistent section of , if

;

for all .
Informally speaking, the maximal consistent section of an PMCS can be considered as a reliable part of that PMCS. We use to denote the maximal consistent section of . Evidently, given an inconsistent PMCS , a maximal equilibrium of is exactly an equilibrium of the section , because less preferred contexts cannot bring new information to more preferred contexts in an PMCS. This implies that finding the maximal consistent section may be not harder than finding maximal equilibrium.
Example 4.2
Consider again. The section is its maximal consistent section.
As mentioned above, Eiter et al have proposed diagnoses and inconsistency explanations for a multicontext system. We use the following example to demonstrate what will happen when we apply these to a preferential multicontext system.
Example 4.3
Consider again. Note that all of the following sets of rules are minimal diagnoses of :

, ,;

, , ;

, , .
Note that all of the minimal diagnoses contains one bridge rule of maximal consistent section except . That is, according to for all , we need to deactivate some information exchange in maximal consistent section to restore consistency in . In contrast, leaves information exchange in maximal consistent section unchanged. Allowing for preferences relation over contexts, is more significant for inconsistency handling in .
The example above illustrates that diagnoses not involving maximal consistent section in inconsistency are more preferred. Allowing for the duality relation between diagnoses and explanations, we have the same opinion on inconsistency explanations. However, the compatibility to more preferred knowledge is considered as one of useful strategies in preferential knowledge revision and integration [1, 2]. Next we adapt diagnoses and inconsistency explanations to accommodate maximal consistent section, respectively.
Definition 4.3
Given an PMCS , a diagnosis of is compatible to the maximal consistent section of if .
Note that if we focus on the maximal consistent section of a preferential multicontext system, then the set of bridge rules of all contexts out of the section exactly composes a diagnosis of inconsistency for that system, because . This guarantees that there exists at least one diagnosis compatible with the maximal consistent section.
Example 4.4
Consider again. All of , and are diagnoses compatible to the maximal consistent section.
Furthermore, we consider minimal diagnoses compatible with the maximal consistent section of a given PMCS.
Definition 4.4 (diagnosis)
Given an PMCS , an diagnosis of , is called an diagnosis of , if and . The set of all diagnosis of is .
Essentially, an diagnosis of is an minimal diagnosis that is compatible with the maximal consistent section of , i.e., none of bridge rules of the maximal consistent section of is involved in .
Example 4.5
Consider again. Then is a unique diagnosis compatible to the maximal consistent section, i.e., .
Note that for all , and . So, , but not vice versa.
Definition 4.5 (inconsistency explanation)
Given an PMCS , an inconsistency explanation of , is a set s.t. each , satisfies . The set of all minimal inconsistency explanations of is .
Essentially, an inconsistency explanation focuses on the set of other bridges rules need to cause an inconsistency given a set of bridge rules of the maximal consistent section. Both inconsistency explanations and diagnoses capture the inconsistency under an assumption that every bridge rule of the maximal consistent section should not be revised or modified to restore consistency.
Example 4.6
Consider again. Then both and are minimal inconsistency explanations compatible to the maximal consistent section, moreover, .
More interestingly, we have the following weak duality relation between diagnoses and inconsistency explanations.
Proposition 4.1
Given an inconsistent PMCS , then
Proof
This is a direct consequence of Theorem 2.1 in essence. The main part of this proof is the same as that of Theorem 2.1 provided in [8].
Let be an PMCS and its maximal consistent section. The complement of w.r.t. is denoted as .
We first prove that holds. Let , then . We show that there exists with , for .
Consider , then and . Let . Then for all , .
Suppose that there exists with and . Then , and , then . So, .
Then we prove that holds. Let , then . We show that there exists with , for .
Consider . Let . Assume that , then
Comments
There are no comments yet.