# preferencebased_inconsistency_management_in_multicontext_systems__a85a9d47.pdf

Journal of Artiﬁcial Intelligence Research 60 (2017) 347-424 Submitted 12/16; published 10/17

Preference-Based Inconsistency Management in Multi-Context Systems

Thomas Eiter EITER@KR.TUWIEN.AC.AT Technische Universit at Wien Institut f ur Informationssysteme Abteilung f ur Wissensbasierte Systeme Favoritenstr. 9-11, 184/3 1040 Vienna, Austria

Antonius Weinzierl ANTONIUS.WEINZIERL@AALTO.FI Aalto University Department of Computer Science Konemiehentie 2 02150 Espoo, Finland

Multi-Context Systems (MCS) are a powerful framework for interlinking possibly heterogeneous, autonomous knowledge bases, where information can be exchanged among knowledge bases by designated bridge rules with negation as failure. An acknowledged issue with MCS is inconsistency that arises due to the information exchange. To remedy this problem, inconsistency removal has been proposed in terms of repairs, which modify bridge rules based on suitable notions for diagnosis of inconsistency. In general, multiple diagnoses and repairs do exist; this leaves the user, who arguably may oversee the inconsistency removal, with the task of selecting some repair among all possible ones. To aid in this regard, we extend the MCS framework with preference information for diagnoses, such that undesired diagnoses are ﬁltered out and diagnoses that are most preferred according to a preference ordering are selected. We consider preference information at a generic level and develop meta-reasoning techniques on diagnoses in MCS that can be exploited to reduce preference-based selection of diagnoses to computing ordinary subset-minimal diagnoses in an extended MCS. We describe two meta-reasoning encodings for preference orders: the ﬁrst is conceptually simple but may incur an exponential blowup. The second is increasing only linearly in size and based on duplicating the original MCS. The latter requires nondeterministic guessing if a subset-minimal among all most preferred diagnoses should be computed. However, a complexity analysis of diagnoses shows that this is worst-case optimal, and that in general, preferred diagnoses have the same complexity as subset-minimal ordinary diagnoses. Furthermore, (subset-minimal) ﬁltered diagnoses and (subset-minimal) ordinary diagnoses also have the same complexity.

1. Introduction

At the dawn of an age with growing information connectivity, the issue of interlinking and combining information from various knowledge sources is of increasing importance, posing a challenge to Artiﬁcial Intelligence and to Knowledge Representation and Reasoning in particular. Indeed, with the rise of the internet, sharing information has become as easy as never before, and a wealth of knowledge and information sources is available that can be accessed via communicating devices. Multi-Context Systems (Giunchiglia & Seraﬁni, 1994; Roelofsen & Seraﬁni, 2005; Brewka

c 2017 AI Access Foundation. All rights reserved.

EITER & WEINZIERL

& Eiter, 2007; Bikakis & Antoniou, 2010) are a well-known approach to address the challenge of sharing information, where individual knowledge bases, called contexts, are interlinked with special bridge rules which govern the information exchange, such that a global semantics of the system emerges from the local semantics of the constituent knowledge bases. Some practical applications of MCS are defeasible reasoning in ambient intelligence (Bikakis & Antoniou, 2010), cooperation in distributed information systems (Caire & Bikakis, 2011), and the METIS system for maritime situation awareness support (Velikova et al., 2014).

Rooted in the seminal work of Mc Carthy (1993), which proposed an explicit representation of context where combining different views may give a holistic picture of a situation, the Trento School around Giunchiglia and Seraﬁni developed a notion of multi-context system that is geared to interlink possibly non-monotonic knowledge bases and can be utilized for query answering (Giunchiglia & Seraﬁni, 1994; Ghidini & Giunchiglia, 2001; Roelofsen & Seraﬁni, 2005; Brewka, Roelofsen, & Seraﬁni, 2007). Brewka and Eiter (2007) generalized this to an abstract framework in which contexts can have heterogeneous knowledge bases that are described using a very abstract notion of logic; Context Knowledge Repositories (Seraﬁni & Homola, 2012) evolved MCS in a different direction for the Semantic Web, where meta and object knowledge can be intermingled. For a more detailed overview of MCS, see the work of Brewka et al. (2011a).

As the contexts of an MCS are typically autonomous and host knowledge bases that are inherited legacy systems, it may happen that the information exchange leads to unforeseen conclusions and in particular to inconsistency; to anticipate and handle all such situations at design time is difﬁcult if not impossible, especially if sufﬁcient details about the knowledge bases are lacking. Inconsistency of an MCS means that it has no model (called equilibrium) where a global model is composed of a local model for each context s knowledge base such that all bridge rules governing the information exchange are satisﬁed; thus, the whole MCS becomes useless.

To repair an inconsistent MCS, basic notions for inconsistency management have been developed by Eiter, Fink, Sch uller, and Weinzierl (2010, 2014). Most notably, the notion of diagnosis formalizes the removal of an inconsistency by modifying the information exchange, that is, the bridge rules for the information ﬂow between the contexts. However, while an arbitrary diagnosis restores consistency, the modiﬁed information exchange that it affects may have serious consequences, as shown in the following example.

Example 1. Consider an MCS employed in a hospital, which interconnects three systems: (1) a patient knowledge base storing information e.g. about illnesses, insurance companies, and potential allergies of patients; (2) an expert system suggesting proper treatments to illnesses; and (3) a system billing the insurance company of patients for the administered treatments (a formal account is given later, cf. Example 3, Figure 1). The expert system only recommends treatments to which patients are not allergic, while the billing system only allows administered treatments that are covered by the insurance companies. Now suppose a patient with speciﬁc allergies can be cured only with a drug that is not covered by his/her insurance; this makes the whole MCS inconsistent and hence no treatment for any patient can be soundly inferred. It is easy to repair this inconsistency, e.g. by modifying the information ﬂow such that either the illness or allergy of the patient is ignored, which results in either not treating the patient or causing an allergic reaction. An alternative repair is to not inform the billing system about the uncovered administration of the drug, so the patient is correctly treated at potential ﬁnancial loss of the hospital.

PREFERENCE-BASED INCONSISTENCY MANAGEMENT IN MULTI-CONTEXT SYSTEMS

Fully-automated, unreﬂected inconsistency removal may ignore vital information and lead to dangerous results. It is thus desirable or even necessary to keep a human operator in the loop while selecting a suitable diagnosis for repair. However, in realistic scenarios often a large (even exponential) number of diagnoses exists, which makes careful manual selection a very time consuming task if not infeasible under time and cognitive constraints. The risk of choosing an improper diagnosis or ending up with no (approved) diagnosis clearly is an obstacle to the deployment of MCS to a broader range of application domains. Also note that inconsistency can arise in all applications: some context may consider certain data to be unrealistic, e.g. in ambient intelligence when the reading from a light sensor is regarded as too high after the janitor installed new light bulbs in the rooms; or some context may not expect to receive a certain combination of data from other contexts, e.g. in case of maritime control when a ship is reported to be both faster and bigger than in the record of the knowledge base. In the former case, removing the actual data from the light sensor restores consistency but it might be more preferred to replace the too-high value with an acceptable one. In the latter case there are scenarios where it is more useful to know the speed of a ship correctly and underestimate its size while for other scenarios it can be the other way round, e.g. to ensure that an inspection crew is large enough for the ship s size.

The goal of this work thus is to develop some machinery for automatic identiﬁcation of preferred diagnoses and pruning of those that are unwanted, in order to only require from the human operator to select from a much smaller set (of most preferred diagnoses) the best diagnosis manually. What constitutes a preferred or best diagnosis, cannot be decided in general since it will be different for each MCS and depends on the environment into which an MCS is embedded. In the above example, the health of patients may be considered paramount, but from an economic perspective billing correctly may be considered of highest importance. In any case, we observe that such a decision is up to the person or institution employing the MCS.

Automatic selection of the preferred diagnoses according to some preference requires in turn a formalism for expressing and evaluating preferences. Many such formalisms are available; a prominent and important one are ceteris paribus preferences (Doyle et al., 1991), CP-nets (Boutilier et al., 2004; Domshlak et al., 2001; Goldsmith et al., 2008), or utility functions (Von Neumann & Morgenstern, 1944) widely used in economics. As there is no one-ﬁts-all preference formalism that suits every use case, it is a challenge to accommodate any preference formalism that a user deems to ﬁt for selecting most preferred diagnoses. Our approach is based on the idea that a user-customized preference on diagnoses, speciﬁed in a formalism chosen by the user, can be seen as a knowledgebase or context of an MCS. This context must be enabled to see the diagnoses of the MCS, which is technically challenging. Furthermore, the selection of most preferred diagnoses according to the preference context turns out to be computationally harder than originally thought. As we show, this complexity increase is not due to our meta-reasoning approach, but is intrinsic to the problem, and our approach is worst-case optimal.

Our main contributions are brieﬂy summarized as follows:

We propose two basic methods for selection of preferred diagnoses: one allows to ﬁlter out diagnoses that fail some properties (similar to hard constraints); the other method compares diagnoses with each other in a binary relation and identiﬁes the most preferred one(s). We call the functionalities of these methods ﬁlters and preference orders, respectively. Both are general concepts that can capture many concrete instances to express unwanted or preferred diagnoses. In the ﬂexible and open spirit of the MCS framework, we do not commit to a particular formalism in which ﬁlters and

EITER & WEINZIERL

preference orders are speciﬁed, but remain at an abstract level and leave the choice of a particular formalism to the user. As illustrative sample instantiations, we consider here CP-nets.

To realize the selection of diagnoses in such an open way, we develop three transformations to enable meta-reasoning about diagnoses in MCS, i.e., given an MCS and a ﬁlter or preference order, a transformed MCS is constructed such that the diagnoses of the original MCS also occur in the transformed MCS, but an additional context is able to observe these diagnoses and apply custom (preference) reasoning. Since the observer context is not restricted to any particular formalism, this allows one to express ﬁlters and preference orders in any formalism that can be couched into a context of an MCS.

For the selection of (most) preferred diagnoses, three extensions of the notion of diagnosis are introduced, namely protected-minimal, prioritized-minimal, and subset-minimal prioritized minimal diagnosis. We investigate the computational complexity of these notions and show by polynomial-time reductions that the ﬁrst two are of the same complexity as checking whether a pair of sets of bridge rules constitutes a subset-minimal diagnosis. For the third notion, we provide a novel non-deterministic refutation algorithm that works in polynomial time with the help of an oracle for one of the other notions. Still the algorithm is worst-case optimal in a number of settings, as it matches the complexity of the underlying problem. A byproduct of these results are concrete algorithms that can exploit an existing implementation of inconsistency explanation (B ogl, Eiter, Fink, & Sch uller, 2010). The results of this work may be applied to concrete instances of MCS, and the basic notions and results may be carried over to generalizations and recent extensions of MCS, as we shall discuss; furthermore, they may be of use for formalisms that can be modeled using (extensions or variants of) MCS, such as hybrid MKNF knowledge bases (Knorr, Slota, Leite, & Homola, 2014), knowledge base networks (Eiter & ˇSimkus, 2015), or Boolean networks (Kauffman, 1969, 1993, cf. Inoue, 2011), to mention a few.

1.1 Organization

The remainder of this article is structured as follows. After recalling preliminary notions and ﬁxing notation in Section 2, we introduce in Section 3 ﬁlters and preference orders and consider some sample instantiations. In Section 4 we investigate how an (extended) MCS can be enabled to select diagnoses of the original MCS. In Section 5 we show how diagnoses may be selected according to a ﬁlter or a preference order and prove the correctness of these realizations, while in Section 6 their computational complexity is investigated. Section 7 discusses related work and in Section 8 we conclude with a summary and an outlook. Proofs of theorems and propositions as well as some detailed examples are in the appendix. This article is strongly based on the work of Weinzierl (2014), which in turn is a signiﬁcant extension and revision of work by Eiter, Fink, and Weinzierl (2010).

2. Preliminaries

In this section we recall the framework of Multi-Context Systems (MCS) by Brewka and Eiter (2007) and notions for inconsistency management in MCS from Eiter et al. (2014). The MCS framework is based on three basic concepts: abstract logics to capture knowledge-representation formalisms, contexts which represent concrete instances of knowledge bases, and bridge rules to

PREFERENCE-BASED INCONSISTENCY MANAGEMENT IN MULTI-CONTEXT SYSTEMS

specify the information exchange; an MCS then simply is a collection of such contexts and their respective bridge rules. Finally, the semantics of an MCS is given in terms of equilibria. To capture all kinds of knowledge-representation formalisms, the concept of an abstract logic is used, which reduces it to the set-theoretic level.

Deﬁnition 1 (Brewka & Eiter, 2007). An abstract logic L, is a triple L = (KB, BS, ACC) where:

KB is the set of knowledge bases of L, where each knowledge base kb KB is a set of elements called formulas .

BS is the set of possible belief sets, where each S BS is a set of elements called beliefs .

ACC : KB 2BS is a function describing the semantics of the logic, by assigning to each knowledge base a set of acceptable belief sets.

Intuitively, each knowledge base kb KB is a set of well-formed formulas while each belief set bs BS is a set of beliefs (statements) that a reasoner may jointly hold. The acceptability function ACC(kb) singles out, given a knowledge base kb KB, those sets of beliefs that are acceptable according to some reasoning method for kb. ACC is a multi-valued function in order to capture also nonmonotonic formalisms, where a knowledge base may have multiple acceptable belief sets (as e.g. for Answer-Set Programming, see Gelfond & Lifschitz, 1991; Default Logic, see Reiter, 1980; or in Abstract Argumentation, see Dung, 1995). Depending on the concrete situation, e.g. given an existing legacy system or a theorem prover for a speciﬁc logic, different formalizations for some logic might be used. There is no ﬁxed mapping between a given logic and an abstract logic representing it, and the mapping may be adjusted to speciﬁc application needs. The approach allows one to capture ﬂexibly, e.g., a knowledge-base, an expert system using a logic program, and a billing system using a description logic ontology as they might occur in the scenario described in Example 1. Let us consider two examples for abstract logics.

Example 2. Classical propositional logic might be modeled as follows:

KB is the set of all (well-formed) formulas over a signature Σ built using , , , ;

BS is the set of deductively closed sets S of Σ-formulas (i.e., S = Cn(S)); and

ACC(kb) is the singleton set {Cn(kb)}.

Disjunctive logic programs under answer set semantics over a function-free ﬁrst order signature Σ may be modeled as follows:

KB is the set of disjunctive logic programs over Σ, i.e., each kb KB is a set of rules r

a1 . . . an b1, . . . , bi, not bi+1, . . . , not bm. n + m > 0, (1)

also written H(r) B(r), where all ai, bj, are atoms over Σ and not is negation as failure; we further require that each variable in r occurs also in b1, . . . , bi (safety).

BS is the set of Herbrand interpretations over Σ, i.e, each S BS is a set of ground (variable-free) atoms from Σ, and

EITER & WEINZIERL

ACC(kb) is the set of answer sets of kb, i.e., consists of all S BS such that (i) S is a model of kb S and (ii) no S S is a model of kb S (Faber, Leone, & Pfeifer, 2004), where kb S = {r grnd(P) | S |= B(r)} is the set of all ground instances r of rules in P whose body B(r) is satisﬁed by S; here for evaluation, not is treated like classical negation .

We denote these modelings by Lpl Σ and Lasp Σ , respectively.

We remark that each rule r with n = 0 is a constraint; its heads H(r) amounts to , where is a falsity. We view the latter as a special atom that is false in every Herbrand interpretation. In the remainder of this work we often omit the explicit deﬁnition of the signature Σ for an abstract logic if it is clear from the context. To specify information exchange between contexts, so-called bridge rules are used. Bridge rules are similar in form and behavior to rules in logic programming. They differ from each other by the fact that bridge rules are based on beliefs from (possibly) different abstract logics and corresponding contexts. Based on the presence (or absence) of beliefs at other contexts, a bridge rule can add information to a context.

Deﬁnition 2 (Brewka & Eiter, 2007). Given a sequence L = (L1, . . . , Ln) of abstract logics Lj = (KBj, BSj, ACCj), 1 j n, an Lk-bridge rule over L, with k {1, . . . , n} is of form:

(k : s) (c1 : p1), . . . , (ci : pi), not (ci+1 : pi+1), . . . , not (cm : pm). (2)

where for each 1 i m we have that ci {1, . . . , n}, pi S BSci is an element of some belief set of Lci, and s S KBk is a knowledge base formula of Lk.

Each bridge rule in an MCS is associated to a certain context in such a way that all Lk bridge rules belong to the context with identiﬁer k. We denote by ϕ (r) the formula s in the head of r and by Ch (r) the context k where r belongs to. The full head of r is denoted by head(r) = (k : s), thus head(r) = (Ch (r) : ϕ (r)). The literals in the body of r are referred to as body (r), body+(r), body (r), body(r), which denote the sets {(c1 : p1), . . . , (cm : pm)}, {(c1 : p1), . . . , (cj : pj)}, {(cj+1 : pj+1), . . . , (cm : pm)}, {(c1 : p1), . . . , (cj : pj), not (cj+1 : pj+1), . . . , not (cm : pm)}, respectively. Furthermore, Cb (r) denotes the set of contexts referenced in r s body, i.e., Cb (r) = {ci | (ci : pi) body (r)}. Note that different from the work of Brewka and Eiter (2007), the head of r contains not only the knowledge-base formula s but also the context identiﬁer k. This choice merely is syntactic sugar and allows easier identiﬁcation of the context where r belongs to. For later technical use, we denote by cf (r) the condition-free bridge rule resulting from r by removing all elements in its body, i.e., cf (r) is (k : s) . and for any set of bridge rules R, we let cf (R) = S r R cf (r). We emphasize that bridge rules only deal with elements of knowledge bases and elements of belief sets, both of which are considered to be atomic expressions from the perspective of MCS. Incorporating variables into bridge rules is possible but requires restrictions on context logics or additional machinery for variable substitution (for details, see Fink, Ghionna, & Weinzierl, 2011; Barilaro, Fink, Ricca, & Terracina, 2013; Sch uller & Weinzierl, 2011). Since bridge rules are the only way to exchange information between contexts and bridge rules only refer to beliefs, the contents of a context (i.e., its knowledge-base and semantics) is completely hidden from other contexts. In addition to that, there is no central point of information exchange, hence the MCS framework is somewhat decentralized.

PREFERENCE-BASED INCONSISTENCY MANAGEMENT IN MULTI-CONTEXT SYSTEMS

With bridge rules to connect contexts at hand, Multi-Context Systems are deﬁned as follows.

Deﬁnition 3 (cf. Brewka & Eiter, 2007). A Multi-Context System is a collection M = (C1, . . . , Cn) of contexts Ci = (Li, kbi, bri), 1 i n, where (i) Li = (KBi, BSi, ACCi) is an abstract logic, (ii) kbi KBi is a knowledge base, and (iii) bri is a set of Li-bridge rules over L = (L1, . . . , Ln). Furthermore, for each H {ϕ (r) | r bri} it holds that kbi H KBi (i.e., knowledge bases are closed under adding bridge rule heads).

In the sequel, br(M) = Sn i=1 bri denotes the set of all bridge rules of M; C (M) = {1, . . . , n} denotes the set of all context identiﬁers of M; and bri(M) denotes the set of bridge rules of context i of M, i.e., bri(M) = {r br(M) | Ch (r) = i}.

Example 3. The MCS described in Example 1 can now be formalized. Let M = (C1, C2, C2) be an MCS with three contexts: a patient knowledge-base C1, a logic program C2 suggesting proper medication, and a logic program C3 handling the billing. Context C1 uses the abstract logic Lpl Σ, while both C2 and C3 use Lasp Σ . We restrict our example to a single patient with the knowledge bases kb1, kb2, and kb3 as given in Figure 1 on page 354 for the contexts C1, C2, and C3, respectively. Intuitively, the knowledge base kb1 of context C1 states that the patient has severe hyperglycemia, that she is allergic to animal insulin, and that her health insurance is with company B. Context C2 s knowledge base kb2 suggests to apply either human or animal insulin if the patient has hyperglycemia and requires that the applied insulin does not cause an allergic reaction. Context C3 does the billing and encodes that insurance B only pays animal insulin. The MCS M contains ﬁve rather simple bridge rules shown in Figure 1 (bridge rules are presented in the format name: head body. ). Their task is to carry information from one context to another. Bridge rule r1, for example, carries information about hyperglycemia of the patient from the patient knowledge-base C1 to the medication recommender system C2. Bridge rule r2 is the sole non-monotonic one and it turns the absence of an allergy to animal insulin (in C1) into the allowance to administer this kind of insulin (in C2). A graphical depiction of M is shown in Picture 1 inside Figure 1. The latter also shows the minimal diagnoses of M (cf. below for further details).

The semantics of an MCS M = (C1, . . . , Cn) is deﬁned in terms of special belief states, which are sequences S = (S1, . . . , Sn) of belief sets Si BSi, 1 i n; intuitively, each Si must be a locally accepted belief set where the bridge rules of context Si are respected. To formalize this, we call a bridge rule r of form (2) applicable in a belief state S, denoted by S r, if (i) for each (j : p) body+(r) it holds that p Sj, and (ii) for each (j : p) body (r) it holds that p / Sj. For a set R of bridge rules and a belief state S, app(R, S) denotes the set of bridge rules of R that are applicable in S, i.e., app(R, S) = {r R | S r}. We can now deﬁne the desired belief states of an MCS as follows.

Deﬁnition 4 (cf. Brewka & Eiter, 2007). A belief state S = (S1, . . . , Sn) of M is an equilibrium if for every belief set Si, 1 i n, it holds that Si ACCi kbi {ϕ (r) | r app(bri, S)} . The set of all equilibria of an MCS M is denoted by EQ(M).

To create bridge rules that are always resp. never applicable, we also allow r = (k : s) , resp. r = (k : s) , where S r resp. S r for every belief state S. Here denotes the empty body and a body containing (ℓ: p), not (ℓ: p) where p is any belief of any context Cℓ. For simplicity, we assume that the bridge rules r and r have no body literals.

EITER & WEINZIERL

Figure 1: The Hospital MCS M = (C1, C2, C3) with knowledge bases kbi and bridge rules rj.

kb1 = {hyperglycemia, allergic animal insulin, insurance B}

kb2 = { give human insulin give animal insulin hyperglycemia.

give animal insulin, not allow animal insulin}

kb3 = { bill bill animal insulin.

bill more bill human insulin.

insurance B, bill more.}

r1: (2 : hyperglycemia) (1 : hyperglycemia).

r2: (2 : allow animal insulin) not (1 : allergic animal insulin).

r3: (3 : bill animal insulin) (2 : give animal insulin).

r4: (3 : bill human insulin) (2 : give human insulin).

r5: (3 : insurance B) (1 : insurance B).

Patient data C1 Medication C2

Picture 1: The MCS M visualized.

The set of minimal diagnoses of M is:

D m(M) = {r1} , , {r4} , , {r5} , , , r2 .

Application of these diagnoses intuitively results in:

({r1} , ) illness of the patient is ignored. ({r4} , ) medication is not billed. ({r5} , ) insurance company receives bill it will not pay. ( , {r2}) patient is given medication she is allergic to.

No diagnosis is clearly the best, it depends on one s preferences.

PREFERENCE-BASED INCONSISTENCY MANAGEMENT IN MULTI-CONTEXT SYSTEMS

Given an MCS M = (C1, . . . , Cn) over abstract logics L = (L1, . . . , Ln), a set R of bridge rules is compatible with M, if a partitioning R1, . . . , Rn of R = Sn k=1 Rk exists where every r Rk is an Lk-bridge rule over L. For such R, we write M[R] for the MCS that results by replacing its bridge rules with R. E.g., M[br(M)] = M and M[ ] is M with no bridge rules. We say that M is inconsistent, denoted M |= , if M has no equilibrium, i.e., EQ(M) = . The converse, that M is consistent, is denoted by M |= , i.e., EQ(M) = . For a consistency-based explanation of inconsistency pairs (D1, D2) of sets of bridge rules are considered, such that if we deactivate the rules in D1 and add the rules in D2 in condition-free form, the MCS becomes consistent (i.e., admits an equilibrium).

Deﬁnition 5. Given an MCS M, a diagnosis of M is a pair (D1, D2), D1, D2 br(M), such that M[br(M) \ D1 cf (D2)] |= . We denote by D (M) the set of all diagnoses.

An alternative reading of Def. 5 is that a diagnosis indicates which bridge rules are assumed to require modiﬁcation in order to obtain a consistent MCS, i.e., a diagnosis constitutes a way to repair an MCS if its bridge rules are modiﬁed according to the diagnosis. Adding rules condition-free is the most severe form of modiﬁcation of a rule s body, but as shown by Eiter et al. (2014), this notion also allows one to capture more ﬁne-grained forms of modiﬁcation. We call any pair D = (D1, D2) 2br(M) 2br(M) a candidate diagnosis (regardless of whether D D (M) holds). We denote the MCS resulting from the application of a candidate diagnosis (D1, D2) (br(M), br(M)) by M[D1, D2], which equals the MCS M[br(M) \ D1 cf (D2)]. Following Occam s razor, one may consider those diagnoses to be the preferred ones that require the least modiﬁcations. This motivates the notion of minimal diagnosis.

Deﬁnition 6. Given an MCS M, a diagnosis D D (M) is (pointwise) subset minimal, if no D D is in D (M); by D m(M) we denote all such D, i.e., D m(M) = {D D (M) | D D (M) : D D D D }.

Here, given pairs A = (A1, A2) and B = (B1, B2) of sets, the pointwise subset relation A B holds iff A1 B1 and A2 B2; moreover, A B holds iff A B A = B, where A = B holds iff A1 = B1 A2 = B2.

Example 4. Reconsider the MCS M of Example 3. Since the patient has hyperglycemia and is allergic to animal insulin, the belief set containing give human insulin is the only one acceptable at C2, i.e., the human insulin must be given. Since the insurance company does not cover human insulin, the billing context C3 admits no acceptable belief set and the MCS M therefore is inconsistent. As shown at the bottom of Figure 1, the minimal diagnoses of M are D m(M) = {D(1), D(2), D(3), D(4)} with D(1) = ({r1}, ), D(2) = ({r4}, ), D(3) = ({r5}, ), and D(4) = ( , {r2}). Applying the diagnosis D(i) for 1 i 4, i.e., considering for D(i) = (D(i) 1 , D(i) 2 ) the MCS M[br(M) \ D(i) 1 cf (D(i) 2 )], yields that the illness of the patient is ignored (D(1)), that the medication is not billed (D(2)), that the insurance receives a bill it will not pay (D(3)), and that the patient is given a medication she is allergic to (D(4)).

3. Preferences

Clearly, in general not all diagnoses of an MCS are equally appealing, as applying the selected repair might have serious consequences, e.g., in the MCS M of Example 4 if the illness of the patient is

EITER & WEINZIERL

ignored. It is not easy to identify the best diagnosis in D m(M): if the health of the patient is most important, then those diagnoses only causing a wrong billing are preferred; on the other hand, if costs matter, one might consider any diagnosis leading to a wrong billing as unacceptable. In the literature two basic ways occur frequently: one is to separately consider each outcome (i.e., diagnosis) and discard it whenever it fails some preference condition; the other is to compare outcomes with each other and decide which is the most appealing. We call the former a ﬁlter, since it ﬁlters unwanted diagnoses, and the other a preference. Both notions of diagnosis can be deﬁned in general by relying on some notion of plausibility (see e.g., for abduction Bylander et al., 1991). As for preference among diagnoses, two immediate questions are (i) how to model preference formally and (ii) how to obtain or elicit a concrete preference description for a particular MCS. Regarding (i), we aim in this work to be rather general and resort to a prototypical model in terms of a preference relation, formalized as binary relation on the set of diagnoses that is reﬂexive and transitive; this abstract notion allows us to capture a large number of formalisms that have been developed for specifying preference. Regarding (ii), there is no simple or straightforward answer, since the construction of a particular preference order may very much depend on the particular MCS and its application domain. It may appear far easier instead to obtain a preference order on individual bridge rules; since diagnoses amount to special sets of bridge rules, it is possible to construct a preference order between diagnoses from such preferences, by using techniques that lift preference on elements to sets of elements, as in the work of Brewka, Truszczy nski, and Woltran (2010), or to apply iterative improvement techniques; we refer here to the work by Brafman, Domshlak, Shimony, and Silver (2006), and Brewka et al. (2010), where also respective preference representation languages are considered. Guaranteeing that such preference is desired and preference elicitation tailored speciﬁcally for MCS, however, requires a study of its own and is beyond the scope of this article. We thus assume that preferences (or ﬁlters) over diagnoses are already given and concentrate on the computational challenges of imposing them on an MCS. To illustrate some particular formalism for preference speciﬁcation where elicitation respectively preference generation has been thoroughly studied, we consider here the widely known CP-nets (cf. Boutilier et al., 2004; Allen, 2016) in which preference is speciﬁed by statements like if bridge rules r1 and r2 are removed, then I prefer bridge rule r3 to be condition-free . Since preferences allow to compare diagnoses, but they do not allow the exclusion of diagnoses from being considered, preferences alone are not sufﬁcient. If one wants to ensure that certain diagnoses are excluded from being considered acceptable, the need for a way to ﬁlter out certain diagnoses arises. For specifying a ﬁlter, we again use the most general approach, which is a Boolean function on diagnoses. In this section we introduce the deﬁnitions of ﬁlters and preference orders in general, as well as some speciﬁc preference formalisms. The following sections then show how they can be realized in MCS in such a way that any formalism used to deﬁne the preference order or ﬁlter can be incorporated thanks to using the abstract logic of an MCS context. Furthermore, our approach preserves core properties of MCS like information hiding and allows for a decentralized evaluation.

3.1 Filters on Diagnoses

Filters allow the MCS designer to apply sanity checks on diagnoses; they act as hard constraints: diagnoses that fail to satisfy the conditions are ﬁltered out and discarded for consistency restoration.

PREFERENCE-BASED INCONSISTENCY MANAGEMENT IN MULTI-CONTEXT SYSTEMS

3.1.1 PROTECTING BRIDGE RULES

In a ﬁrst attempt, we may consider protecting some bridge rules from modiﬁcation, i.e., we disallow a diagnosis to contain them. The adapted notion of diagnosis is as follows.

Deﬁnition 7. Let M be an MCS with protected rules br P br(M). A diagnosis excluding protected rules br P is a diagnosis (D1, D2) D (M), where D1, D2 br(M) \ br P . We denote the set of all such diagnoses by D (M, br P ). The set of all minimal such diagnoses is D m(M, br P ) = {D D (M, br P ) | D D (M, br P ) : D D}.

Example 5. Consider the hospital MCS M of Example 3 again. One might decide that bridge rules for health-related information-ﬂow are protected, i.e., br P = {r1, r2}. The set of minimal protected diagnoses then is:

D m(M, br P ) = {({r4}, ), ({r5}, )}

In the following we also write diagnosis with protected bridge rules meaning a diagnosis excluding protected rules. The following property is easy to verify.

Proposition 1. Let M be an inconsistent MCS with protected rules br P . Then D (M, br P ) D (M) and D m(M, br P ) D m(M), i.e., every diagnosis is a diagnosis excluding protected rules and every minimal diagnosis excluding protected rules is a minimal diagnosis.

Proof. Let D D (M, br P ), then by deﬁnition D D (M). Given D = (D1, D2) with D D m(M, br P ), assume towards contradiction that there exists (D 1, D 2) D m(M) such that (D 1, D 2) (D1, D2). Observe that D 1, D 2 br(M)\br P , hence (D 1, D 2) D (M, br P ). This contradicts that D D m(M, br P ), thus it follows that D D m(M).

In Section 6 it is shown that deciding whether D D (M, br P ) and D D (M) have the same complexity, i.e., protected bridge rules do not increase the complexity.

3.1.2 FILTERS IN GENERAL

We now introduce ﬁlters in general. A candidate diagnosis (D1, D2) is considered whether it fails some conditions; if so, it is ﬁltered out and not considered for consistency restoration; thus a ﬁlter can be seen as hard constraints on diagnoses.

Example 6. Consider two scientists, Prof. K and Dr. J, who plan to write a paper. We formalize their reasoning in an MCS M with two contexts C1 and C2 that employ Lasp Σ for answer set semantics. Dr. J will write most of the paper and Prof. K will engage if she ﬁnds time or if Dr. J thinks the paper needs improvement (r1). Dr. J knows that involving Prof. K results in a good paper (r2 and kb1) and he will list her as an author if she participates (r3). The knowledge bases of the contexts are:

kb1 = {contribute improve.; contribute has time.}

kb2 = { good coauthored.}

The bridge rules of M are:

r1 : (1 : improve) not (2 : good).

r2 : (2 : coauthored) (1 : contribute).

r3 : (2 : name K) (1 : contribute).

EITER & WEINZIERL

Prof. K C1 Dr. J C2

Figure 2: Contexts and bridge rules of the MCS M = (C1, C2) from Example 6.

Figure 2 depicts the contexts and bridge rules of M. It appears that M is inconsistent, intuitively because the cycle through bridge rules r1 and r2 has an odd number of negations. The set of minimal diagnoses of M is: D m(M) = {({r1} , ) , ({r2} , ) , ( , {r2}) , ( , {r1})} . The ﬁrst two diagnoses break the cycle by removing a rule, the last two stabilize it.

We aim for a general notion of a ﬁlter, therefore we deﬁne a ﬁlter to be a Boolean function on candidate diagnoses.

Deﬁnition 8. Let M be an MCS with bridge rules br(M). A diagnosis ﬁlter for M is a function f:2br(M) 2br(M) {0, 1} and the set of ﬁltered diagnoses is D f (M) = {(D1, D2) D (M) | f(D1, D2) = 1}. By D m,f (M) we denote the set of all subset-minimal such diagnoses.

Given a candidate diagnosis D = (D1, D2) 2br(M) 2br(M), we also write f(D) to denote f(D1, D2). Writing the set D m,f(M) explicitly, we obtain:

D m,f(M) = D D (M) | f(D) = 1 D D (M) : D D f(D ) = 1 (3)

Example 7. Consider the MCS of Example 6 and the diagnoses D = ({r2} , ) and D = ( , {r2}), where the contribution of Prof. K is either enforced or forbidden. For both cases, the authorship information conveyed by r3 is wrong. Using a ﬁlter, we can declare diagnoses undesired if they modify r2 without modifying r3 accordingly as follows:

f(D1, D2) =

0 if r3 D1, r2 / D1 or r3 / D1, r2 D1; 0 if r3 D2, r2 / D2 or r3 / D2, r2 D2; 1 otherwise.

In particular it holds that f(D) = 0 = f(D ).

Note that ﬁlters generalize diagnoses with protected bridge rules. Indeed, let M be an MCS with protected bridge rules br P . Then we construct a ﬁlter fbr P in the following way:

fbr P (D1, D2) =

( 0 if r br P : r (D1 D2); 1 otherwise.

It is easy to see that D D (M, br P ) holds iff fbr P (D) = 1. From the deﬁnition of fbr P one can also see that diagnoses with protected bridge rules are some kind of modular ﬁlter, where each bridge rule of a diagnosis D can be checked independently of the other bridge rules. It also holds that every ﬁltered diagnosis is an ordinary diagnosis, but minimal ﬁltered diagnoses are not necessarily minimal diagnoses. Thus an analog to Proposition 1 does not hold, as shown by the following example.

PREFERENCE-BASED INCONSISTENCY MANAGEMENT IN MULTI-CONTEXT SYSTEMS

Example 8. Reconsider the MCS M and the ﬁlter f of Example 7. The set of minimal ﬁltered diagnoses is as follows: D m,f(M) = ({r1}, ), ( , {r1}), ({r2, r3}, ), ( , {r2, r3}) . While ({r2, r3}, ) is not in D m(M), it is a subset-minimal diagnosis respecting the condition expressed by the ﬁlter f. Intuitively, the latter diagnoses modify the authorship information in a consistent way and are minimal in the sense that no unnecessary modiﬁcation is applied.

One could argue whether minimal ﬁltered diagnoses should select from the set of regular minimal diagnoses only those which pass the ﬁlter, i.e., select the set {D D m(M) | f(D) = 1}. This looks appealing, but no minimal diagnosis may pass the ﬁlter while (non-minimal) diagnoses do. The resulting set of ﬁltered minimal diagnoses then is empty while there are useful diagnoses that satisfy the ﬁlter and do not incur unnecessary modiﬁcations other than to satisfy the ﬁlter condition and to make the MCS consistent. Therefore D m,f consists of the latter diagnoses, and thus seems to be more appropriate.

3.2 Preferences on Diagnoses

To compare diagnoses and select the most appealing one(s), we use preferences. In the spirit of MCS we also want this approach to be open to any kind of formalism for specifying preference. In general, preference is just a binary order relation on diagnoses. To avoid counter-intuitive results like A being preferred over B and B being preferred over C, but A not being preferred over C, we require that preferences are transitive. Since virtually every other preference formalism yields an order relation, we ﬁrst introduce the general formalization and later show how the speciﬁc formalism of CP-nets ﬁts into our approach.

Deﬁnition 9. A preference order over diagnoses for an MCS M is a transitive and reﬂexive binary relation on 2br(M) 2br(M); for D, D 2br(M) 2br(M) we say that D is preferred to D if D D .

Given a preference order , we denote by the irreﬂexive and anti-symmetric version of , i.e., D D holds iff D D and D D hold. Using a preference order , we now deﬁne what constitutes a most preferred diagnosis. The intuition is that such a diagnosis incurs a minimal set of modiﬁcations and no other diagnosis exists that is strictly more preferred. We ﬁrst introduce -preferred diagnoses, which are those diagnoses such that no other diagnosis is strictly more preferred. The most preferred diagnoses then are the subset-minimal ones from the set of -preferred diagnoses.

Deﬁnition 10. Let M be an inconsistent MCS and let D D (M). Then D is called -preferred if for all D 2br(M) 2br(M) with D D it holds that D / D (M). Furthermore, D is minimal -preferred if D is subset-minimal among all -preferred diagnoses. The set of all -preferred diagnoses is denoted by D (M) and the set of all minimal -preferred by D m, (M).

Observe that we do not require that is acyclic and by relying on we consider all diagnoses in a cycle to be equally preferred.

Example 9. Consider the hospital MCS M of Example 3 again, where bridge rules r1 and r2 transport information regarding the patient s health and bridge rules r3, r4, and r5 cover the information ﬂow for billing. If we consider it most important that the information ﬂow regarding health information is changed as little as possible, a preference order as follows might be used:

(D1, D2) (D 1, D 2) iff {r1, r2} (D1 D2) (D 1 D 2) {r1, r2}

EITER & WEINZIERL

We observe that following this deﬁnition, the following preferences (and several more) hold:

({r4, r5}, ) ({r1}, ) ({r4}, ) ({r1}, ) ({r5}, ) ({r1}, )

({r4, r5}, ) ( , {r2}) ({r4}, ) ( , {r2}) ({r5}, ) ( , {r2})

({r4}, ) ({r5}, ) ({r5}, ) ({r4}, )

Note that indeed yields cyclic preferences among those candidate diagnoses that are incomparable; in particular ({r4}, ) and ({r5}, ). We have that

D (M) = {(D1, D2) | D1, D2 {r3, r4, r5} and r4 D1 \ D2 or r5 D1 \ D2}

Note that ({r5}, ), ({r4}, ), and ({r4, r5}, ) are all in D (M). Selecting the subset-minimal diagnoses from D (M) we obtain D m, (M) = {({r5}, ), ({r4}, )}. This agrees with our intuition that a minimal set of modiﬁcations should be applied and we favor to modify bridge rules for billing information rather than modifying health-related bridge rules.

For use in the following sections, we also state the sets D (M) and D m, (M) explicitly.

D (M) = {D D (M) | D D (M) : (D D D = D D D )} (4)

D m, (M) = {D D (M) | D D (M) : D D D = D}

In Section 5 we show how preferences can be realized in general.

3.2.1 SAMPLE INSTANTIATIONS OF PREFERENCE ORDERS: CP-NETS

We now brieﬂy demonstrate how our notion of preference can capture some practical preference formalisms. Conditional preference networks (CP-nets) (Boutilier et al., 2004) are a widespread preference formalism with many appealing features. CP-nets capture a natural class of preference statements like If my new car is from Japan, I prefer hybrid over diesel engine, assuming all else is equal . We brieﬂy present the essential concepts of CP-nets in compact form to show their ﬂavor. A CP-net has a set of outcome variables where each variable ranges over some domain. In our example, we have the variables origin country and engine type with origin country including Japan and engine type including diesel and hybrid . A distinguishing feature of CP-nets is the dependency of preferences, e.g., the above preference on the engine type only upholds if the outcome of the origin country is Japan . This dependency is expressed in CP-nets as a directed graph N = (V, E) on outcome variables V . Each outcome variable v V is associated with a set dom(v) of possible outcomes. A total outcome o assigns each v V a value from dom(v), denoted by ov; for a subset V V of the variables, o V denotes the restriction of o to V (note that o = o V ). Furthermore, each variable v has an associated conditional-preference table cpt(v) which contains a total preference order over dom(v) for every possible outcome of the parent variables Pa(v) on which v depends, i.e., Pa(v) = {v | (v , v) E}. A preference order over total outcomes satisﬁes N, if for all total outcomes o, o and all variables v V it holds that o Pa(v) = o Pa(v) implies that o o holds iff ov is preferred to o v in cpt(v). Informally, satisﬁes N if it agrees with all conditional-preference tables of N; for formal details and further background see the work of Boutilier et al. (2004) and Allen (2016). Note that dependencies in CP-nets are natural to humans as CP-nets have successfully been used for preference elicitation, e.g. by Domshlak et al. (2001). CP-nets also allow one to compare total

PREFERENCE-BASED INCONSISTENCY MANAGEMENT IN MULTI-CONTEXT SYSTEMS

outcomes, so we may ask whether an outcome o is preferred to an outcome o under all preferences that satisfy N. If this is the case, then o is said to dominate o , written as N |= o o (entailment). CP-nets may be used to specify preference among diagnoses of an MCS M as follows: each bridge rule r br(M) is assigned two outcome variables V r 1 and V r 2 , where the domain of V r 1 is {in D1, not in D1} and the domain of V r 2 is {in D2, not in D2}. We call any CP-net N = (V, E) with V = {V r 1 , V r 2 | r br(M)} and domains as before fully compatible to M, or just a fully compatible CP-net. Every total outcome of such a CP-net corresponds one-to-one to a candidate diagnosis of M.

Deﬁnition 11. Given an MCS M and a CP-net N that is fully compatible to M, we say a diagnosis D D (M) is N-preferred iff there exists no D D (M) such that N |= D D holds and N |= D D does not hold. Let DN(M) denote the set of all N-preferred diagnoses of M. Then the set D ird(M, N) of irredundant N-preferred diagnoses, consists of the subset-minimal diagnoses of DN(M). Formally, D ird(M, N) = {D DN(M) | D DN(M) : D D D = D }.

Observe that given a CP-net N that is compatible to the MCS M, we can readily deﬁne a preference order N that is equivalent to N as follows: for all D, D 2br(M) 2br(M) it holds that D N D N |= D D . Since the entailment of the CP-net is transitive and reﬂexive, N

is transitive and reﬂexive, therefore N is a preference relation in the sense of Deﬁnition 9. Hence, we can use N and the notion of most preferred diagnosis to select the irredundant N-preferred diagnoses, formally:

Proposition 2. Given a CP-net N compatible to an MCS M, let D N D hold iff N |= D D

holds. Then DN(M) = D N (M) and D m, N (M) = D ird(M, N).

Deciding whether a global outcome o is preferred over o by a given CP-net N, i.e., deciding N |= o o, is no easy task in general. In the work of Goldsmith et al. (2008) it is shown that this task is PSPACE-complete. Restricting the CP-net, however, decreases the computational complexity, e.g., the same decision problem is NP-complete for binary-valued directed-path singly connected CP-nets and even in quadratic time for binary-valued tree-structured CP-nets as shown by Boutilier et al. (2004). Notice that fully-compatible CP-nets are binary-valued.

4. Meta-Reasoning for Diagnosis

To realize ﬁlters and preference orders inside an MCS, some MCS context must be able to reason on diagnoses of the MCS. We achieve this by a rewriting technique, transforming an MCS M into an extended MCS M , where certain new context(s) can do meta-reasoning on diagnoses of the original MCS M. The underlying idea here is that a diagnosis D applied to M has the same effects as if D would be applied to M, but in M there are additional contexts that observe the behavior of the bridge rules in M to reason about the observed diagnosis D. A signiﬁcant advantage of this approach is that the observation contexts may use any abstract logic for reasoning about the observed diagnoses. Thus our approach can capture a wide range of formalisms to specify preferences by ﬁlters or preference orders, and it allows the creator of an MCS to use whichever formalism she or he sees to ﬁt best. Furthermore, the rewriting is not intrusive, since it only requires that each rule is duplicated and one additional positive literal added in it. The transformation given in this section realizes ﬁlters in general by using diagnoses with protected bridge rules. Preferences also require some additional notions of diagnoses that allow to

EITER & WEINZIERL

prioritize some bridge rules. This prioritization in principle establishes a lexicographic order on candidate diagnoses. We present in fact two possible ways to realize general preferences. The ﬁrst adds exponentially many bridge rules, while the second adds only linearly many bridge rules but comes at the cost of duplicating the contexts of the original MCS. In the following section, we present a uniform encoding for meta-reasoning on diagnoses, which serves as the basis for realizing ﬁlters and preferences as well as for proving correctness.

4.1 Injecting Diagnoses

We can encode the modiﬁcations of a diagnosis directly in an MCS such that observations are perfect, which means that the original system is not just observed but actively modiﬁed. Conceptually, given an MCS M = (C1, . . . , Cn) all its bridge rules are rewritten and protected such that a diagnosis is applied only to the bridge rules of an additional context Cn+1. This context Cn+1 then is able to deﬁnitely observe the modiﬁcations and to exhibit this observation to all other contexts via its acceptable belief set. The bridge rules of the original system are rewritten to consider the belief set of Cn+1. So they either behave like being removed or like being made condition-free, depending on what Cn+1 believes. Furthermore, the deﬁnition of the observation context Cn+1 is generic and only speciﬁes some necessary properties. This provides the user with the possibility to instantiate it with a logic and a knowledge base of her choice, which is in line with the spirit of the MCS framework. To encode (observe) diagnoses, the context Cn+1 needs bridge rules to which a diagnosis can be applied and which can be observed reliably. To this end, for every r br(M) we have the following two bridge rules to encode/observe whether r is removed or made unconditional (i.e., condition-free). d1(r) : (n+1 : not removedr) . (5)

d2(r) : (n+1 : uncondr) . (6) For a set R br(M), let d1(R) = {d1(r) | r R} and d2(R) = {d2(r) | r R}. Since the meta-reasoning encoding is used as uniform foundation for ﬁlters and preferences, we introduce a property θ that describes the additional behavior of the context Cn+1. This allows us to later specify the required behavior for both ﬁlters and preferences. The preference encoding requires further bridge rules for mapping preferences to bridge rules; this set of additional bridge rules is called Kp, so we obtain an MCS Mmr(θ,Kp) as the meta-reasoning encoding of M as follows.

Deﬁnition 12. Let M = (C1, . . . , Cn) be an MCS, let Kp be a set of bridge rules such that the following holds for all r Kp: ϕ (r) / {not removedr , uncondr | r br(M)}, body(r) = { }, and Ch (r) = n+1. Furthermore, let θ be a ternary property over 2br(M) 2br(M) 2Kp. Then, the MCS Mmr(θ,Kp) = (C 1, . . . , C n, Cn+1) is a meta-reasoning encoding if the following holds:

(i) for every Ci = (Li, kbi, bri) with 1 i n it holds that C i = (Li, kbi, br i) where br i contains for every r bri of form (2) the following two bridge rules: (i : s) (c1 : p1), . . . , (cj : pj), not (cj+1 : pj+1), . . . , not (cm : pm),

not (n+1 : removedr). (7)

(i : s) (n+1 : uncondr). (8) (ii) Cn+1 = (Ln+1, kbn+1, brn+1) is an arbitrary context such that:

(a) the logic Ln+1 = (KBn+1, BSn+1, ACCn+1) is an arbitrary logic where

PREFERENCE-BASED INCONSISTENCY MANAGEMENT IN MULTI-CONTEXT SYSTEMS

KBn+1 fulﬁlls that A {uncondr, not removedr | r br(M)} {ϕ(r) | r Kp} implies that there exists a knowledge-base kb KBn+1 with A kb. BSn+1 fulﬁlls that B {removedr, uncondr | r br(M)} implies that there exists a belief set bs BSn+1 with B bs. ACCn+1 is such that some kb KBn+1 fulﬁlls the property ( ) in item (d) below.

(b) the set of bridge rules is brn+1 = d1(br(M)) d2(br(M)) Kp and the only rules with head formulas not removedr and uncondr are of form (5) and (6).

(c) the knowledge base kbn+1 KBn+1 is arbitrary but fulﬁlls the following property:

( ) for every H {ϕ (r) | r brn+1} it holds that

Sn+1 ACCn+1(kbn+1 H) iff θ(R1, R2, R3) is true

where R1 = {r br(M) | not removedr / H},

R2 = {r br(M) | uncondr H},

R3 = {r Kp | ϕ (r) H}, and

Sn+1 = {removedr | r R1} {uncondr | r R2}.

The protected bridge rules br P of Mmr(θ,Kp) are all rules of form (7) and (8).

The bridge rules of form (7) and (8) for a bridge rule r br(M) either behave like removed or like made unconditional, depending on what Cn+1 believes. The bridge rule (7) behaves like r being removed by a diagnosis if Cn+1 believes it is removed (i.e., it does not ﬁre even if the original body of r is satisﬁed). The bridge rule (8) behaves like r being made condition-free by a diagnosis if Cn+1 believes it is condition-free (i.e., it ﬁres regardless of whether the original body of r is satisﬁed). The property ( ) guarantees that (i) the beliefs of Cn+1 coincide with the diagnosis encoded by bridge bridge rules of form (5) and (6), and (ii) that there is an acceptable belief set whenever θ holds. This deﬁnition of Mmr(θ,Kp) is thus generic and the Propositions 3-5 below are very general. The advantage of this approach is that we have a common foundation for encoding ﬁlters and preferences, such that several propositions hold for both encodings. Furthermore, as shown later in detail, the property θ to realize a ﬁlter f amounts to simply stating that θ(D1, D2, ) holds iff f(D1, D2) = 1, while θ and Kp sufﬁce to capture preferences. The context Cn+1 is similar to an interface in programming, which deﬁnes certain properties but is open to an arbitrary implementation. A concrete realization of Cn+1 using the logic Lasp Σ for Answer-Set Programming is illustrated in Example 19 in Appendix B. Speciﬁcally, there the rules (22) (34) implement the interface .

Example 10. Recall the MCS M = (C1, C2) of Example 6. Let Kp = and θ(D1, D2, ) always hold. Then the meta-reasoning encoding Mmr(θ,Kp) = (C 1, C 2, C3) is such that the contexts C1, C2, equal modulo bridge rules the contexts C 1, C 2, respectively. Recall that the bridge rules of M are:

r1 : (1 : improve) not (2 : good).

r2 : (2 : coauthored) (1 : contribute).

r3 : (2 : name K) (1 : contribute).

EITER & WEINZIERL

Prof. K C1 Dr. J C2

Observer/Encoder C3

Figure 3: Contexts of the meta-reasoning encoding Mmr(θ,Kp) = (C1, C2, C3) from Example 10. Only bridge rules r 1, r 1, d1(r1), d2(r1) of Mmr(θ,Kp) that stem from bridge rule r1 br(M) are shown.

The bridge rules of Mmr(θ,Kp) are then as follows:

r 1 : (1 : improve) not (2 : good), not (3 : removedr1).

r 1 : (1 : improve) (3 : uncondr1).

r 2 (2 : coauthored) (1 : contribute), not (3 : removedr2).

r 2 (2 : coauthored) (3 : uncondr2).

r 3 (2 : name K) (1 : contribute), not (3 : removedr3).

r 3 (2 : name K) (3 : uncondr3).

d1(ri) : (3 : not removedri) . i {1, 2, 3}

d2(ri) : (3 : uncondri) . i {1, 2, 3}

Notice that only the last six bridge rules of Mmr(θ,Kp) are not protected, i.e., the ﬁrst six bridge rules are guaranteed not to be modiﬁed in a diagnosis with protected bridge rules. Figure 3 depicts the contexts and, for better visibility, only those bridge rules of Mmr(θ,Kp) that stem from r1 br(M) are shown.

Note that the observation context of a meta-reasoning encoding only knows that some bridge rules exist but it has no knowledge of the actual information exchange or the contents of any of the other contexts. Since the meta-reasoning encoding is the basis for all later encodings, it provides us with a mechanism to determine preferred solutions for both preference orders and ﬁlters that maintains privacy and information hiding of the contexts. For ﬁlters that are not inherently centralized, the realization even allows for ﬁnding preferred solutions in a decentralized, localized manner (cf. Section 7.1 on decomposing the central observation contexts). Thus we mostly preserve key properties of MCS also for inconsistency assessment and selection of preferred diagnoses. Def. 12 forbids the observation context Cn+1 to exhibit any belief not of the form removedr or uncondr for r br(M). In practice however, auxiliary beliefs are useful when realizing a preference or ﬁlter. Since the applicability of bridge rules does not depend on beliefs that do not occur in any bridge rule, this restriction can be lifted to allow for auxiliary beliefs in Cn+1.

PREFERENCE-BASED INCONSISTENCY MANAGEMENT IN MULTI-CONTEXT SYSTEMS

In the remainder of this section, we show some properties of Mmr(θ,Kp), which are the basis for proving the correctness of the subsequent realizations of ﬁlters and preferences. First, there is a one-to-one correspondence between diagnoses of M and diagnoses of Mmr(θ,Kp).

Proposition 3. Let M be an MCS and Mmr(θ,Kp) be a meta-reasoning encoding with protected bridge rules br P , and let D1, D2 br(M), K Kp. Then,

(1) let S = (S1, . . . , Sn) be a belief state of M and let S = (S1, . . . , Sn, Sn+1) where Sn+1 = {removedr | r D1} {uncondr | r D2}. Then, S EQ(M[D1, D2]) and θ(D1, D2, K) holds if and only if S EQ(Mmr(θ,Kp)[d1(D1), d2(D2) K]) holds.

(2) (d1(D1), d2(D2) K) D (Mmr(θ,Kp), br P ) holds if and only if (D1, D2) D (M) and θ(D1, D2, K) hold.

From this, the following correspondence between minimal θ-satisfying diagnoses of M and minimal diagnoses of Mmr(θ,Kp) holds.

Proposition 4. Let Mmr(θ,Kp) be a meta-reasoning encoding of an MCS M. Then the set of minimal θ-satisfying diagnoses with protected bridge rules br P of Mmr(θ,Kp) is

D m(Mmr(θ,Kp), br P ) = (d1(D1), d2(D2) K) | (D1, D2) D (M) and θ(D1, D2, K) holds

and there exist no (D 1, D 2) D (M), K Kp such that

(D 1, D 2 K ) (D1, D2 K) and θ(D 1, D 2, K ) holds . This result can be strengthened given that θ obeys some property. We say that θ is functional (or a function), if for every D1, D2 br(M) there exists at most one K Kp such that θ(D1, D2, K) holds. We say that θ is functional increasing if K K holds whenever θ is functional, θ(D1, D2, K), θ(D 1, D 2, K ), and (D1, D2) (D 1, D 2), where D1, D2, D 1, D 2 br(M), K, K Kp.

Proposition 5. Let Mmr(θ,Kp) be a meta-reasoning encoding of an MCS M such that θ is functional increasing. Then, the set of minimal θ-satisfying diagnoses with protected bridge rules br P of Mmr(θ,Kp) is

D m(Mmr(θ,Kp), br P ) = (d1(D1), d2(D2) K) | (D1, D2) D (M) and θ(D1, D2, K) holds

and there exists no (D 1, D 2) D (M) such that

(D 1, D 2) (D1, D2) and θ(D 1, D 2, K ) holds for some K, K Kp .

Given these relationships between diagnoses of M and Mmr(θ,Kp) with respect to property θ, we show in the next section several ways how Mmr(θ,Kp) can be used to realize preferences.

5. Preference Realization

In the previous section we introduced a transformation that enables meta-reasoning on diagnoses. In this section, we ﬁrst present how ﬁlters can be realized and then proceed to preferences, where we ﬁrst introduce a plain encoding using exponentially many bridge rules to realize total preference orders and then introduce an encoding that allows to realize arbitrary preference orders at the expense of cloning the contexts of the original MCS.

EITER & WEINZIERL

5.1 Filter Encoding

We use the meta-reasoning encoding to realize ﬁlters, by simply requiring that the observation context becomes inconsistent if the observed diagnosis does not pass the ﬁlter, i.e., we use Mmr(θ,Kp)

where K = and θ is such that θ(D1, D2, K) holds if and only if f(D1, D2) = 1. Since no further bridge rules are needed to realize ﬁltered diagnoses, it is sufﬁcient to pick Kp = .

Deﬁnition 13. Let M be an MCS and let f be a ﬁlter. Let Kp = and let θ(D1, D2, ) hold iff f(D1, D2) = 1. Then Mmr(θ,Kp) is the ﬁlter-encoding of M wrt. f, which we also denote by Mf.

Example 11. Reconsider the MCS M = (C1, C2) of Example 7 where two scientists write a paper and diagnoses are to be ﬁltered by a ﬁlter f if the authorship information is modiﬁed by a diagnosis in an incoherent way. The ﬁlter f (see Example 7) is deﬁned as follows:

f(D1, D2) =

0 if r3 D1, r2 / D1 or r3 / D1, r2 D1 0 if r3 D2, r2 / D2 or r3 / D2, r2 D2 1 otherwise

The resulting ﬁlter encoding Mf is the MCS Mmr(θ,Kp) = (C 1, C 2, C3), which has the same contexts and bridge rules as the MCS of Example 10. It only differs in the contents of the observation/encoding context C3 which now realizes the ﬁlter f. We use ASP again for the logic of C3 = (Lasp Σ , kb3, br3). Recall that the knowledge-base formulas added by bridge rules to C3 are either of the form uncondr or not removedr and this information has to be exposed accordingly in the accepted belief set. Also remember that the deﬁnition of the meta-reasoning encoding requires that every accepted belief set only consists of beliefs in {removedr, uncondr | r br(M)}, but since no other bridge rule of Mmr(θ,Kp) uses any other belief, we may allow further beliefs in the accepted belief set, i.e., our ASP program may use additional atoms. The knowledge base kb3 of C3 then is:

kb3 = { removedr1 not not removedr1. removedr3, not removedr2.

removedr2 not not removedr2. not removedr3, removedr2.

removedr3 not not removedr3. uncondr3, not uncondr2.

not uncondr3, uncondr2. }

The ﬁrst three rules of kb3 ensure that the removal information is correct while nothing is needed to ensure that the information about condition-free bridge rules is exposed (if bridge rule ri is made unconditional, then the fact uncondri is added to kb3 by the bridge rule d2(ri) br3(Mmr(θ,Kp)) being applicable and hence uncondri is also present in the answer set and thus in the belief set of C3. The four constraints of kb3 ﬁnally encode the ﬁlter condition and they ensure that the context has no acceptable belief set if the corresponding diagnoses are applied.

Observe that the deﬁnition of θ uses the notion of f, which is an abstraction / generalization of some desired actual behavior. Instead of f, it is possible to use the desired actual behavior directly to realize the context Cn+1 of Mmr(θ,Kp), i.e., for a concrete use case where some logic is used to describe which diagnoses should be ﬁltered out, it is not really necessary to ﬁrst abstract the concrete

PREFERENCE-BASED INCONSISTENCY MANAGEMENT IN MULTI-CONTEXT SYSTEMS

case to a ﬁlter f, build θ accordingly and then derive a concrete instantiation of Cn+1. Rather it is sufﬁcient to take the deﬁnition of the meta-reasoning encoding and interpret it as the deﬁnition of the interfacing between the logic that does the ﬁltering and the rest of the MCS framework. The reason why we introduced ﬁlters in general lies in the fact that this allows us to prove that all such ﬁlterings can be realized correctly. The following theorem now shows that diagnoses with protected bridge rules of Mf indeed correspond one-to-one to ﬁltered diagnoses of M.

Theorem 1. Let M be an MCS, let f be a ﬁlter and let Mf be the corresponding ﬁlter-encoding. Then, D m,f(M) = {(D1, D2) | (d1(D1), d2(D2)) D m(Mf, br P )}.

To obtain all minimal-ﬁltered diagnoses of an MCS M wrt. the ﬁlter f, it is therefore sufﬁcient to compute all subset-minimal diagnoses (with protected bridge rules) of the MCS Mf = Mmr(θ,Kp). Note that this encoding does not come with increased computational cost, since M and Mf have the same number of bridge rules that possibly occur in a diagnosis with protected bridge rules. Consider Mf and the respective bridge rules, i.e., the set br(Mf) \ br P = d1(br(M)) d2(br(M)): since body(r) = { } for r d1(br(M)) and body(r) = { } for r d2(br(M)), it holds for every (R1, R2) D m(Mf, br P ) that r R1 implies r d1(br(M)) and r R2 implies r d2(br(M)) (this follows from Lemma 8 in Appendix A.2). Hence, there are 2|d1(br(M))| 2|d2(br(M))| possibly relevant diagnoses for Mf while there are 2|br(M)| 2|br(M)| possible diagnoses for M; since |d1(br(M))| = |d2(br(M))| = |br(M)|, the candidate space, i.e., the number of candidate diagnoses, for deciding whether a minimal-ﬁltered diagnosis exists for M has the same size as the candidate space for deciding whether a minimal diagnosis with protected bridge rules exists for Mf.

5.2 Plain-Preference Encoding

We now show how to use the meta-reasoning encoding Mmr(θ,Kp) for realizing preference orders. The set Kp plays a crucial role, since it is used to map a given preference order on diagnoses to the relation on Kp. This allows us to select minimal -preferred diagnoses by considering -minimal diagnoses of Mmr(θ,Kp). Since the -minimality on Kp should take precedence over the remaining modiﬁed bridge rules of Mmr(θ,Kp), we introduce a lexicographic order on bridge rules in which the latter are after those of Kp. As we show in Section 6, the complexity of identifying a diagnosis with respect to prioritized bridge rules Kp is not higher than identifying a minimal diagnosis. In the following, we present a plain and simple encoding, which comes at the cost of Kp being exponentially larger than br(M), i.e., Mmr(θ,Kp) contains exponentially many more bridge rules than M. We also prove that the approach is correct for total preference orders. Before presenting the plain encoding, ﬁrst we introduce the notion of a prioritized-minimal diagnosis, and second we show how a total order can be mapped to the relation. In the following, we write (D1, D2) br H (D 1, D 2) as shorthand for (D1 br H, D2 br H) (D 1 br H, D 2 br H), i.e., we denote by br H the restriction of to the set br H; furthermore, we write =br H for an analogous restriction on =. To realize a total preference order, the following deﬁnition is sufﬁcient where we select from the set of minimal diagnoses with protected bridge rules those that are minimal with respect to the prioritized bridge rules. The bridge rules that are marked as prioritized take precedence for minimality. A prioritized-minimal diagnosis is subset-minimal with respect to prioritized bridge rules (regardless of minimality of the remaining bridge rules).

EITER & WEINZIERL

Deﬁnition 14. Let M be an MCS with bridge rules br(M), protected rules br P br(M), and prioritized rules br H br(M). The set of prioritized-minimal diagnoses is D (M, br P , br H) = D D m(M, br P ) D D m(M, br P ) : D br H D D =br H D .

We now show how an arbitrary order relation over a pair of sets may be mapped to the - relation on an exponentially larger set, i.e., we map on the diagnoses of an MCS M, to another exponentially larger set.

Deﬁnition 15. Let be a preference relation on 2br(M) 2br(M) and let g : 2br(M) 2br(M) Kp be a bijective mapping where Kp is arbitrary. Then, the subset-mapping mapg : 2br(M) 2br(M) 2Kp is deﬁned as follows. For every (D1, D2) 2br(M) 2br(M):

mapg (D1, D2) = K Kp | K=g(D 1, D 2) for some (D 1, D 2) (D1, D2) .

Observe that mapg (D1, D2) collects g(D 1, D 2) of all (D 1, D 2) below (D1, D2). The following lemma shows that the subset-mapping correctly maps a preference relation on diagnoses to the subset-relation on an exponentially larger set. This allows to decide whether a diagnosis is more preferred than another solely based on subset relationship.

Lemma 1. Let be a preference on candidate diagnoses of an MCS M, and let g be a bijective mapping g : 2br(M) 2br(M) Kp for any set Kp. Then, for any (D1, D2), (D 1, D 2) 2br(M) 2br(M) it holds that (D1, D2) (D 1, D 2) iff mapg (D1, D2) mapg (D 1, D 2).

We now use mapg to map the preference of a total order to the set Kp which occurs in the meta-reasoning transformation Mmr(θ,Kp). To that end, we choose θ(D1, D2, K) such that it holds iff mapg (D1, D2) = K, for K Kp. By that, every diagnosis of Mmr(θ,Kp) with protected bridge rules (d1(D1), d2(D2) K) contains the preference encoded in K. Selecting a diagnosis of Mmr(θ,Kp) where K is minimal then selects a preferred diagnosis according to .

Deﬁnition 16. Let M be an MCS and let be a preference order over diagnoses of M. Furthermore, let Kp = {(n+1 : diag D1,D2) . | D1, D2 br(M)} (9)

and let g : 2br(M) 2br(M) Kp be a bijective function such that g(D1, D2) = (n+1 : diag D1,D2) . for all D1, D2 br(M). Let θ(D1, D2, K) hold iff mapg (D1, D2) = K. Then the MCS Mmr(θ,Kp) is called the plain encoding of M wrt. , which we also denote by Mpl ; all bridge rules of Kp are prioritized, i.e., br H = Kp.

Note that since mapg is a function, also θ is equivalent to a function 2br(M) 2br(M) Kp.

Example 12. We consider the hospital MCS M of Example 3 again using a preference order on diagnoses similar to the one of Example 9, i.e., we prefer changing bridge rules regarding health, r1, r2, as little as possible. To make the preference total, we use cardinality-minimality, i.e.,

(D1, D2) (D 1, D 2) iff {r1, r2} (D1 D2) (D 1 D 2) {r1, r2} .

The resulting MCS Mmr(θ,Kp) is outlined in Figure 4, where only bridge rules stemming from r5 of br(M) and some of the bridge rules of the observation context C4 are indicated. Note that br4(Mmr(θ,Kp)) contains for every possible diagnosis of M a distinguished bridge rule. For C4 = (Lasp Σ , kb4, br4), we use ASP again to show a possible realization; kb4 consists of the rules:

PREFERENCE-BASED INCONSISTENCY MANAGEMENT IN MULTI-CONTEXT SYSTEMS

Patient data C1 Medication C2

Observer/Encoder C4

r2 r3 r4 r 5

d2(r5) diag , diag{r1}, diag{r1,r2},

diagbr(M),br(M)

Figure 4: Contexts and some bridge rules of the plain encoding Mpl = (C1, C2, C3, C4) of the hospital MCS wrt. from Example 12. For illustration purposes, only bridge rules stemming from r5 and some from Kp are shown; dashed lines indicate bridge rules r1, . . . , r4 from M whose corresponding bridge rules in Mpl are not shown.

removedr not not removedr. r br(M) cur diag D1,D2, not diag D1,D2. D1, D2 br(M), cur diag D 1,D 2 cur diag D1,D2. (D 1, D 2) (D1, D2), cur diag D1,D2 removedr1, . . . , removedrk, uncondr 1, . . . , uncondr m. D1, D2 br(M), D1 = {r1, . . . , rk}, D2 = {r 1, . . . , r m}.

Intuitively, the rules of the ﬁrst line ensure that diagnosis observation is exposed correctly in an accepted belief set of C4; the constraints following ensure the presence of condition-free bridge rules. Rules of the third line guarantee that all bridge rules corresponding to more-preferred diagnoses also need to be condition-free; under ASP semantics, these rules effect mapg (D1, D2). Finally, the rules of the last line recognize one of the exponentially many candidate diagnoses.

The next theorem shows the relation between minimal -preferred diagnoses of M wrt. a total preference and prioritized-minimal diagnoses of Mpl . Observe that mapg is injective since is reﬂexive, thus mapg (D1, D2) contains g(D1, D2), which by g being a bijection is different for every candidate diagnosis (D1, D2). Therefore, mapg is bijective on its range and it allows to establish a one-to-one relation between minimal -preferred diagnoses of M and prioritizedminimal ones of Mpl . Intuitively, this shows that for a total preference order, the set of prioritizedminimal diagnoses of the plain encoding of M wrt. can be used to select the minimal -preferred diagnoses of M.

EITER & WEINZIERL

Theorem 2. For every MCS M and total preference on its diagnoses, D (Mpl , br P , br H) = {(d1(D1), d2(D2) K) | (D1, D2) D m, (M), mapg (D1, D2) = K}.

To select minimal -preferred diagnoses based on an arbitrary preference order, another encoding can be utilized, which we describe next.

5.3 Clone-Preference Encoding

The clone encoding requires that the original MCS M is cloned, but comes at the advantage of only requiring linearly many bridge rules, speciﬁcally it holds that |Kp| = 4|br(M)| + 1. First an MCS 2M is built that consists of two independent copies of M, and then the meta-reasoning encoding is applied on 2M, i.e., the resulting MCS is (2M)mr(θ,Kp). We show that the minimal -preferred diagnoses can be selected from (2M)mr(θ,Kp) using a slightly more involved diagnosis notion with prioritized bridge rules. The complexity of selecting such diagnoses increases, but it is still worst-case optimal as shown later. The basic idea of the clone encoding is that the original MCS is duplicated such that the observation context sees two diagnoses of the original MCS at the same time and is able to compare them. Intuitively, if we combine two MCS M and M into a single one M , then every diagnosis of the combined MCS M is the combination of a diagnosis of M with a diagnosis of M . Establishing this technically requires some care, since one needs to account for the fact that contexts are identiﬁed by their position: Hence, M cannot simply contain the bridge rules of M and M . We thus introduce context shifting and build an operator to combine two MCS. We then show some general properties of the operator, and ﬁnally give the clone encoding, which adds a certain observation context to the combination M M of the MCS M whose minimal -preferred diagnoses we are interested in. For shifting contexts, we use a permutation I : N N, i.e., I is a bijective mapping. Given a bridge rule r of form (2), then I(r) is the bridge rule

(I(k) : s) (I(c1) : p1), . . . , (I(cj) : pj), not (I(cj+1) : pj+1), . . . , not (I(cm) : pm);

furthermore, for a set R of bridge rules we have I(R) = {I(r) | r R} and for a context Ci = (Li, kbi, bri) we have I(Ci) = (Li, kbi, I(bri)). Given an MCS M = (C1, . . . , Cn), a permutation I is compatible with M if I(x) n holds for all x n, i.e., I is a permutation on C (M); the shufﬂed version of M wrt. a compatible I then is I(M) = (I(CI 1(1)), . . . , I(CI 1(n))). Given a belief state S = (S1, . . . , Sn) we have I(S) = (SI 1(1), . . . , SI 1(n)). To combine two existing MCS M = (C1, . . . , Cn) and M = (C 1, . . . , C m) into a new one, we use the following operator:

M M = (C1, . . . , Cn, I(C 1), . . . , I(C m)) where I(x) =

n + x for 1 x m, x m for m + 1 x n + m, x otherwise.

In the following, we call I the permutation wrt. M M . Note that by construction the permutation I wrt. M M is compatible with M M . Recall that M[R1, R2] = M[br(M) \ R1 cf (R2)]. Regarding modiﬁcations and candidate diagnoses, we then observe that M[A1, A2] M [B1, B2] = (M M )[A1 I(B1), A2 I(B2)] where I is the mapping wrt. M M . The following lemma shows that shifting has no inﬂuence on acceptability.

PREFERENCE-BASED INCONSISTENCY MANAGEMENT IN MULTI-CONTEXT SYSTEMS

Lemma 2. Given an MCS M = (C1, . . . , Cn) and a compatible permutation I, it holds that S EQ(M) iff I(S) EQ(I(M)).

It immediately follows that S EQ(M[D1, D2]) iff I(S) EQ(I(M[D1, D2])) for any candidate diagnosis (D1, D2). The main observation on the operator is that M M admits exactly those diagnoses which are a combination of a diagnosis of M and a diagnosis of M .

Proposition 6. Given two MCS M and M , then D (M M ) = {(A1 I(B1), A2 I(B2)) | (A1, A2) D (M), (B1, B2) D (M )} where I is the permutation wrt. M M .

Next we deﬁne for an MCS M = (C1, . . . , Cn) the MCS 2M = (C1, . . . , C2n) as 2M = M M, i.e., 2M consists of two clones of M. For easier reference, we write 2.r to denote the clone of the bridge rule r, i.e., 2.r = I(r) where I is the permutation wrt. M M. Note that 2.br(M) is the set of bridge rules of M shifted by n, i.e., 2.br(M) is the set of bridge rules of the second clone of M. The next lemma, which follows from Proposition 6, shows that diagnoses of 2M correspond to diagnoses of M in such a way that every diagnosis of 2M is composed of two diagnoses of M.

Lemma 3. Let M be an MCS. Then (D1, D2) D (2M) holds iff there exist (D 1, D 2) D (M) and (D 1, D 2) D (M) such that D1 = D 1 2.D 1 and D2 = D 2 2.D 2.

The underlying idea of the encoding is that a speciﬁc prioritized bridge rule tmax indicates whether the diagnosis applied to the second clone is preferred over the diagnosis applied to the ﬁrst clone. Additionally, the diagnosis of the ﬁrst clone is exhibited via prioritized bridge rules, while the diagnosis of the second clone is only exhibited via non-prioritized bridge rules. If the diagnosis applied to the second clone is more preferred than the one applied to the ﬁrst, then tmax needs not become condition-free. Thus, if for a given diagnosis of the ﬁrst clone, there exists some more preferred diagnosis of the second clone, then there exists a diagnosis where tmax is not included. A diagnosis D such that no more preferred diagnosis D exists is maximal wrt. the inclusion of tmax, because there exists no more preferred diagnosis D of M that could occur at the second clone. Selecting a diagnosis that modiﬁes a minimal set of prioritized bridge rules and that contains tmax thus selects a -preferred diagnosis. We deﬁne tmax as follows:

tmax : (2n+1 : ismax) .

To represent the diagnosis of the ﬁrst clone, we use the following prioritized bridge rules. For a bridge rule r br(M) let in1(r), in1(r), in2(r), and in2(r) denote the following bridge rules:

in1(r) : (2n+1 : in1(r)) . in2(r) : (2n+1 : in2(r)) .

in1(r) : (2n+1 : in1(r)) . in2(r) : (2n+1 : in2(r)) .

We identify a candidate diagnosis (D1, D2) 2br(M) 2br(M) using these bridge rules by the set K(D1, D2) = {in1(r) | r D1} {in1(r) | r / D1} {in2(r) | r D2} {in2(r) | r / D2}. The clone encoding then formally is as follows.

EITER & WEINZIERL

Deﬁnition 17. Let M = (C1, . . . , Cn) be an MCS and a preference order. The clone encoding of M wrt. is the MCS 2Mmr(θ,Kp) where 2M = (C1, . . . , C2n) = M M,

(2n+1 : q) ., | q {in1(r), in1(r), in2(r), in2(r)} {tmax}

and for any R1, R2 br(2M), and R3 Kp, θ(R1, R2, R3) holds iff R1 = D1 2.D 1, R2 = D2 2.D 2 and either

(D1, D2) = (D 1, D 2) and R3 = K(D1, D2) {tmax} or

(D 1, D 2) (D1, D2) and R3 = K(D1, D2).

The protected bridge rules br P are all bridge rules except those of context C2n+1; the prioritized bridge rules are br H = Kp. We denote the clone encoding of M wrt. by M = 2Mmr(θ,Kp).

Note that the second case above with (D 1, D 2) (D1, D2) implies that (D1, D2), (D 1, D 2) are two diagnoses of M, because the MCS 2M only admits a diagnosis if (D1, D2) D (M) and (D 1, D 2) D (M) both hold (cf. Lemma 3). Also observe that M = (2M)mr(θ,Kp) = (M M)mr(θ,Kp) is linear in the size of M, as for every bridge rule in M there exist 2 4+4 bridge rules in M , (the factor 2 is from M M, the factor 4 is from the meta-reasoning encoding itself and the +4 is due to Kp). In total |br(M )| = 12 |br(M)| + 1, where the +1 is due to tmax.

Example 13. Reconsider the MCS M from Example 3 shown in Figure 1. Applying the clone encoding on M wrt. a preference order results in the MCS M = (C1, C2, C3, C4, C5, C6, C7) depicted in Figure 5. It is based on two clones of M, where the ﬁrst comprises the contexts C1, C2, C3 and the second the contexts C4, C5, C6. The context C7 ﬁnally is the observation/encoding context. For each bridge rule r br(M) and each clone of M, there are two bridge rules simulating that r is removed respectively made condition-free in the clone. Hence the bridge rules in M for the contexts C1, . . . , C6 are:

r 1 : (2 : hyperglycemia) (1 : hyperglycemia), not (7 : removedr1).

r 1 : (2 : hyperglycemia) (7 : uncondr1).

r 2 : (2 : allow animal insulin) not (1 : allergic animal insulin), not (7 : removedr2).

r 2 : (2 : allow animal insulin) (7 : uncondr2).

r 3 : (3 : bill animal insulin) (2 : give animal insulin), not (7 : removedr3).

r 3 : (3 : bill animal insulin) (7 : uncondr3).

r 4 : (3 : bill human insulin) (2 : give human insulin), not (7 : removedr4).

r 4 : (3 : bill human insulin) (7 : uncondr4).

r 5 : (3 : insurance B) (1 : insurance B), not (7 : removedr5).

r 5 : (3 : insurance B) (7 : uncondr5).

I(r1) : (5 : hyperglycemia) (4 : hyperglycemia), not (7 : removedr1).

I(r1) : (5 : hyperglycemia) (7 : uncondr1).

I(r2) : (5 : allow animal insulin) not (4 : allergic animal insulin), not (7 : removedr2).

I(r2) : (5 : allow animal insulin) (7 : uncondr2).

PREFERENCE-BASED INCONSISTENCY MANAGEMENT IN MULTI-CONTEXT SYSTEMS

I(r3) : (6 : bill animal insulin) (5 : give animal insulin), not (7 : removedr3).

I(r3) : (6 : bill animal insulin) (7 : uncondr3).

I(r4) : (6 : bill human insulin) (5 : give human insulin), not (7 : removedr4).

I(r4) : (6 : bill human insulin) (7 : uncondr4).

I(r5) : (6 : insurance B) (4 : insurance B), not (7 : removedr5).

I(r5) : (6 : insurance B) (7 : uncondr5).

For each bridge rule r above there are two (non-protected) bridge rules at the observation context C7 indicating whether r is regarded as removed respectively condition-free. Overall, the set of bridge rules of C7 is: (7 : ismax) . (7 : not removedr1) . (7 : uncondr1) .

(7 : not removedr2) . (7 : uncondr2) .

(7 : not removed I(r4)) . (7 : uncond I(r4)) .

(7 : not removed I(r5)) . (7 : uncond I(r5)) .

(7 : in1(r1)) . (7 : in1(r1)) .

(7 : in2(r1)) . (7 : in2(r1)) .

(7 : in1(r5)) . (7 : in1(r5)) .

(7 : in2(r5)) . (7 : in2(r5)) .

The bridge rules of Kp are now all rules among them with head formula ini(r) or ini(r) for i {1, 2} and r br(M), plus the bridge rule tmax. These bridge rules are the prioritized ones i.e., br H = Kp. A detailed description for a concrete preference order is given in Appendix B (Example 19).

For selecting minimal -preferred diagnoses based on an arbitrary preference order, Deﬁnition 14 is strengthened in two steps: ﬁrst, if two diagnoses are equal considering their prioritized bridge rules, then subset-minimality on the remaining bridge rules is taken into account. Second, since we only want to select diagnoses where no more preferred ones exist, we consider only prioritized-minimal diagnoses that contain the bridge rule tmax. For the ﬁrst step, let M be an MCS with bridge rules br(M), protected rules br P , and prioritized rules br H br(M). The set of subset-minimal prioritized-minimal diagnoses then is:

D m(M, br P , br H) = D D m(M, br P ) | Minbr H,br P (M, D) D D m(M, br P ) :

Minbr H,br P (M, D ) D br(M)\br H D D =br(M)\br H D (10)

where Minbr H,br P (M, X) denotes that X is minimal among all protected diagnoses with respect to br H, i.e., Minbr H,br P (M, X) = D D m(M, br P ) : D br H X X =br H D. The ﬁrst condition ensures that a diagnosis D is prioritized-minimal and for all other prioritized-minimal diagnoses D it holds that D is minimal wrt. non-prioritized bridge rules. For the second step, we just add to D m(M, br P , br H) the condition that D and D make tmax condition-free. Formally:

EITER & WEINZIERL

Patient data C1 Medication C2

Observer/Encoder C7

Patient data C4 Medication C5

I(r3) I(r4)

d1(r5) d2(r5) d1(I(r5)) d2(I(r5))

Figure 5: The MCS M = (C1, C2, . . . , C7) of Example 13. Some bridge rules of the observation context C7 are shown and the bridge rules stemming from r5; dashed and gray lines indicate the other bridge rules of M M whose resulting bridge rules in M are omitted. The prioritized bridge rules of M are tmax and all bridge rules ini(rj) and ini(rj).

Deﬁnition 18. Given an MCS M with protected bridge rules br P and prioritized bridge rules br H, the set of subset-minimal prioritized-minimal (mpm) diagnoses wrt. tmax is

D m,tmax (M, br P , br H) = D D m(M, br P ) | Minbr H,br P (M, D) tmax D

D D m(M, br P ) : (Minbr H,br P (M, D ) tmax D )

D br(M)\br H D D =br(M)\br H D

where tmax D stands for D = (D1, D2) tmax D2 and Minbr H,br P (M, X) is as above.

Intuitively, D is an mpm-diagnosis, if it respects protected bridge rules and contains tmax, if it is preferred, i.e., it is minimal wrt. prioritized bridge rules br H among all other diagnoses of the MCS M, and if for all other preferred diagnoses that contain tmax it holds that D is subset-minimal wrt. regular bridge rules.

Example 14. Consider again the clone encoding M of Example 13 with a preference order on the diagnoses of the MCS M that prefers changing bridge rules regarding health, i.e., r1, r2, as little

PREFERENCE-BASED INCONSISTENCY MANAGEMENT IN MULTI-CONTEXT SYSTEMS

as possible. Formally, let (D1, D2) (D 1, D 2) hold iff {r1, r2} (D1 D2) (D 1 D 2) {r1, r2}. We illustrate the notion of mpm-diagnosis by examining three candidate diagnoses of M . (1) Consider a diagnosis on M corresponding to the diagnosis (D1, D2) = ({r4}, ) on M, viz. the diagnosis Dp = {d1(r4), d1(I(r4))}, K({r4}, ) {tmax} . Then Dp is an mpmdiagnosis of M , because (i) it contains no protected bridge rules; (ii) θ holds according to the conditions of the clone encoding, speciﬁcally for R1 = D1 2.D1, R2 = D2 2.D2 and R3 = K(D1, D2) {tmax}, hence Dp D m(M , br P ); (iii) Dp is minimal among diagnoses respecting prioritized bridge rules; and (iv) no other such diagnosis is a subset of Dp on non-prioritized bridge rules. (2) The diagnosis Do = {d1(r4), d1(r5), d1(I(r4)), d1(I(r5)}, K({r4, r5}, ) {tmax} contains no protected bridge rules and θ holds as deﬁned by the clone encoding. Furthermore, Do is minimal among the diagnoses that respect prioritized bridge rules, since the encoding ensures that K({r4}, ) and K({r4, r5}, ) are incomparable, because in1(r5) K({r4}, ) \ K({r4, r5}, ) while in1(r5) K({r4}, ) \ K({r4, r5}, ). However, Do is not an mpm-diagnosis, because Dp

is minimal with respect to prioritized rules and is smaller on the non-prioritized rules than Do, i.e., {d1(r4), d1(I(r4))} {d1(r4), d1(r5), d1(I(r4)), d1(I(r5)}. (3) Consider a diagnosis Dn stemming from the diagnosis ({r1}, ), which is not preferred according to , i.e., it holds that ({r4}, ) ({r1}, ). Let Dn = {d1(r1), d1(I(r1))}, K({r1}, ) {tmax} . Then, Dn is not an mpm-diagnosis, because it is not minimal among diagnoses respecting prioritized bridge rules. Consider the diagnosis where the diagnosis ({r4}, ) is applied to the second clone of M, i.e., Ds = {d1(r1), d1(I(r4)), K({r1}, ) . Observe that θ holds for Ds according to Deﬁnition 17, because ({r4}, ) ({r1}, ) and R3 = K({r1}, ). It also holds that Ds br H Dn, because K({r1}, ) K({r1}, ) {tmax} and therefore Minbr H,br P (M , Dn) does not hold. Consequently, Dn is not an mpm-diagnosis.

As we show in the next section, the notion of mpm-diagnosis is computationally harder than the notion of prioritized-minimal diagnosis. Nevertheless, the problem itself (i.e., identifying a minimal -preferred diagnosis) is shown to be as hard as this notion, which means the notion of mpm-diagnosis is worst-case optimal. Note that D, D D (M, br P ) implies that D br(M)\br H D holds iff D br(M)\br H\br P D

holds, because D = (D1, D2) D (M, br P ) implies that D1 br P = = D2 br P . The same also holds for =br(M)\br H and =br(M)\br H\br P . As it appears, D (M , br P , br H) sufﬁces to obtain those diagnoses of M that are -preferred. In the following, we write t(D1, D2) as a shorthand for the corresponding candidate diagnosis in the MCS M , i.e., t(D1, D2) = (d1(D1 2.D1), d2(D2 2.D2) K(D1, D2) {tmax}).

Theorem 3. Let M be an MCS and let be a preference order on the diagnoses of M. Then D D (M) is -preferred iff t(D) D (M , br P , br H) holds.

Note that t(D) D (M , br P , br H) implies that tmax t(D); but there also are diagnoses T D (M , br P , br H) such that tmax / T. Nevertheless, it follows directly from the deﬁnition of M that for any T D (M , br P , br H) with tmax T there exist D1, D2 br(M) such that T = t(D1, D2). Hence, diagnoses of D (M , br P , br H) that contain tmax correspond one-to-one to -preferred diagnoses of M.

Example 15 (ctd.). Consider the diagnosis D = ({r4, r5}, ). It is -preferred, as it does not modify any of the bridge rules in {r1, r2}. The corresponding diagnosis t(D) is the diagnosis Do

EITER & WEINZIERL

from Example 14, i.e, t(D) = {d1(r4), d1(r5), d1(I(r4)), d1(I(r5)}, K({r4, r5}, ) {tmax} . It holds that Do D (M , br P , br H), as stated by Theorem 3.

The next theorem shows that the clone encoding M and the notion of mpm-diagnosis D m,tmax allow to select all minimal -preferred diagnoses of M. This theorem therefore establishes that the clone encoding is sound and complete.

Theorem 4. Let M be an MCS and let be a preference order on diagnoses of M. Then (D1, D2) D m, (M) holds iff t(D1, D2) D m,tmax (M , br P , br H) holds.

Recall that given a CP-net N that is compatible with an MCS M, the minimal -preferred diagnoses according to N and the irredundant N-preferred diagnoses coincide, i.e., D ird(M, N) = D m, N (M) (cf. Proposition 2). One thus can realize the selection of optimal diagnoses according

to a CP-net using the clone encoding M N and the methods provided in this section. Also note that M N has size only linearly larger than M. Since the approaches only specify some of the behavior of the observation context, the concrete choice of a logic to realize the observation remains to the user. This is especially useful for preference formalisms like CP-nets where algorithms may be chosen according to the computational complexity of the employed CP-net.

6. Computational Complexity

To select preferred and most preferred diagnoses, the previous section introduced several advanced notions of diagnosis. In this section we investigate the computational complexity of these notions. As it turns out, considering protected bridge rules as well as prioritized bridge rules does not increase the computational complexity of identifying a diagnosis.1 Identifying subset-minimal diagnoses among those with protected and prioritized bridge rules, however, incurs additional cost. Since selecting most preferred diagnoses is hard for the same complexity class in the basic case, the additional cost are expected and our approach is thus worst-case optimal. We begin by recalling the necessary notions of complexity analysis in MCS.

6.1 Complexity Classes and Context Complexity

Recall that P, EXPTIME, and PSPACE are the classes of problems that can be decided using a deterministic Turing machine in polynomial time, exponential time, and polynomial space, respectively. Furthermore NP (resp., co NP) is the class of problems that can be decided on a nondeterministic Turing machine in polynomial time, where one (resp., all) computation paths accept. The polynomial hierarchy is built as follows: ΣP 0 = ΠP 0 = P, and for all i 1, ΣP i = NPΣP i 1 is NP with a ΣP i 1 oracle and ΠP i is co-ΣP i . Given a complexity class C, D(C) denotes the difference class of C, i.e., D(C) = {L1 L2 | L1 C, L2 co-C} is the complexity class of decision problems that are the conjunction of a problem L1 in C and a problem L2 in co-C. We use the notation that D(NP) = DP 1 and

1. In line with and for comparability to the work of Eiter et al. (2014), we concentrate on recognizing diagnoses and omit deciding (advanced) diagnosis existence. Brieﬂy, the latter problem is for context complexity C in NPC

for polynomial-time ﬁlters f (in particular, for protected bridge rules), which collapses to C if C is closed under conjunction and projection; thus for all considered notions, the existence problem is in this case C-complete.

PREFERENCE-BASED INCONSISTENCY MANAGEMENT IN MULTI-CONTEXT SYSTEMS

D(ΣP i ) = DP i . A prototypical problem that is complete for DP 1 is deciding, given a pair (F1, F2) of propositional Boolean formulas, whether F1 is satisﬁable and F2 is unsatisﬁable. Since MCS are composed of contexts where each context is a KR formalism, the complexity of deciding whether an MCS is consistent clearly depends on the complexity of the KR formalisms employed in its contexts. This intuition is captured by the notion of context complexity, which measures deciding whether a set of beliefs is acceptable under a given knowledge-base of a context and a given set of formulas added via bridge rules. Let OUT i = {p | (i : p) body(r) for some r br(M)} denote the set of beliefs of context Ci which occur in the body of some bridge rule of the MCS. Context complexity is deﬁned wrt. output-projected beliefs, i.e., belief sets projected to output beliefs (for details see Eiter et al., 2014), formally:

Deﬁnition 19 (cf. Eiter et al., 2014). Given a context Ci = (kbi, bri, Li) and a pair (H, Ti), with H {ϕ (r) | r bri} and Ti OUT i, the context complexity CC(Ci) of Ci is the computational complexity of deciding whether there exists an Si ACCi(kbi H) such that Si OUT i = Ti.

We view here (as in Eiter et al., 2014) the computational complexity of a problem Π technically as the set of all problems Π that are polynomial-time many-one reducible to Π, i.e., as the problems that are not harder than Π; in particular SAT has the computational complexity NP. Furthermore, the logics Li of all contexts are considered to be given implicitly and thus the instance size of a given MCS M is |M| = |kb M| + |br(M)| where |kb M| denotes the size of the knowledge bases in M and |br(M)| denotes the size of its set of bridge rules. Given an MCS M, we say M has upper context complexity C, denoted CC(M) C, if CC(Ci) C for every context Ci of M; we say M has lower context complexity C, denoted CC(M) C, if C CC(Ci) for some context Ci of M. We say that M has context complexity C, denoted CC(M) = C, iff CC(M) C and CC(M) C. That is, if CC(M) = C all contexts in M have complexity at most C, and some context in M has C-complete complexity with respect to polynomial-time many-one reductions, which requires that the class C has complete problems. Restricting disjunctive ASP to the ground case admits ΣP 2 -complete acceptability checking (see Dantsin, Eiter, Gottlob, & Voronkov, 2001; Gottlob, 1992), hence the context complexity of a context using Lasp Σ is ΣP 2 -complete given that all kb-elements are ground; in the (function-free) non-ground case, the context complexity is NEXPTIMENP (Eiter, Gottlob, & Mannila, 1997). Acceptability checking of a context using Lpl Σ amounts to entailment checking for all literals present in the belief set and non-entailment checking for all literals absent in the belief set, i.e., it amounts to an UNSAT and an independent SAT check, hence the context complexity is DP.

Example 16. The MCS M = (C1, C2, C3) of Example 3 is such that CC(C1) = NP and CC(C2) = CC(C3) = ΣP 2 . As NP ΣP 2 , it holds that CC(M) ΣP 2 , and as C2 is ΣP 2 -complete, we obtain CC(M) ΣP 2 ; hence CC(M) = ΣP 2 .

The problem of deciding whether for a given MCS M and a pair (D1, D2) of bridge rules, it holds that (D1, D2) is a minimal diagnosis, i.e., deciding whether (D1, D2) D m(M), is denoted by MCSDm. As shown in [Prop. 11 by Eiter et al., 2014] if CC(M) = P, then MCSDm is DP 1 - complete; if CC(M) = C and C is a class with complete problems and closed under conjunction and projection, then the problem of MCSDm is D(C)-complete. Intuitively, a class C is closed under conjunction, if all its decision problems are such that checking multiple instances of the problem at the same time is a problem in C. For example, checking whether a propositional formula F is

EITER & WEINZIERL

Context Deciding (D1, D2) ?

complexity D m(M) D m(M, br P ) D (M, br P , br H) D m,tmax (M, br P , br H)

CC(M) MCSDm MCSDPm MCSDPH MCSDPHm,tmax

P DP 1 -complete DP 1 -complete DP 1 -complete ΠP 2 -complete

NP DP 1 -complete DP 1 -complete DP 1 -complete ΠP 2 -complete

ΣP i , i 1 DP i -complete DP i -complete DP i -complete ΠP i+1-complete

PSPACE PSPACE-complete

EXPTIME EXPTIME-complete

Shown by Eiter et al. (2014) Theorem 5 Theorem 6 Theorems 7 + 8

Table 1: Complexity results of deciding whether a candidate diagnosis is subset-minimal, additionally protected, prioritized-minimal, or an mpm-diagnosis. Problem MCSDMPREF has the same complexity as MCSDPHm,tmax if deciding D D is in CC(M).

satisﬁable is in NP; given two independent formulas F and G, checking whether both are satisﬁable also is in NP since it amounts to checking whether F G is satisﬁable. A class C is closed under projection, if intuitively for every problem in C, the decision problem on projected instances (similar as for output-projected equilibria) is contained in C. For example, given a formula F in propositional logic over variables var(F), ﬁnding an assignment VA over (projected) variables A var(F) such that (i) there exists an assignment V A to the variables A = var(F) \ A and (ii) VA V A |= F, is as hard as ﬁnding an (overall) assignment V over var(F) such that V |= F. For further details we refer to the work of Eiter et al. (2014). Speciﬁcally, for CC(M) = ΣP i it holds that MCSDm is in DP i . Furthermore, since DP i is closed under conjunction and projection, it holds that MCSDm is DP i -complete if at least one context in M is complete for ΣP i .

6.2 Overview of Results

We now investigate the complexity of our enhanced notions of diagnosis. More speciﬁcally, we study the complexity of the following decision problems, given an MCS M, a candidate diagnosis D 2br(M) 2br(M), and depending on the problem additionally given protected bridge rules br P br(M), prioritized bridge rules br H br(M), and tmax br(M):

MCSDPm: deciding whether D is a subset-minimal diagnosis with protected bridge rules, i.e., deciding whether D D m(M, br P ) holds.

MCSDPH: deciding whether D is a prioritized-minimal diagnosis, i.e., deciding whether D D (M, br P , br H) holds.

MCSDPHm,tmax : deciding whether D is an mpm-diagnosis (a subset-minimal prioritizedminimal diagnosis wrt. tmax), i.e., deciding whether D D m,tmax (M, br P , br H) holds.

MCSDMPREF: given an arbitrary preference order deciding whether D D m, (M) holds.

PREFERENCE-BASED INCONSISTENCY MANAGEMENT IN MULTI-CONTEXT SYSTEMS

We show that MCSDPm is not harder than MCSDm, i.e., deciding whether a candidate diagnosis D is a subset-minimal diagnosis with protected bridge rules is not harder than deciding whether D is a subset-minimal diagnosis (Thm. 5). We also demonstrate that the same is true for prioritizedminimal diagnoses, i.e., MCSDPH is as hard as MCSDm (Thm. 6). This notion of diagnosis can be applied to the plain encoding Mpl for total preference orders to select minimal -preferred diagnoses according to a total preference order . The drawback of this approach, however, is the exponential number of bridge rules in Mpl . Since the clone encoding M incurs no exponential blow-up of bridge rules, it is reasonable to expect that the computational complexity of MCSDPHm,tmax is higher than the one of MCSDm. Indeed, for context complexity CC(M) in ΣP i we prove that MCSDPHm,tmax is in ΠP i+1 while MCSDm is in DP i (Thm. 7). Speciﬁcally, for CC(M) in NP the complexity of MCSDPHm,tmax is ΠP 2 while MCSDm is in DP 1 . Since deciding t(D) D m,tmax (M , br P , br H) only serves to decide D D m, (M), we also investigate the lower bound for the latter problem, i.e., MCSDMPREF. We prove that it is ΠP 2 -hard (Thm. 8) if CC(M) is in P; hence we obtain that the clone encoding using M and D m,tmax (M , br P , br H) is in fact worst-case optimal. Furthermore, we also show that MCSDMPREF is hard for ΠP i+1 if CC(M) is hard for ΣP i . Table 1 summarizes the results for the introduced notions of diagnosis and for context complexity being in one of several complexity classes. Note that the results for PSPACE and EXPTIME in the last column follow from the fact that co NPPSPACE = PSPACE and co NPEXPTIME = EXPTIME for membership while hardness can be shown using a trivial MCS where the acceptability function of some context is hard for PSPACE resp. EXPTIME. Our results are derived using several reductions and a genuine algorithm, which are presented in the remainder of this section; proofs can be found in the appendix.

6.3 Derivation of Results

For the problem of recognizing minimal diagnoses with protected bridge rules we have the following result.

Theorem 5. MCSDPm is equivalent to MCSDm under polynomial-time reductions.

Indeed, MCSDPm is polynomially reducible to MCSDm, by simply checking ﬁrst whether the candidate diagnosis contains protected bridge rules and then solve MCSDm to check whether it is subset-minimal. A formal reduction is provided in the proof of Theorem 5. Conversely, every instance of MCSDm is an instance of MCSDPm with br P = , and thus MCSDm trivially reduces to MCSDPm in polynomial time. Next we consider the problem MCSDPH. We will show that this problem has the same complexity as MCSDPm. To this end we ﬁrst present a polynomial-time many-one reduction DPH2DPm from MCSDPH to MCSDPm. We remark that a direct membership proof would be simpler, but the reduction is of interest in its own right.

6.3.1 UNDERLYING IDEA OF DPH2DPm

Given an MCS M with protected bridge rules br P and prioritized bridge rules br H, we simulate the modiﬁcations of regular bridge rules inside the resulting MCS. The set Rreg of regular (nonprioritized, non-protected) bridge rules is Rreg = br(M) \ br H \ br P and their modiﬁcations can

EITER & WEINZIERL

d1(r2) d2(r2)

Mmr(θ,Kp) M

r1 : (2 : b) (1 : a).

r2 : (3 : d) (2 : c).

kbn+1 = removedr1 not not removedr1. removedr2 not not removedr2.

kbn+2 = not removedr1 not removedr1. removedr1 not not removedr1. uncondr1 not not uncondr1. not uncondr1 not uncondr1.

Figure 6: The reduction from MCSDPH to MCSDPm exempliﬁed on an MCS M = (C1, C2, C3) with two bridge rules br(M) = {r1, r2}. Shown are the MCS M M employed in the reduction DPH2DPm (components are indicated in gray), bridge rules of M, and the knowledge bases of Cn+1 and Cn+2.

be simulated by using a meta-reasoning transformation Mmr(θ,Kp) = (C1, . . . , Cn+1), where the bridge rules of Cn+1 correspond to modiﬁcations of bridge rules in Rreg. They take their values from an additional context Cn+2 that generates all possible modiﬁcations, i.e., every possible modiﬁcation corresponds to an acceptable belief set of Cn+2. We protect in the resulting MCS M = (C1, . . . , Cn+2) all bridge rules except those that correspond to modiﬁcations of bridge rules in br H, i.e., every diagnosis of M corresponds to one (or more) diagnoses of M, but the diagnoses of M only contain bridge rules corresponding to subsets of br H. Consequently, any minimal diagnosis of M is br H-minimal wrt. M. To ensure that the diagnosis indeed is -minimal, we further add a copy of M, i.e., the resulting MCS is M M where M ensures minimality wrt. br H and M ensures minimality wrt. . An illustration of the resulting MCS is given in Figure 6 for a concrete MCS that is considered later in Example 17 below in detail.

PREFERENCE-BASED INCONSISTENCY MANAGEMENT IN MULTI-CONTEXT SYSTEMS

6.3.2 FORMAL DETAILS OF DPH2DPm

Given an MCS M and a set Rreg br(M), let Kp = and let θ be such that for all D1, D2 br(M) the property θ(D1, D2, ) holds. We craft an MCS based on the meta-reasoning MCS Mmr(θ,Kp) = (C1, . . . , Cn, Cn+1) to obtain an MCS where the modiﬁcation of all bridge rules in Rreg is hidden in the set of possible belief states. To this end, we introduce another context Cn+2 without bridge rules whose acceptable belief sets encode all respective modiﬁcations of bridge rules of Rreg. Formally, Cn+2 = (Lasp Σ , kbn+2, ) where

kbn+2 = not removedr not removedr. removedr not not removedr. uncondr not not uncondr. not uncondr not uncondr.

Observe that for every D1, D2 Rreg, there is a belief set Sn+2 with

Sn+2 {not removedr, uncondr | r Rreg} = {not removedr | r Rreg \ D1}

{uncondr | r D2}.

In addition to that, since Cn+2 has no bridge rules, it follows that Sn+2 ACCn+2(kbn+2 app(brn+2, S )) holds for all belief states S = (S 1, . . . , S n+2) where S n+2 = Sn+2. Recall that all bridge rules of Cn+1 are either of the form (n + 1 : not removedr) . or (n + 1 : uncondr) . where r br(M). Let Cn+1 = (L, kbn+1, brn+1); then C n+1 = (L, kbn+1, br n+1) where

br n+1 = {(n + 1 : not removedr) (n + 2 : not removedr). | r br(M), r Rreg} (11)

{(n + 1 : uncondr) (n + 2 : uncondr). | r br(M), r Rreg} (12)

{(n + 1 : not removedr) . | r br(M), r / Rreg} (13)

{(n + 1 : uncondr . | r br(M), r / Rreg}. (14)

Intuitively, C n+1 equals Cn+1 but the bridge rules occurring in Rreg refer to Cn+2. Similar to the meta-reasoning encoding, we denote by d1(r) and d2(r) the corresponding bridge rule of the form in (13) and in (14), respectively. We extend these notions to sets of bridge rules and let di(R) = {di(r) | r R} for any R br(M) and i = 1, 2. For example, d1(br(M) \ R1) denotes all bridge rules of line (13). Finally, we call M = (C1, . . . , Cn, C n+1, Cn+2) the meta-guessing MCS for M and Rreg. The effect of the redirection to Cn+2 is that the acceptable belief sets of Cn+2 guess all possible modiﬁcations. The rest of M behaves like an ordinary meta-reasoning encoding, where protected bridge rules of M are br P = br M \ (d1(br(M) \ Rreg) d2(br(M) \ Rreg)), i.e., all bridge rules are protected except those in Cn+1 that do not correspond to bridge rules in Rreg. Now the reduction DPH2DPm from MCSDPH to MCSDPm is as follows:

(M, (D1, D2), br P , br H) 7 (M M, (D 1, D 2), br P )

where M is the meta-guessing MCS wrt. Rreg = br(M) \ br P \ br H and br P = br P I(br P ) where I is the mapping wrt. M M and br P is the set of protected bridge rules of the metaguessing MCS M ; furthermore D 1 = I(D1) d1(D1 br H) and D 2 = I(D2) d2(D2 br H), i.e., (D 1, D 2) contains a candidate diagnosis of M and a candidate diagnosis over br H with modiﬁcations to the remaining bridge rules of M being simulated by M .

EITER & WEINZIERL

Observe that the size of (M M, (D 1, D 2), br P ) is polynomial in the size of (M, (D1, D2), br P , br H), because M M only has four times as many bridge rules as M and all other sets are subsets of these bridge rules. Furthermore, (M M, (D 1, D 2), br P ) can be computed in polynomial time in the size of (M, (D1, D2), br P , br H); more precisely, even in linear time.

Example 17. We illustrate the reduction DPH2DPm and the MCS resulting from on a simple MCS M = (C1, C2, C3) with three contexts and two bridge rules br(M) = {r1, r2} as follows:

r1 : (2 : b) (1 : a).

r2 : (3 : d) (2 : c).

No bridge rule is protected, i.e., br P = , and r2 is prioritized, i.e., br H = {r2}, thus Rreg = {r1}. Figure 6 illustrates M (on the right) and the meta-guessing MCS M for M and Rreg (on the left); their combination M M (the overall Figure 6), is the MCS constructed in the reduction

DPH2DPm. It also shows a possible realization of the contexts Cn+1 and Cn+2 using ASP. Since Cn+1 stems from the meta-reasoning encoding where θ holds for all potential diagnoses, the two rules in kbn+1 are sufﬁcient to exhibit the observed modiﬁcations of r1 and r2 as beliefs. Intuitively, the rules in kbn+2 guess all potential modiﬁcations of r1 and exhibit them to Cn+1 as beliefs.

The following lemma shows that DPH2DPm indeed is a correct reduction from MCSDPH to MCSDPm.

Lemma 4. DPH2DPm is a polynomial-time reduction from MCSDPH to MCSDPm.

On the other hand, one can easily reduce MCSDPm to MCSDPH. We thus obtain that MCSDPH indeed has the same complexity as deciding D D m(M, br P ) and hence whether D D m(M) holds.

Theorem 6. MCSDPH is equivalent to MCSDPm under polynomial-time reductions.

6.3.3 FURTHER COMPLEXITY RESULTS

A stepping stone for analyzing MCSDPHm,tmax is the decision problem MCSDPHtmax , which we consider next. MCSDPHtmax is deﬁned as follows: given an MCS M, a candidate diagnosis D 2br(M) 2br(M) with D = (D1, D2), protected bridge rules br P br(M), prioritized bridge rules br H br(M), and tmax br(M); decide whether (i) tmax D2 and (ii) for all T D m(M, br P ) it holds that T br H D T =br H D. Notice that MCSDPHtmax basically amounts to checking the presence of tmax in a candidate diagnosis of MCSDPH. As the following lemma shows, former is not harder than the latter.

Lemma 5. MCSDPHtmax is polynomial-time reducible to MCSDPH and thus in the complexity class C, if MCSDPH is in C and C is closed under polynomial reductions.

Note that all classes in Section 6.1 above are closed under polynomial-time reductions. We use an MCSDPHtmax -oracle in Alg. 1 to obtain membership results of MCSDPHm,tmax .

Theorem 7. If MCSDPH is in C, then MCSDPHm,tmax is in co NPC.

PREFERENCE-BASED INCONSISTENCY MANAGEMENT IN MULTI-CONTEXT SYSTEMS

Algorithm 1: Deciding whether (D1, D2) D m,tmax (M, br P , br H) holds.

Input : MCS M, (D1, D2), br P , and br H with D1, D2 br(M), br P , br H br(M). Output: YES if (D1, D2) D m,tmax (M, br P , br H)

1 if oracle MCSD P Htmax (D1, D2), M, br P , br H = NO then output YES

2 guess T1, T2 br(M)

3 if oracle MCSD P Htmax (T1, T2), M, br P , br H = YES (T1, T2) = (D1, D2) (T1, T2) br(M)\br H (D1, D2) (T1, T2) =br(M)\br H (D1, D2) then output YES

Proof. Algorithm 1 decides whether (D1, D2) D m,tmax (M, br P , br H) holds using an oracle for MCSDPHtmax . Intuitively, (D1, D2) is not an mpm-diagnosis if it either is no subset-minimal prioritized-minimal containing tmax, which is checked in the ﬁrst line using the oracle, or if there exists a subset-minimal prioritized-minimal diagnosis (T1, T2) (D1, D2) that also contains tmax. In the second line such a (T1, T2) is guessed and in the third line it is veriﬁed that the guessed candidate indeed has the above properties. Checking whether (D1, D2) D m,tmax (M, br P , br H) holds is possible by Algorithm 1 and negating its output. By assumption MCSDPH is in C, thus by Lemma 5 it holds that MCSDPHtmax is in C, i.e., the complexity of the oracle in Algorithm 1 is in C. Since Algorithm 1 uses a polynomial-size guess for (T1, T2) its complexity clearly is NPC. Consequently, deciding whether (D1, D2) D m,tmax (M, br P , br H) holds is in co NPC.

The previous decision problems arise from our approach to realize the selection of preferred and ﬁltered diagnoses of an MCS. To give a full picture, we also investigate the complexity of the basic problem, i.e., of MCSDMPREF. As the following theorem shows, MCSDMPREF itself is ΠP 2 -hard even if both the context complexity and deciding whether D D holds are tractable. This result also shows that our approach of realizing the selection of minimal -preferred diagnoses is worst-case optimal.

Theorem 8. If CC(M) is hard for ΣP i (ΠP i ) then MCSDMPREF is hard for ΠP i+1 (ΠP i+2) with i 0. Moreover, MCSDMPREF is ΠP 2 -hard even if both CC(M) and deciding D D are in P.

For establishing completeness of MCSDMPREF, we use the clone encoding of the previous section as a polynomial-time reduction to MCSDPHm,tmax .

Corollary 1. Let M be an MCS with CC(M) = ΣP i , i 0 (resp., CC(M) = PSPACE, CC(M) = EXPTIME), and a preference order such that deciding D D is in ΣP i (resp., PSPACE, EXPTIME). Then MCSDMPREF is complete for ΠP i+1 (resp., PSPACE, EXPTIME). In particular, MCSDMPREF is ΠP i+1-complete if deciding D D is in P and CC(M) = ΣP i , i 0.

Examples of preference orders as hard as PSPACE are CP-nets in general while restricted variants are in NP or even P (cf. Section 3.2.1). We can also use the clone encoding to show the completeness of MCSDPHm,tmax .

Corollary 2. MCSDPHm,tmax is ΠP i+1-complete if CC(M) = ΣP i , i 1, and ΠP 2 -complete if CC(M) = P or CC(M) = NP.

EITER & WEINZIERL

The hardness result of ΠP i+2 for MCSDMPREF with CC(M) = ΠP i might seem to contradict Corollary 2, which shows, using the clone encoding, that MCSDMPREF is in ΠP i+1 for CC(M) = ΣP i . However this is no contradiction since the basic problem of recognizing minimal diagnoses, i.e., MCSDm, is not known to be in ΣP i for CC(M) = ΠP i . In the work of Eiter et al. (2014) it is shown that MCSDm is in D(C) if C is closed under conjunction and projection, which presumably is not the case for ΠP i , i 0 (while it is for ΣP i ). Hence for CC(M) = ΠP i , MCSDm is not in D(ΠP i ), thus MCSDPHtmax is presumably not in ΠP i+1. On the other hand, ΠP i is in ΣP i+1, consequently MCSDm is in D(ΣP i+1) and MCSDPHtmax in ΠP i+2.

7. Discussion and Related Work

In this section we ﬁrst discuss options for decomposing the central observation context of the metareasoning transformation and then consider related work.

7.1 Decomposing the Central Observation Context

A key strength of MCS is the capability of integrating different knowledge bases in a decentralized manner. Accordingly, scenarios for MCS where a centralized speciﬁcation of preferences on diagnoses may be unwanted, e.g., if different companies agree to share data, their preferences might expose some information they are actually not willing to share. The approaches presented here use a central observation context that knows all bridge rules, or more speciﬁcally, that knows the labels of all bridge rules, and for each of them whether and how it is modiﬁed. The observer, however, does neither know the structure, i.e., the contents of the head and body, of the bridge rules, nor the actual status of the information exchange, and it cannot see any beliefs of any context. Hence, our approach supports almost full information hiding and only decentralization is lost. Criteria for decomposing a context have been investigated by Weinzierl (2014). The results there can be applied to the meta-reasoning transformation that we described in Section 5.1 in order to decompose the observation context of the ﬁlter encoding Mf. If the underlying ﬁlter can be broken up, the central observation context thus may be replaced with several contexts, each covering only a partition of the bridge rules in br(M). If there is a partition br(M) = A B (where A, B are disjoint and nonempty) such that a given ﬁlter f satisﬁes that for all D1, D2 br(M) it holds that f(D1, D2) = 1 iff f(D1 A, D2 A) = 1 and f(D1 B, D2 B) = 1, then the observation context of Mf is decomposable. Informally, f is such that the modiﬁcations of bridge rules in A can be checked independently from those in B and vice versa. Notice that for any reasonable logical formalism which realizes f, checking whether f(D1 A, D2 A) = 1 resp. f(D1 B, D2 B) = 1 can be realized by two (independent) knowledge bases; the latter are the decomposition of the observation context. Depending on f, this decomposition may be repeated several times, where each time one context is decomposed into two independent contexts until the observation of diagnoses is fully decentralized.

Example 18. Consider the MCS Mf = (C1, C2, C3) of Example 11 realizing the ﬁlter f on the MCS M whose bridge rules are br(M) = {r1, r2, r3}. Recall that f is deﬁned by:

f(D1, D2) =

0 if r3 D1, r2 / D1 or r3 / D1, r2 D1, 0 if r3 D2, r2 / D2 or r3 / D2, r2 D2, 1 otherwise.

PREFERENCE-BASED INCONSISTENCY MANAGEMENT IN MULTI-CONTEXT SYSTEMS

Obviously, br(M) can be partitioned into A = {r2, r3} and B = {r1}, because for all D1, D2 br(M) holds that f(D1 B, D2 B) = 1 and f(D1 A, D2 A) = f(D1, D2). The resulting decomposition of bridge rules in C3 is: br A 3 = {d1(r2), d2(r2), d1(r3), d2(r3)} and br B 3 = {d1(r1), d2(r1)}. Since the knowledge base kb3 of Mf uses ASP, we can easily get the knowledge bases kb A 3 and kb B 3 by partitioning kb3:

removedr2 not not removedr2. removedr3 not not removedr3. removedr3, not removedr2. not removedr3, removedr2. uncondr3, not uncondr2. not uncondr3, uncondr2.}

kb B 3 = {removedr1 not not removedr1.}

The resulting decomposed MCS is M = (C 1, C 2, CA 3 , CB 3 ), where all bridge rules from C3 either belong to CA 3 or CB 3 and all beliefs of C3 that are referred to in other bridge rules of Mf either refer to CA 3 or CB 3 in M . The diagnoses of M correspond one-to-one to those of Mf. As diagnoses with protected bridge rules are directly based on ordinary diagnoses, these results thus extend to diagnoses with protected bridge rules. The MCS M can be used to obtain minimal ﬁltered diagnoses of M, where the ﬁlter itself is realized in a decentralized way.

In principle, decomposition may also be applied to the clone encoding M , but the bridge rule tmax disallows a simple decomposition. Nonetheless, it seems possible to achieve decomposition using additional protected bridge rules for information exchange between the decomposed contexts; a formal result, however, remains to be established.

7.2 Related Work

We now brieﬂy consider further, previous work and then discuss related work on multi-context systems and other KR formalisms.

7.2.1 PREVIOUS WORK

In the work of Weinzierl (2014) several of the notions presented here have been investigated and exempliﬁed in more depth; among others, formal results on the decomposition method introduced in Section 7.1 above. While in this article fully-compatible CP-nets are shown as sample formalism to specify preferences over diagnoses, there are other possibilities of using CP-nets to compare diagnoses, e.g. by assigning each bridge rule r only one variable V r and a domain of {unmodiﬁed, removed, condition-free}. This kind of CP-nets, however, cannot represent a candidate diagnosis (D1, D2) with r D1 D2, i.e., where a bridge rule is both removed and conditionfree, while fully compatible CP-nets can represent all candidate diagnoses. There is another sample instantiation of preference orders that is based on units of modiﬁed bridge rules. The idea is that bridge rules are grouped according to the information they carry; e.g. in Example 4 there are two units: health-related information (r1 and r2) and billing-related information (r3, r4, and r5). A preference relation over diagnoses is established by considering how many such units are modiﬁed (hence potentially broken); preferred are those diagnoses modifying the least number of units. Two transformations for meta-reasoning on diagnoses in an MCS M were developed, where the ﬁrst merely adds bridge rules and contexts to observe the information exchange between contexts of M. The disadvantage of this transformation is that there are concrete MCS for which the observation

EITER & WEINZIERL

cannot identify each diagnosis correctly. The second transformation, which is the one presented in this article, is more general and allows for the correct identiﬁcation of diagnoses for all MCS; however, this comes at the price of rewriting the bridge rules. Below we discuss two closely related approaches that rely on preference to ensure consistency of MCS and a third approach that integrates preferences into MCS contexts directly. We also sketch how our approach can be applied to further extensions of the MCS framework and we relate our approach to preference-based inconsistency management in other KR formalisms. An extended discussion is available in the work of Weinzierl (2014).

7.2.2 PREFERENTIAL MCS

In the work of Mu, Wang, and Wen (2015) an approach at preference-based inconsistency management in MCS is introduced: Preferential Multi-Context Systems (PMCS) are similar to ordinary MCS where an additional preference order s restricts the information ﬂow. The relation s is a total preorder on a partitioning of the contexts of M, i.e., s compares sets of contexts and all contexts in the same set are treated as equally preferred. The information ﬂow then is restricted from more preferred to less-or-equally preferred contexts, i.e., a PMCS is stratiﬁed. Note that this total preorder differs from our notion of a total preference, since we consider preference over candidate diagnoses, not over sets of contexts. Based on the ordering, one may ask for a maximal consistent section, which is the maximal initial segment of the ordering of preferred contexts that still admit an equilibrium. Furthermore, the notion of a c-diagnosis is introduced, which is a diagnosis that does not modify bridge rules of the maximal consistent section. Note that Mu et al. (2015) only consider diagnoses that remove bridge rules, i.e., diagnoses of the form (D1, ). In the same work, it is noted that a ﬁlter f on diagnoses may be used to select c-diagnoses, by simply ﬁltering out all diagnoses that modify bridge rules of the maximal consistent section. This however, requires to know the maximal consistent section in advance. Intuitively, c-diagnoses can be fully captured by preference orders as follows. We recall the notation of an i-cut for PMCS ﬁrst: given a PMCS M with total preorder s on sets of contexts of M, the i-cut of M, denoted by M(i) contains all contexts that are in the i-th and lower stratum according to s. For example, M(1) contains the most preferred contexts, M(2) contains contexts of M(1) and all that are less preferred than the ones in M(1) but more preferred than any other contexts, and so on. Notice that M(2) M(1) holds, i.e., M(i) contains all contexts of M(j) for j i. Now a preference order is deﬁned on candidate diagnoses as follows: (D1, D2) (D 1, D 2) iff D2 = and for every 1 i m such that D1 {r brℓ| Cℓ M(i)} = , it holds that D 1 {r brℓ| Cℓ M(i)} = . The intuition is that prefers (D1, D2) over (D 1, D 2) if every i-cut M(i) that is modiﬁed by the former is also modiﬁed by the latter. This effectively guarantees that the most preferred diagnoses according to only modify bridge rules from less preferred contexts. In fact, no most preferred diagnosis modiﬁes any bridge rule of the maximal consistent section, because such a diagnosis is always preferred. Thus, the set of most preferred diagnoses according to should coincide with the set of c-diagnoses. Clarifying this and a more extensive comparison to PMCS remains for future work. Another approach for handling inconsistency in MCS based on a preference order was presented by Caire, Bikakis, and Traon (2013). The notion of conviviality stemming from multi-agent systems is used to model and measure information dependencies in MCS: intuitively, conviviality measures

PREFERENCE-BASED INCONSISTENCY MANAGEMENT IN MULTI-CONTEXT SYSTEMS

how much contexts exchange information with each other. Every ordinary diagnosis D of an inconsistent MCS M is then associated with the conviviality of the resulting MCS where D is applied, i.e., the conviviality of M[D]. A diagnosis is regarded as being optimal, if its associated conviviality is maximal. Suppose that Conv(M) is the conviviality of an MCS M, we can capture the approach by selecting -preferred diagnoses where is a preference on diagnoses as follows: D D iff Conv(M[D]) Conv(M[D ]). Subsequently, D (M) is the set of optimal diagnoses according to Caire et al. (2013).

7.2.3 MULTI-CONTEXT SYSTEMS WITH PREFERENCES

Le, Son, and Pontelli (2015) recently extended the abstract logics of MCS with ranking information to ranked logics and deﬁned an equilibrium semantics for the ensuing Multi-Context Systems with Preferences (MCSP). Formally, a ranked logic is a tuple L = (KBL, BSL, ACCL, <L) such that (KBL, BSL, ACCL) is an abstract logic for MCS and <L is a partial order over pairs (kb, bs) of a knowledge base kb and an acceptable belief set for kb, i.e., bs ACCL(kb). The semantics of an MCSP M = (C1, . . . , Cn) is given in terms of particular equilibria of the induced ordinary MCS M = (C 1, . . . , C n), in which the ranking information is dropped. An equilibrium S of M

is weakly preferred (resp. strongly preferred) over an equilibrium S of M , if S is preferred over S in some (resp. every) ranking <i of the contexts Ci, i.e., (kbi, Si) <Li (kbi, S i) holds where Ci = (Li, kbi, bri). Furthermore, S is most preferred, if there is no other equilibrium S of M

that is weakly (resp. strongly) preferred over S; the semantics of M is given by its most preferred equilibria. Compared to our work, there is a noticeable difference: in MCSP preference information is directly integrated into the semantics to select among equilibria (provided some exist), while in our approach preference is used to select diagnoses for systems that do not admit an equilibrium, i.e., systems that are inconsistent. This is similar with distributed abductive diagnosis (DAD), which is brieﬂy sketched by Le et al. (2015) as an application for MCSP; they discuss how one can use an MCSP in order to obtain an abductive explanation for a set of observations on an MCS from a given set of hypotheses. While DAD strives to explain beliefs in an equilibrium, the diagnoses that we consider address the lack on an equilibrium. Le et al. (2015) do not consider whether their approach could be used to diagnose an inconsistent MCS. As their hypotheses are elements of knowledge bases respectively belief sets but not observations of inconsistency of the system as such, this is not apparent. It remains to be clariﬁed whether (under suitable restrictions) and how this is possible. As regards preference, in principle, one could use <Li over equilibria to select those diagnoses that admit the best ranked equilibria. More formally, we can construct a preference order such that D D holds if some (resp. all) S EQ(M[D]) are weakly preferred (resp. strongly preferred) over some (resp. all) S EQ(M[D ]).

7.2.4 DEFEASIBLE MCS

In ordinary MCS, all bridge rules that are applicable in a belief state add their head formulas to the respective contexts. Different from that, Defeasible MCS (d MCS) have bridge rules which only add their head formulas if no inconsistency arises, i.e., bridge rules are defeasible. By that, defeasible MCS are an important contribution to inconsistency management in MCS since these MCS are inherently consistent. They have been investigated in the works of Bikakis and Antoniou (2008, 2010), and Bikakis, Antoniou, and Hassapis (2009, 2011), which address inconsistency in a homogeneous

EITER & WEINZIERL

MCS setting. The semantics of d MCS is given by resorting to an argumentation-inspired approach (Bikakis & Antoniou, 2010). Each context is a local theory composed of strict and defeasible rules, where the conclusion of an applicable strict rule is always considered while for defeasible rules their conclusion is only considered if there is no contrary evidence. Bridge rules, or mapping rules, are (local) defeasible rules whose body literals refer to other contexts. The decision which rules to ignore is based for every context on a strict total order of all contexts. The set of (mapping) rules that are ignored thus corresponds to a unique deletion-only diagnosis whose declarative description is more involved compared to our notion. Since local information is important for identifying the defeasible rules that are ignored, an encoding within our framework is possible but requires an involved MCS where contexts expose private information. One notable advantage of defeasible MCS is that for acyclic systems, only a polynomial number of computation steps is required for answering queries that are a single literal. The second component of diagnoses, i.e., rules that are forced to be applicable, however, have no counterpart in the inconsistency management approach for d MCS. Furthermore, the strict total order over contexts forces the user to make (perhaps unwanted) decisions at design time; alternative orders would require a redesign and separate evaluation. Bikakis and Antoniou (2011) also relaxed the strict total order condition to allow for partial preference orders over contexts. Four variants, based on argumentation, are introduced to resolve inconsistency and it is shown that partial preference orders come at the cost of more information exchange being rejected. Our approach avoids this and allows to respect various kinds of orderings and preferences; it is not committed to a particular formalism and in principle any formalism that can be couched into a context of an MCS can be employed.

7.2.5 FURTHER MCS EXTENSIONS

In recent years, some signiﬁcant extensions of the Multi-Context Systems framework itself have been proposed. We give a short overview of these extensions and sketch how the notions of diagnosis and preference can be adapted. Managed Multi-Context Systems (m MCS) are an extension of MCS where each context is equipped with a management component that is called a context manager (Brewka, Eiter, Fink, & Weinzierl, 2011b). This manager allows applicable bridge rules to not only add information, but to apply arbitrary operations on the knowledge base. In m MCS the heads of bridge rules are operational statements of the form o(s), where s is a knowledge-base element as in ordinary MCS and o is the name of an operation to apply, e.g., revise( p) indicates that the knowledge base is to be revised with the formula p. Many kinds of operations can be captured by m MCS, e.g. updating logic programs, belief revision, or database view updates. Most notably, if all context managers ensure locally that some acceptable belief set exists for the context, then inconsistency in an m MCS may only arise from cyclic information ﬂow. Notably, m MCS can be translated faithfully to MCS, hence the diagnosis notion of MCS and the techniques for selecting most preferred diagnoses also extend to m MCS. Reactive Multi-Context Systems (r MCS), which were introduced and investigated by Brewka (2013), Ellmauthaler (2013), and Brewka, Ellmauthaler, and P uhrer (2014a, 2014b), and evolving Multi-Context Systems (e MCS), which were deﬁned and studied by Goncalves, Knorr, and Leite (2014b, 2014a) are similar formalisms. Both are an extension of m MCS to allow change over time; although r MCS and e MCS have been developed independently and their formalizations differ somehow, they are, in essence, quite similar. Both adopt a discrete time ontology where at each

PREFERENCE-BASED INCONSISTENCY MANAGEMENT IN MULTI-CONTEXT SYSTEMS

step a set of observations is taken into account. Observations then either inﬂuence sensor atoms in bridge rules (r MCS) or the knowledge bases of designated sensor contexts with ﬁxed acceptability functions (e MCS). A semantics is deﬁned that pairs at each time step the observations with an equilibrium for that step, taking into account the equilibrium of the previous step, i.e., semantics is an incremental sequence of equilibria. For e MCS this sequence is called an evolving equilibrium while for r MCS it is called a run.

We note that one may unroll the time steps of a given r MCS or e MCS M such that for an observation sequence of k time steps, the unrolled MCS Mu contains k copies of the ordinary contexts and bridge rules of M. Sensor atoms and sensor contexts are at each time step according to the step in the observation sequence and additional bridge rules for inertia and incremental change of beliefs and knowledge bases carry information from copy i to copy i + 1 in the unrolled system Mu. Then, Mu is an ordinary MCS where the notions of diagnosis, ﬁlter, and preference can be applied, hence these notions also extend to r MCS and e MCS.

Since any ordinary bridge rule r br(M) is duplicated k times in Mu, a diagnosis can independently modify the copy of r at time i from the copy of r at time j, for i = j. Such independent modiﬁcations may be unwanted and one may consider only a diagnosis to be valid that modiﬁes all copies uniformly, or alternatively consider only diagnoses that keeps bridge rules unmodiﬁed until some time point ℓand for all time points i ℓthe same modiﬁcation is applied. Notice that one can easily craft a ﬁlter f for such unrolled Mu that ensures either of the above conditions. Vice versa, it is also possible to deﬁne notions of diagnosis with those properties directly for r MCS and e MCS, each yielding another notion of diagnosis. More work on this is required, but outside the scope of this article.

Tasharroﬁand Ternovska (2014) introduced the notion of supported equilibrium semantics, which requires a notion of support throughout contexts. In principle, this notion of support enables a new notion of diagnosis that also considers modiﬁcations of knowledge bases to restore global consistency. Preferences and ﬁlter may then be deﬁned on top of such a diagnosis notion.

An event-based approach to the semantics of MCS is given by Ellmauthaler and P uhrer (2014), where so-called asynchronous Multi-Context Systems (a MCS) are introduced. However, the semantics of a MCS is highly operational, which makes it rather difﬁcult to see how the declarative notion of diagnosis could be reasonably extended to this setting.

Jin, Wang, and Wen (2012) developed a framework for possibilistic reasoning in MCS termed poss-MCS where each context is a possibilistic logic program and information exchange is realized using possibilistic bridge rules. Intuitively, every (bridge) rule of a possibilistic context is an ordinary (bridge) rule that has an associated degree of necessity α [0, 1]. Based on those necessity degrees, possibilistic (local) models and possibilistic equilibria can be deﬁned. Although this potentially hints at using possibilistic equilibria for inconsistency resolution, it is shown that every possibilistic equilibrium is an ordinary equilibrium. Consequently, the notion of possibilistic equilibrium cannot remedy the absence of an ordinary equilibrium.

7.2.6 OTHER KR FORMALISMS

Clearly, the use of preferences to resolve inconsistency has been suggested and elaborated for rulebased systems and knowledge-exchange systems in numerous works before. We brieﬂy mention here two, but note that they are only remotely related to MCS.

EITER & WEINZIERL

Balduccini and Gelfond (2003) extended the ASP-based language A-Prolog with consistencyrestoring (CR) rules. Such rules are normally not applicable, but if the head restores consistency of an otherwise inconsistent ASP program, then a rule may become applicable. The semantics of CRProlog is given via a translation to abductive logic programs (cf. Kakas, Kowalski, & Toni, 1992) and takes a ranking over the CR rules into account. We note that consistency-restoring rules are similar in behavior to making a bridge rule condition-free. Hence, the diagnoses of an MCS under a speciﬁcally crafted preference order are capable of capturing the semantics of CR rules in certain cases. Peer-to-peer data integration systems, e.g. by Calvanese et al. (2004), allow for dynamically changing the data integration scenario in which peers can enter or leave the system anytime. An automatic approach for reasoning with inconsistent knowledge in a peer-to-peer system was presented by Binas and Mc Ilraith (2008) where knowledge from other peers is ranked according a preference order. A semantics is given in terms of extensions of a Dung-style abstract argumentation framework (Dung, 1995), which designates formulas that are distributed entailed . In principle, preference orders over diagnoses of an MCS can be used to simulate the ranking of formulas that occur in the head of bridge rules, yet this approach is limited to contexts where a notion of peer support can be deﬁned and successfully incorporated into the preference order.

8. Conclusion

In this work, we have addressed the problem of identifying and selecting those repairs of an inconsistent Multi-Context System (MCS) which are most preferred. In general, there can be by far too many possible repairs (also called diagnoses) such that they can all be manually inspected and a best one selected by hand. Supporting a preference mechanism to select appealing diagnoses is therefore vital for inconsistency management in MCS. To identify and select among all diagnoses of an MCS the most preferred ones, we have considered ﬁlters, which allow to discard diagnoses that do not fulﬁll certain criteria, and preference orders, which allow to compare diagnoses. As MCS are a ﬂexible framework for interlinking information from heterogeneous formalisms in different application contexts, in this spirit the user should have a choice for the formalism to specify both types of preferences. To achieve this, we followed an internalization approach: if the required conditions or preferences can be expressed via a context of an MCS, then they can be employed for the selection of preferred diagnoses, where in principle any (abstract) context logic may be used. To this end, several techniques for meta-reasoning about diagnoses in MCS have been developed which transform a given MCS M and a ﬁlter (resp., preference order) into an MCS M such that the diagnoses of M correspond one-to-one to the ﬁltered (resp., most-preferred) diagnoses of M. We ﬁrst presented ﬁlters and preference orders on diagnoses in their most general form, which allows to capture well-known formalisms for preferences speciﬁcation like CP-nets (Boutilier et al., 2004). We then presented an approach at meta-reasoning where a direct encoding of bridge rule modiﬁcations allows for perfect observation. The approach requires some enhanced notions of diagnosis, namely diagnoses where some bridge rules are protected and diagnoses where some bridge rules are considered to be of higher priority than the rest. An analysis of the computational complexity of these notions revealed that (subset-)minimal diagnoses with protected bridge rules have the same complexity as (subset-)minimal diagnoses; prioritized-minimal diagnoses have the same complexity, but are not sufﬁciently strong to characterize the most-preferred diagnoses in general. The respective

PREFERENCE-BASED INCONSISTENCY MANAGEMENT IN MULTI-CONTEXT SYSTEMS

MCS M and . . . Transformation Size Diagnosis notion Complexity

ﬁlter f Mf (Def. 13) linear D m(Mf, br P ) DP i total pref. order Mpl (Def. 16) exponential D m(Mpl , br P , br H) DP i preference order M (Def. 17) linear D m,tmax (M , br P , br H) ΠP i+1

Table 2: Overview of the meta-reasoning transformations to select ﬁltered and most-preferred diagnoses. Size is in terms of |br(M)|, and complexity wrt. context complexity of M if

CC(M) = ΣP i , i 1, and deciding f(D) ?= 1 resp. D D is in CC(M).

notion are mpm-diagnoses, which have higher complexity than subset-minimal diagnoses. On the other hand, identifying most-preferred diagnoses is as hard as identifying mpm-diagnoses; hence our meta-reasoning approach is worst-case optimal from a complexity point of view. Table 2 gives an overview of the developed meta-reasoning techniques and their respective overall complexities.

8.0.1 OUTLOOK

Regarding future work, some issues are still open. First, we currently allow arbitrary preferences on diagnoses, but these preferences cannot take the behavior of the repaired MCS into account. For example, a diagnosis of the hospital MCS might be less preferred if vital information is lost due to the diagnosis, e.g., a patient having some illness is known to the context with patient data, but the medication context suggests no treatment for the patient. In this case, the required preference cannot be deﬁned on sets of bridge rules alone, but one needs to take the resulting equilibrium into account. In principle, the meta-reasoning transformation presented here can be extended to consider also beliefs that result from the witnessing equilibrium, e.g. by adding protected bridge rules from all contexts of the original MCS to the observer context. Since a diagnosis possibly admits multiple equilibria, a correct encoding is neither obvious nor is it independent of the formalization of said preferences. Another issue concerns an implementation of the presented transformations as well as an implementation of the advanced notions for diagnosis selection. Due to our complexity results, one may in principle exploit the implementation of subset-minimal diagnoses in the MCS-IE tool by B ogl et al. (2010) and Eiter et al. (2014). The latter is based on encoding the diagnoses of an MCS to answer sets of a HEX-program as in the work of Eiter et al. (2010). HEX-programs extend ASP with an API-style interface to external information; this interface can be exploited to model the acceptability function of a range of context logics. As the encoding represents the removal resp. modiﬁcation of bridge rules by designated atoms (similar as in Lemma 4), it can be adapted to leave protected bridge rules untouched; consequently, the diagnoses with protected bridge rules, and by the system s ﬁltering the subset-minimal such diagnoses can be computed. Combined with our polynomial reductions for all but mpm-diagnoses to subset-minimal diagnoses, we can get an implementation of all advanced notions of diagnosis, except for mpm-diagnoses; moreover, even a distributed evaluation method (Salcher, 2016), based on the results by Dao-Tran, Eiter, Fink, and Krennwallner (2015) can be imagined. Practical restrictions and particular instantiations of the context logics will allow for additional optimizations, which however we did not consider in this foundational analysis of the problems. Indeed, such restrictions may also lower the complexity. For example, total prefer-

EITER & WEINZIERL

ence orders potentially warrant this, as on the one hand, for such orders the computationally easier notion of prioritized-minimal diagnoses is sufﬁcient to select the most-preferred diagnoses, and on the other hand, the hardness results for general preference orders rely on a non-total preference order. Further work is needed to reﬁne the picture in this regard.

Acknowledgements

We are grateful for the meticulous feedback we received from several anonymous reviewers and we thank them for their time and their suggestions that helped to improve this article signiﬁcantly. This work has been partially supported by by the Austrian Science Fund (FWF) project P27730 and the Academy of Finland, project 251170. Most of the contributions of the second author were done at TU Wien where initial investigations were also funded by the Vienna Science and Technology Fund (WWTF) under grant ICT08-020.

Appendix A. Proofs

A.1 Proofs of Section 3

Proof of Proposition 2. We ﬁrst show that DN(M) = D N (M). We write down DN(M) in setnotation and obtain:

DN(M) = {D D (M) | D D (M) : N |= D D (N |= D D )}

= {D D (M) | D D (M) : N |= D D N |= D D }

Regarding D N (M) we have that:

D N (M) = {D D (M) | D D (M) : (D N D D N D D = D)}

= {D D (M) | D D (M) : (N|= D D N|= D D D = D)}

= {D D (M) | D D (M) : N |= D D N |= D D D = D}

It remains to show that given any D, D D (M), the following two formulas are equivalent:

N |= D D N |= D D (15)

N |= D D N |= D D D = D (16)

Clearly, (15) implies (16), it thus remains to show that (16) implies (15). The latter clearly holds if N |= D D holds or N |= D D holds. Therefore, it only remains to show that in the case where both do not hold, (15) is implied by (16): from N |= D D and N |= D D follows D = D, hence by N |= D D it then follows that N |= D D , i.e., (15) is satisﬁed in this case. Consequently, (16) implies (15) and thus, both conditions are equivalent. Therefore, it holds that DN(M) = D N (M).

It then follows trivially from the deﬁnitions of D ird(M, N) and D m, N (M) that they are the same, because D ird(M, N) is the set of -minimal diagnoses of D N (M) while D m, N (M) is the set of -minimal diagnoses of DN(M).

PREFERENCE-BASED INCONSISTENCY MANAGEMENT IN MULTI-CONTEXT SYSTEMS

A.2 Proofs of Section 4

The following lemma shows that the applicable bridge rules of M under a diagnosis (D1, D2) add exactly those knowledge-base elements that are also added under the corresponding diagnosis (d1(D1), d2(D2) K) of Mmr(θ,Kp), where K Kp is arbitrary.

Lemma 6. Let M be an MCS and Mmr(θ,Kp) be a meta-reasoning encoding wrt. θ and Kp. Furthermore, let D1, D2 br(M), let K Kp, let S = (S1, . . . , Sn) be a belief state of M, and let S = (S1, . . . , Sn, Sn+1) be a belief state of Mmr(θ,Kp) where Sn+1 = {uncondr | r D2} {removedr | r D1}. Then, for all 1 i n, {ϕ (r) | r app(bri(M[D1, D2]), S)} = {ϕ (r) | r app(bri(Mmr(θ,Kp)[d1(D1), d2(D2) K]), S )}.

Proof. Let D1, D2 br(M), let K Kp, let S = (S1, . . . , Sn) be a belief state of M, and let S = (S1, . . . , Sn, Sn+1) be a belief state of Mmr(θ,Kp) where Sn+1 = {uncondr | r D2} {removedr | r D1}. Furthermore, let i be arbitrary such that 1 i n holds. We show that {ϕ (r) | r app(bri(Mmr(θ,Kp)[d1(D1), d2(D2) K]), S )} = {ϕ (r) | r app(bri(M[D1, D2]), S)} holds. : Let s {ϕ (r) | r app(bri(M[D1, D2]), S)}. Then s = ϕ (r) for some bridge rule r such that either r br(M) \ D1 and S r, or r = cf (r2) where r2 D2. In the former case, consider the bridge rule r1 of form (7) wrt. r. By construction, body(r1) = body(r) {not (n+1 : removedr)} and ϕ (r1) = ϕ (r). Since r / D1, removedr / Sn+1, and since S and S agree on Si for i {1, . . . , n}, i.e., S ={1,...,n} S , it follows that S r1. Therefore ϕ (r1) = ϕ (r) = s {ϕ (r) | r app(bri(Mmr(θ,Kp)[d1(D1), d2(D2) K]), S )}. In the latter case, where r = cf (r2) and r2 D2 hold, observe that r2 D2 implies that uncondr2 Sn+1. Consider the bridge rule r 2 of form (8) wrt. r2 and observe that ϕ (r 2) = ϕ (r2) = s while body(r 2) = {(n+1 : uncondr2)}. Since uncondr2 Sn+1, it holds that S r 2, hence s {ϕ (r) | r app(bri(Mmr(θ,Kp)[d1(D1), d2(D2) K]), S )}. Thus it follows that {ϕ (r) | r app(bri(M[D1, D2]), S)} {ϕ (r) | r app(bri(Mmr(θ,Kp)[d1(D1), d2(D2) K]), S )}. : Let s {ϕ (r) | r app(bri(Mmr(θ,Kp)[d1(D1), d2(D2) K]), S )}. Then there exists some r app(bri(Mmr(θ,Kp)[d1(D1), d2(D2) K]), S ) such that s = ϕ (r). Note that r either is of form (7) or of form (8). In the former case, it holds that S r and removedr1 / Sn+1 where r1 bri(M) and r is the bridge rule of form (7) wrt. r1. Since S and S agree on all belief sets from S1 to Sn, i.e., S ={1,...,n} S , and body(r) = body(r1) {not (n+1 : removedr)}, it holds that S r. Since removedr1 / Sn+1 it furthermore holds that r1 / D1. This implies that r1 bri(M[D1, D2]) and consequently it holds that r1 app(bri(M[D1, D2]), S), thus s = ϕ (r) = ϕ (r1) {ϕ (r) | r app(bri(M[D1, D2]), S)}. If r is of form (8), body(r) = {(n+1 : uncondr2)} where r2 bri(M) and r is the bridge rule of form (8) wrt. r2. Since r app(bri(Mmr(θ,Kp)[d1(D1), d2(D2) K]), S ) and r / d2(D2) K, it follows that S r, hence uncondr2 Sn+1 and thus r2 D2. Therefore, it holds that cf (r2) app(bri(M[D1, D2]), S) and consequently ϕ (r2) = ϕ (r) = s {ϕ (r) | r app(bri(M[D1, D2]), S)}. In both cases it holds that {ϕ (r) | r app(bri(Mmr(θ,Kp)[d1(D1), d2(D2) K]), S )} {ϕ (r) | r app(bri(M[D1, D2]), S)}.

The next lemma shows that every protected diagnosis of a meta-reasoning MCS is exhibited in the belief set of the observation context of every witnessing equilibrium of said diagnosis.

EITER & WEINZIERL

Lemma 7. Let M = (C1, . . . , Cn) be an MCS and Mmr(θ,Kp) = (C1, . . . , Cn, Cn+1) be a metareasoning encoding. Given that D1, D2 br(M), K Kp, and S = (S1, . . . , Sn, Sn+1) is a belief state of Mmr(θ,Kp),

Sn+1 ACCn+1(kbn+1 {ϕ (r) | r app(brn+1(Mmr(θ,Kp)[d1(D1), d2(D2) K]), S)})

holds iff Sn+1 = {uncondr | r D2} {removedr | r D1} and θ(D1, D2, K) holds.

Proof. By deﬁnition of ACCn+1 (cf. Deﬁnition 12)

Sn+1 ACCn+1(kbn+1 {ϕ (r) | r app(brn+1(Mmr(θ,Kp)[d1(D1), d2(D2) K]), S)})

holds iff Sn+1 = {removedr | r R1} {uncondr | r R2} and θ(R1, R2, R3) is true, where

R1 = {r br(M) | not removedr / H},

R2 = {r br(M) | uncondr H},

R3 = {r Kp | ϕ (r) H}, and

H = {ϕ (r) | r app(brn+1(Mmr(θ,Kp)[d1(D1), d2(D2) K]), S)}.

To prove this lemma, it therefore sufﬁces to show that R1 = D1, R2 = D2, and R3 = K. Consider the set B of bridge rules of context Cn+1 in the MCS resulting from the application of the diagnosis:

B = brn+1(Mmr(θ,Kp)[d1(D1), d2(D2) K])

= brn+1(Mmr(θ,Kp)) \ d1(D1) cf d2(D2) K

= d1(br(M)) d2(br(M)) Kp \ d1(D1) cf d2(D2) K .

Observe that every bridge rule r B is such that either body(r) = { } or body(r) = { }. Hence, for any belief state S the set of applicable bridge rules, call it Bapp, is exactly the set of rules whose body is . Formally,

Bapp = {r B | body (r) = { }} = app(brn+1(Mmr(θ,Kp)[d1(D1), d2(D2) K]), S).

Recall that r d1(br(M)) d1(D1) cf d2(D2) K implies that body(r) = { }, while r d2(br(M)) Kp implies that body(r) = { }. Therefore,

Bapp = d1(br(M)) \ d1(D1) cf d2(D2) K

and consequently it holds for the set H of heads of applicable bridge rules that

H = {ϕ (r) | r app(brn+1(Mmr(θ,Kp)[d1(D1), d2(D2) K]), S)}

= {ϕ (r) | r Bapp}

= {ϕ (r) | r d1(br(M)) \ d1(D1) cf (d2(D2) K) }

= {not removedr | r br(M) \ D1} {uncondr | r D2} {ϕ (r) | r K}.

Note that the heads of brn+1 are unique, i.e., for all r = r , r, r brn+1 holds ϕ (r) = ϕ (r ). This is because the bridge rules r of Kp all have unique head formulas ϕ (r) and the remaining

PREFERENCE-BASED INCONSISTENCY MANAGEMENT IN MULTI-CONTEXT SYSTEMS

bridge rules of brn+1 also have unique heads. Since the heads of brn+1 are unique, it holds for any r K Kp and r br(M) that uncondr = ϕ (r K) = not removedr and it also holds for any K Kp that the heads of K are unique. Consequently, it holds that

R1 = {r br(M) | not removedr / H} = {r br(M) | r D1} = D1 R2 = {r br(M) | uncondr H = {r br(M) | r D2} = D2 R3 = {r Kp | ϕ (r) H} = {r Kp | r K} = K.

Since it only remained to show that R1 = D1, R2 = D2, and R3 = K, the lemma is therefore proven.

Proof of Proposition 3. (1) Since Sn+1 = {uncondr | r D2} {removedr | r D1} and S = (S1, . . . , Sn, Sn+1), all pre-conditions of Lemma 7 and Lemma 6 are satisﬁed; hence we conclude the following.

By Lemma 7, θ(D1, D2, K) holds iff

Sn+1 ACCn+1 kbn+1

{ϕ (r) | r app(brn+1(Mmr(θ,Kp)[d1(D1), d2(D2) K]), S )} . (17)

By Lemma 6, for all 1 i n holds

{ϕ (r) | r app(bri(Mmr(θ,Kp)[d1(D1), d2(D2) K]), S )}

= {ϕ (r) | r app(bri(M[D1, D2]), S)}.

which implies that for all 1 i n it holds that

ACCi(kbi {ϕ (r) | r app(bri(Mmr(θ,Kp)[d1(D1), d2(D2) K]), S ))})

= ACCi(kbi {ϕ (r) | r app(bri(M[D1, D2]), S)}).

This in turn implies that for all 1 i n, it holds that

Si ACCi(kbi {ϕ (r) | r app(bri(Mmr(θ,Kp)[d1(D1), d2(D2) K]), S ))})

iff Si ACCi(kbi {ϕ (r) | r app(bri(M[D1, D2]), S)}). (18)

From (18) and (17) we therefore obtain that: θ(D1, D2, K) holds and for all 1 i n it holds that Si ACCi(kbi {ϕ (r) | r app(bri(M[D1, D2]), S) if and only if for all 1 j n + 1 it holds that

Si ACCi(kbi {ϕ (r) | r app(bri(Mmr(θ,Kp)[d1(D1), d2(D2) K]), S ))}).

This is equivalent to: θ(D1, D2, K) and S EQ(M[D1, D2]) hold iff it holds that S EQ(Mmr(θ,Kp)[d1(D1), d2(D2) K]).

(2) This is a direct consequence of (1) and the fact that a diagnosis implies the existence of a witnessing equilibrium and vice versa, i.e., (D1, D2) D (M) iff there exists a belief state S EQ(M[D1, D2]), for any M, D1, D2, and S. Thus

EITER & WEINZIERL

(D1, D2) D (M) and θ(D1, D2, K) hold iff θ(D1, D2, K) and (S1, . . . , Sn) EQ(M[D1, D2]) hold iff (by (1)) (S1, . . . , Sn, Sn+1) EQ(Mmr(θ,Kp)[d1(D1), d2(D2) K]) holds iff (d1(D1), d2(D1) K) D (Mmr(θ,Kp)) holds.

It remains to show that (d1(D1), d2(D1) K) D (Mmr(θ,Kp)) iff (d1(D1), d2(D1) K) D (Mmr(θ,Kp), br P ). This follows from (d1(D1) d2(D2) K) br P = (see Deﬁnition 12) and Proposition 1, which shows that D (Mmr(θ,Kp), br P ) D (Mmr(θ,Kp)), i.e, every diagnosis with protected bridge rules also is a diagnosis.

The following lemma shows that the bridge rules of context Cn+1 in the MCS Mmr(θ,Kp) are such that for a minimal diagnosis (D1, D2) D m(Mmr(θ,Kp), br P ), a bridge rule r with body(r) = { } is only contained in D1 (or not modiﬁed at all), and a bridge rule r with body(r) = { } is only contained in D2 (or not modiﬁed at all).

Lemma 8. Let Mmr(θ,Kp) be a meta-reasoning encoding with protected bridge rules br P , and let (D1, D2) D m(Mmr(θ,Kp), br P ). Then, for every r br(Mmr(θ,Kp)) \ br P holds that:

(i) body(r) = { } implies r / D2 and

(ii) body(r) = { } implies r / D1.

Proof. Since (D1, D2) D m(Mmr(θ,Kp), br P ), there exists a witnessing equilibrium S EQ(Mmr(θ,Kp)[D1, D2]) of (D1, D2). Since (D1, D2) is a diagnosis with protected bridge rules, it holds that (D1 D2) br P = , which by construction of Mmr(θ,Kp) implies that r brn+1. For a proof by contradiction, we now show the following:

(i) if body(r) = { } and r D2 then (D1 \ {r}, D2 \ {r}) D (Mmr(θ,Kp), br P );

(ii) if body(r) = { } and r D1 then (D1 \ {r}, D2) D (Mmr(θ,Kp), br P ).

To show that the respective smaller diagnosis admits a witnessing equilibrium it sufﬁces in the following to consider only applicable bridge rules of Cn+1, because it is the only context of Mmr(θ,Kp)

with bridge rules that are not protected.

(i) Case body(r) = { } and r D2. Then

ϕ (r) {ϕ (r) | r app(brn+1(Mmr(θ,Kp)[D1, D2]), S)}

since cf (r) app(brn+1(Mmr(θ,Kp)[D1, D2]), S). Now consider (D1 \ {r}, D2 \ {r}) (D1, D2) and observe that r app(brn+1(Mmr(θ,Kp)[D1 \ {r}, D2 \ {r}]), S) since r is a bridge rule of the modiﬁed system and body(r) = { }. Thus, S EQ(Mmr(θ,Kp)[D1 \ {r}, D2 \ {r}]) and (D1 \ {r}, D2 \ {r}) D (Mmr(θ,Kp), br P ). Note that this reasoning applies regardless of whether r D1 holds.

(ii) Case body(r) = { } and r D1. Then

app(brn+1(Mmr(θ,Kp)[D1 \ {r}, D2]), S) = app(brn+1(Mmr(θ,Kp)[D1, D2]), S)

PREFERENCE-BASED INCONSISTENCY MANAGEMENT IN MULTI-CONTEXT SYSTEMS

since r either is not applicable (left-hand side), or it is not a bridge rule of the modiﬁed MCS (right-hand side). Consequently, S EQ(Mmr(θ,Kp)[D1 \ {r}, D2]) and therefore (D1 \ {r}, D2) D (Mmr(θ,Kp), br P ).

Each of these statements contradicts that (D1, D2) D m(Mmr(θ,Kp), br P ), hence the statement of the lemma follows.

The following lemma shows that there are no diagnoses in D m(Mmr(θ,Kp), br P ) other than those which correspond to diagnoses of M.

Lemma 9. Let M be an MCS and Mmr(θ,Kp) be some meta-reasoning encoding for M. For every (R1, R2) D m(Mmr(θ,Kp), br P ) there exist D1, D2 br(M) and K Kp such that R1 = d1(D1) and R2 = d2(D2) K.

Proof. Recall that br P contains all bridge rules of form (7) and (8), hence the only bridge rules not in br P are those of brn+1, because br Mmr(θ,Kp) = br P brn+1. Since brn+1 = d1(br(M)) d2(br(M)) Kp, it follows directly that for every (R1, R2) D m(Mmr(θ,Kp), br P ) there exist D1, D 1, D2, D 2 br(M) and K, K Kp such that R1 = d1(D1) d2(D 1) K and R2 = d1(D 2) d2(D2) K. Observe that for all r d2(D 1) K it holds that body(r) = { }, hence by Lemma 8 it follows that d2(D 1) K = . Furthermore, it holds for all r d1(D 2) that body(r) = { }, hence by Lemma 8 it follows that d1(D 2) = . Together, this means that D 1 = D 2 = K = and therefore it holds for every (R1, R2) D m(Mmr(θ,Kp), br P ) that there exist D1, D2 br(M) and K Kp such that R1 = d1(D1) and R2 = d2(D2) K.

Proof of Propostion 4. By deﬁnition of minimal diagnosis, it holds that

D m(Mmr(θ,Kp), br P ) =

{(R1, R2) | (R1, R2) D (Mmr(θ,Kp), br P )

and there exists no (R 1, R 2) D (Mmr(θ,Kp), br P )

such that (R 1, R 2) (R1, R2)}

By Lemma 9, it holds for every (R1, R2) D m(Mmr(θ,Kp), br P ) that there exist D1, D2 br(M) and K Kp such that R1 = d1(D1) and R2 = d2(D2) K, hence we obtain that

D m(Mmr(θ,Kp), br P ) =

{(d1(D1), d2(D2) K) | (d1(D1), d2(D2) K) D (Mmr(θ,Kp), br P )

and there exists no (d1(D 1), d2(D 2) K ) D (Mmr(θ,Kp), br P )

such that (d1(D 1), d2(D 2) K ) (d1(D1), d2(D2) K)

holds for some K, K Kp}

EITER & WEINZIERL

By Proposition 3 we know that (d1(D1), d2(D2) K) D (Mmr(θ,Kp), br P ) holds iff (D1, D2) D (M) and θ(D1, D2, K) hold. Therefore we obtain

D m(Mmr(θ,Kp), br P ) =

{(d1(D1), d2(D2) K) | (D1, D2) D (M) and θ(D1, D2, K) holds

and there exists no (D 1, D 2) D (M) such that

(d1(D 1), d2(D 2) K ) (d1(D1), d2(D2) K) and θ(D 1, D 2, K )

holds for some K, K Kp}.

Since d1 and d2 are bijective, (d1(D 1), d2(D 2) K ) (d1(D1), d2(D2) K) holds iff (D 1, D 2 K ) (D1, D2 K) holds.

D m(Mmr(θ,Kp), br P ) =

{(d1(D1), d2(D2) K) | (D1, D2) D (M) and θ(D1, D2, K) holds

and there exists no (D 1, D 2) D (M) such that

(D 1, D 2 K ) (D1, D2 K) and θ(D 1, D 2, K )

holds for some K, K Kp}.

Proof of Proposition 5. From Proposition 4 we know that

D m(Mmr(θ,Kp), br P ) ={(d1(D1), d2(D2) K) | (D1, D2) D (M), θ(D1, D2, K) holds, (D 1, D 2) D (M), K Kp :

(D 1, D 2 K ) (D1, D2 K) and θ(D 1, D 2, K )holds }.

Because θ is functional increasing, it holds that (D 1, D 2 K ) (D1, D2 K) holds iff (D 1, D 2) (D1, D2). We therefore obtain that:

D m(Mmr(θ,Kp), br P ) =

{(d1(D1), d2(D2) K) | (D1, D2) D (M) and θ(D1, D2, K) holds

and there exists no (D 1, D 2) D (M) such that

(D 1, D 2) (D1, D2) and θ(D 1, D 2, K ) holds for some K, K Kp}.

A.3 Proofs of Section 5

A.3.1 PROOFS OF SECTION 5.1

Proof of Theorem 1. Recall that Mf = Mmr(θ,Kp) where θ is deﬁned such that θ(D1, D2, ) holds iff it holds that f(D1, D2) = 1, hence θ is functional increasing. By Lemma 5 it therefore holds that

D m(Mmr(θ,Kp), br P ) =

{(d1(D1), d2(D2) K) | (D1, D2) D (M) and θ(D1, D2, K) holds

and there exists no (D 1, D 2) D (M) such that

(D 1, D 2) (D1, D2) and θ(D 1, D 2, K ) holds for some K , K Kp}

PREFERENCE-BASED INCONSISTENCY MANAGEMENT IN MULTI-CONTEXT SYSTEMS

which in case of Mf becomes

D m(Mf, br P ) = {(d1(D1), d2(D2)) | (D1, D2) D (M) and θ(D1, D2, ) holds

and there exists no (D 1, D 2) D (M) such that

(D 1, D 2) (D1, D2) and θ(D 1, D 2, ) holds}.

By deﬁnition of Mf it furthermore holds that θ(D1, D2, ) holds iff f(D1, D2) = 1, hence we obtain that

D m(Mf, br P ) = {(d1(D1), d2(D2)) | (D1, D2) D (M) and f(D1, D2) = 1

and there exists no (D 1, D 2) D (M) such that

(D 1, D 2) (D1, D2) and f(D 1, D 2) = 1}

Applying the deﬁnition of minimal-ﬁltered diagnoses, we thus obtain that

D m(Mf, br P ) = {(d1(D1), d2(D2)) | (D1, D2) D m,f(M)}.

Note that this statement is equivalent to

D m,f(M) = {(D1, D2) | (d1(D1), d2(D2)) D m(Mf, br P )}.

A.3.2 PROOFS OF SECTION 5.2

Proof of Lemma 1. : Suppose that (D1, D2) (D 1, D 2). We have to show that for every K mapg (D1, D2) it holds that K mapg (D 1, D 2). Let K mapg (D1, D2) hold. Then it follows by deﬁnition that K = g(D 1, D 2) for some (D 1, D 2) 2br(M) 2br(M). In the case that (D 1, D 2) = (D1, D2) it follows from the reﬂexivity of that (D 1, D 2) (D 1, D 2) and thus by deﬁnition of mapg (D 1, D 2) it holds that K mapg (D 1, D 2). In the case that (D 1, D 2) = (D1, D2) it follows by the deﬁnition of mapg (D1, D2) that (D 1, D 2) (D1, D2). Since (D1, D2) (D 1, D 2) and is transitive, it follows that (D 1, D 2) (D 1, D 2) and consequently, it holds that K mapg (D 1, D 2). Thus for any K mapg (D1, D2) it holds that K mapg (D 1, D 2), i.e., mapg (D1, D2) mapg (D 1, D 2). : Suppose that mapg (D1, D2) mapg (D 1, D 2). We have to show that (D1, D2) (D 1, D 2). By reﬂexivity of it holds that g(D1, D2) mapg (D1, D2), thus g(D1, D2) mapg (D1, D2) and consequently g(D1, D2) mapg (D 1, D 2). By deﬁnition of mapg (D 1, D 2) it then follows that (D1, D2) (D 1, D 2).

The following lemma shows that the set D m(Mpl , br P ) of minimal diagnoses with protected bridge rules of Mpl corresponds to those diagnoses of M which are at the same time, preferred according to and -minimal. These diagnoses not yet correspond to minimal -preferred diagnoses since preference among -incomparable diagnoses is not captured by D m(Mpl , br P ).

Lemma 10. Given an MCS M and a preference on its diagnoses, it holds that

D m(Mpl , br P ) = {(d1(D1), d2(D2) K) | (D1, D2) D (M)

K = mapg (D1, D2) (D 1, D 2) D (M) : (D 1, D 2) (D1, D2) (D 1, D 2) (D1, D2) (D1, D2) = (D 1, D 2)}.

EITER & WEINZIERL

Proof. By Proposition 4 it holds that:

D m(Mmr(θ,Kp), br P ) =

{(d1(D1), d2(D2) K) | (D1, D2) D (M) and θ(D1, D2, K) holds

and there exists no (D 1, D 2) D (M) such that

(d1(D 1), d2(D 2) K ) (d1(D1), d2(D2) K) and

θ(D 1, D 2, K ) holds for some K Kp}

= {(d1(D1), d2(D2) K) | (D1, D2) D (M) θ(D1, D2, K) (D 1, D 2) D (M): K : θ(D 1, D 2, K )

(d1(D 1), d2(D 2) K ) (d1(D1), d2(D2) K)

(d1(D 1), d2(D 2) K ) = (d1(D1), d2(D2) K)}

Next we substitute θ by its deﬁnition, i.e., θ(D1, D2, K) iff mapg (D1, D2) = K.

D m(Mmr(θ,Kp), br P ) = {(d1(D1), d2(D2) K) | (D1, D2) D (M)

mapg (D1, D2) = K (D 1, D 2) D (M): K : mapg (D 1, D 2) = K

(d1(D 1), d2(D 2) K ) (d1(D1), d2(D2) K)

(d1(D 1), d2(D 2) K ) = (d1(D1), d2(D2) K)}

Since d1 and d2 both are bijective, mapg (D1, D2) = K, and mapg (D 1, D 2) = K , it follows that (d1(D 1), d2(D 2) K ) = (d1(D1), d2(D2) K) holds iff (D 1, D 2) = (D1, D2). Hence,

D m(Mmr(θ,Kp), br P ) = {(d1(D1), d2(D2) K) | (D1, D2) D (M)

mapg (D1, D2) = K (D 1, D 2) D (M): K : (mapg (D 1, D 2) = K

(d1(D 1), d2(D 2) K ) (d1(D1), d2(D2) K)

(D1, D2) = (D 1, D 2)}

Towards the next step, we need to show that the following holds true for (D1, D2) D (M), (D 1, D 2) D (M), and mapg (D1, D2) = K:

mapg (D 1, D 2) = K (d1(D 1), d2(D 2) K ) (d1(D1), d2(D2) K)

(D1, D2) = (D 1, D 2) (19)

iff (D 1, D 2) (D1, D2) (D 1, D 2) (D1, D2)

(D1, D2) = (D 1, D 2) (20)

Observe that (d1(D 1), d2(D 2) K ) (d1(D1), d2(D2) K) holds iff (D 1, D 2) (D1, D2) and K K both hold. By Lemma 1 it further holds that K = mapg (D 1, D 2) mapg (D1, D2) = K iff (D 1, D 2) (D1, D2). Therefore, (19) holds iff (20) holds. After substitution, it therefore holds

PREFERENCE-BASED INCONSISTENCY MANAGEMENT IN MULTI-CONTEXT SYSTEMS

D m(Mpl , br P ) = {(d1(D1), d2(D2) K) | (D1, D2) D (M)

mapg (D1, D2) = K (D 1, D 2) D (M) : (D 1, D 2) (D1, D2) (D 1, D 2) (D1, D2) (D1, D2) = (D 1, D 2)}

Proof of Theorem 2. In the following, let θ, Kp, and mapg be according to Mpl = Mmr(θ,Kp). : Let (R1, R2) D (Mpl , br P , br H), i.e., (R1, R2) D m(Mpl , br P ) and for all (R 1, R 2) D m(Mpl , br P ) holds that (R 1, R 2) br H (R1, R2) (R 1, R 2) =br H (R1, R2). By Lemma 10 it holds that (R1, R2) = (d1(D1), d2(D2) K) where K = mapg (D1, D2) and (D1, D2) D (M). To show that (D1, D2) D m, (M), we have to show that (D1, D2) is -preferred and subset minimal among all -preferred diagnoses. Assume that (D1, D2) is not - preferred. Then by (4) there exists a diagnosis (D 1, D 2) D (M) such that (D 1, D 2) (D1, D2) and (D1, D2) (D 1, D 2) hold. Let mapg (D 1, D 2) = K and mapg (D1, D2) = K. Since it holds that (D 1, D 2) (D1, D2) it follows from Lemma 1 that K K. From (D1, D2) (D 1, D 2) it also follows by the same lemma that K K holds and thus K K holds. This means that (R 1, R 2) = (d1(D 1), d2(D 2) K ) br H (d1(D1), d2(D2) K) = (R1, R2) holds. Now suppose (R 1, R 2) D m(Mpl , br P ) holds; then (R1, R2) D (Mpl , br P , br H) contradicts that (R 1, R 2) br H (R1, R2). On the other hand, (R 1, R 2) / D m(Mpl , br P ) implies that some (R 1, R 2) D m(Mpl , br P ) exists with (R 1, R 2) (R 1, R 2), i.e., there exist D 1, D 2 br(M) such that (D 1, D 2) (D 1, D 2) (D1, D2) and K K K both hold where K = mapg (D 1, D 2), R 1 = d1(D 1), and R 2 = d2(D 2) K . Since K K it therefore holds that (R 1, R 2) br H (R1, R2) and together with (R 1, R 2) D m(Mpl , br P ) this contradicts that (R1, R2) D (Mpl , br P , br H). Since every case yields a contradiction, it therefore follows that there exists no such (D 1, D 2), i.e., (D1, D2) indeed is a -preferred diagnosis. It remains to show that (D1, D2) is subset-minimal among all -preferred diagnoses. Towards contradiction, assume there exists (D 1, D 2) D (M) such that (D 1, D 2) (D1, D2). We distinguish on how relates (D1, D2) and (D 1, D 2).

case (D1, D2) (D 1, D 2) (D 1, D 2) (D1, D2): since (R1, R2) D m(Mpl , br P ), it holds by Lemma 10 that (D 1, D 2) (D1, D2) (D 1, D 2) (D1, D2) (D 1, D 2) = (D1, D2) which directly contradicts that (D 1, D 2) (D1, D2).

case (D1, D2) (D 1, D 2) (D 1, D 2) (D1, D2): in this case, (D 1, D 2) is not -preferred, because (D1, D2) (D 1, D 2). Hence, it contradicts that (D 1, D 2) D (M).

case (D1, D2) (D 1, D 2) (D 1, D 2) (D1, D2): this case is analogous to the ﬁrst one, i.e., (R1, R2) D m(Mpl , br P ) contradicts that (D 1, D 2) (D1, D2) and (D 1, D 2) (D1, D2) both hold.

case (D1, D2) (D 1, D 2) (D 1, D 2) (D1, D2): this case contradicts with being total.

Consequently, there exists no (D 1, D 2) D (M) such that (D 1, D 2) (D1, D2) and therefore it holds that (D1, D2) D m, (M).

EITER & WEINZIERL

: Let (D1, D2) D m, (M). We have to show that

(d1(D1), d2(D2) K) D (Mpl , br P , br H)

holds with mapg (D1, D2) = K. By deﬁnition, it holds that

D (Mpl , br P , br H) = {D D m(Mpl , br P ) | D D m(Mpl , br P ) :

D br H D D =br H D}.

While by Lemma 10 it holds that:

D m(Mpl , br P ) = {(d1(D1), d2(D2) K) | (D1, D2) D (M)

K = mapg (D1, D2) (D 1, D 2) D (M) : (D 1, D 2) (D1, D2) (D 1, D 2) (D1, D2) (D1, D2) = (D 1, D 2)}.

Observe that br H = Kp and d1(br(M)) d2(br(M)) Kp = , hence (d1(D1), d2(D2) K) br H (d1(D 1), d2(D 2) K ) holds iff K K holds. Therefore, it also holds that:

D (Mpl , br P ) = {(d1(D1), d2(D2) K) D m(Mpl , br P ) | (21)

(D 1, D 2) D (M) : (D 1, D 2) D (M) : (D 1, D 2) (D 1, D 2)

(D 1, D 2) (D 1, D 2) (D 1, D 2) = (D 1, D 2)

mapg (D 1, D 2) K K = mapg (D 1, D 2) }.

First, we show that (d1(D1), d2(D2) K) D m(Mpl , br P ), which by Lemma 10 holds iff the following holds: (D1, D2) D (M) mapg (D1, D2) = K (D 1, D 2) D (M) : (D 1, D 2) (D1, D2) (D 1, D 2) (D1, D2) (D1, D2) = (D 1, D 2). Since it holds that (D1, D2) D m, (M), it also holds that (D1, D2) D (M), and K = mapg (D1, D2) by construction. It remains to show that (D 1, D 2) D (M) : (D 1, D 2) (D1, D2) (D 1, D 2) (D1, D2)

(D1, D2) = (D 1, D 2). Assume towards contradiction that there exists some (D 1, D 2) D (M) such that (D 1, D 2) (D1, D2) (D 1, D 2) (D1, D2) and (D1, D2) = (D 1, D 2), i.e., it holds for (D 1, D 2) that (D 1, D 2) (D1, D2) (D 1, D 2) (D1, D2). We distinguish whether (D1, D2) (D 1, D 2) also holds: if (D1, D2) (D 1, D 2) holds, (D 1, D 2) is -preferred since (D1, D2) is. Since (D1, D2) D m, (M), (D1, D2) is subset-minimal among all -preferred diagnoses, which contradicts that (D 1, D 2) (D1, D2) holds. In the case that (D1, D2) (D 1, D 2), it holds that (D1, D2) D (M), since it holds that (D 1, D 2) (D1, D2) (D1, D2) = (D 1, D 2) (D1, D2) (D 1, D 2). This contradicts that (D1, D2) D m, (M). Hence it follows that no such (D 1, D 2) exists. Consequently, it holds that (d1(D1), d2(D2) K) D m(Mpl , br P ). According to (21), it remains to show that for all (D 1, D 2) D (M) it holds that

(D 1, D 2) D (M) : (D 1, D 2) (D 1, D 2) (D 1, D 2) (D 1, D 2)

(D 1, D 2) = (D 1, D 2) mapg (D 1, D 2) K K = mapg (D 1, D 2) .

PREFERENCE-BASED INCONSISTENCY MANAGEMENT IN MULTI-CONTEXT SYSTEMS

Towards contradiction, assume there exists (D 1, D 2) D (M) such that (D 1, D 2) D (M) : (D 1, D 2) (D 1, D 2) (D 1, D 2) (D 1, D 2) (D 1, D 2) = (D 1, D 2) holds and also mapg (D 1, D 2) K holds. Since mapg (D 1, D 2) K, it follows by Lemma 1 that (D 1, D 2) (D1, D2) and (D1, D2) (D1 , D2 ) both hold, which implies (D1, D2) / D m, (M), in contradiction to the assumption. Therefore, no such (D 1, D 2) can exist. This proves that (d1(D1), d2(D2) K) D (Mpl , br P , br H), which completes the proof.

A.3.3 PROOFS OF SECTION 5.3

Proof of Lemma 2. Observe that I is a bijection on {1, . . . , n} which simply renames context identiﬁers. Therefore, one can directly conclude that S EQ(M) holds iff I(S) EQ(I(M)) holds. In the following, we show in full detail that this renaming indeed is correct. Let S = (S1, . . . , Sn) and I(S) = (SI 1(1), . . . , SI 1(n)) = (S 1, . . . , S n). and let 1 i n. Note that S EQ(M) holds iff for all 1 i n it holds that Si ACCi(kbi app(bri(M), S)); additionally I(S) EQ(I(M)) holds iff for all 1 j n holds Sj ACCj(kbj app(brj(I(M), I(S)). Given that I is bijective and compatible to M, there exists j {1, . . . , n} for every i {1, . . . , n} such that j = I(i) and vice versa, i.e., for every j {1, . . . , n} exists a i {1, . . . , n} such that i = I 1(j). We now show that for any 1 i, j n such that j = I(i) it holds that Si ACCi(kbi app(bri(M), S) iff Sj ACCj(kbj app(brj(I(M)), I(S)). Observe that by construction of I(M) it holds that Si = Sj, ACCi = ACCj, and kbi = kbj. Hence it sufﬁces to show that app(bri(M), S) = app(brj(I(M)), I(S)). Note that brj(I(M)) = I(bri(M)), hence there exists a bijection from brj(I(M)) to bri(M), namely I; furthermore I also maps bijectively each r bri(M) and every (c : p) body (r) to I(r) and (I(c) : p). Since ϕ (r) = ϕ (I(r)) it sufﬁces to show that p Sc holds iff p S I(c) holds. This is true since S I(c) = SI 1(I(c)) = Sc, thus it follows that app(bri(M), S) = app(brj(I(M)), I(S)) which in turn implies that S EQ(M) iff I(S) EQ(I(M)). From this we also conclude that S EQ(M[D1, D2]) holds iff I(S) EQ(I(M[D1, D2])) holds, because M[D1, D2] is an MCS, hence the above statement also applies to M[D1, D2].

To show that the set of diagnoses of M M is the product of the set of diagnoses of M and of M , we use the following lemma, which states that if M has no bridge rules, the set of diagnoses of M coincides with the set of diagnoses of M M .

Lemma 11. Given an MCS M = (C1, . . . , Cn) and an MCS M = (C 1, . . . , C m) with br(M ) = . Then for every belief state (S1, . . . , Sn) of M exist belief sets Sn+1, . . . , Sn+m such that (S1, . . . , Sn+m) EQ(M M ) holds iff (S1, . . . , Sn) EQ(M) holds.

Proof. Let Mo = M M . : Let S = (S1, . . . , Sn+m) EQ(M M ) be such that for every 1 i n + m holds Si ACCi(kbi app(bri(Mo), S)). Note that by construction of Mo it holds for every bridge rule r bri(Mo) with 1 i n that (c : p) body (r) implies that c {1, . . . , n} holds. Hence by bri(Mo) = bri(M) follows that app(bri(Mo), S) = app(bri(M), (S1, . . . , Sn)). Therefore, for all i C (M) it holds that Si ACCi(kbi app(bri(M), (S1, . . . , Sn))), i.e., (S1, . . . , Sn) EQ(M). : Let S = (S1, . . . , Sn) EQ(M) hold. Since br(M ) = , it holds for all n + 1 j n + m that brj(Mo) = . Recall that contexts are consistent without bridge rules, i.e., there exists S j ACCj(kbj ) for all n + 1 j n + m. Consider the belief state S =

EITER & WEINZIERL

(S1, . . . , Sn, S n+1, . . . , S n+m) and observe that for all 1 i n it holds that app(bri(Mo), S ) = app(bri(M), S) since bri(Mo) = bri(M). It therefore follows that S EQ(Mo) holds.

Since shifting has no inﬂuence on acceptability, we can turn around the above lemma to show that the set of diagnoses of M M equals the set of diagnoses of M if br(M) = .

Corollary 3. Given an MCS M = (C1, . . . , Cn) and an MCS M = (C 1, . . . , C n ) with br(M) = . Then, for every belief state (S 1, . . . , S n ) of M exist belief sets S1, . . . , Sn such that (S1, . . . , Sn, S 1, . . . , S n ) EQ(M M ) holds iff (S 1, . . . , S n ) EQ(M ) holds.

Proof. Consider a permutation I that exchanges the positions of contexts of M and M in M M , formally: let I be the permutation wrt. M M and recall that I is compatible with M M . Let I = I 1 and Ms = I (M M ). Note that Ms equals M M, hence by Lemma 2 we obtain that (S1, . . . , Sn, S 1, . . . , S n ) EQ(M M ) iff I ((S1, . . . , Sn, S 1, . . . , S n )) EQ(Ms) iff (S 1, . . . , S n , S1, . . . , Sn) EQ(M M). Since br(M) = it holds by Lemma 11 that for every belief state (S 1, . . . , S n ) of M exist belief sets Sn +1, . . . , Sn +n such that (S 1, . . . , S n , Sn +1, . . . , Sn +n) EQ(M M) holds iff (S 1, . . . , S n ) EQ(M ) holds. In summary, (S1, . . . , Sn, S n+1, . . . , S n+n ) EQ(M M ) holds iff (S n+1, . . . , S n+n ) EQ(M ) holds.

The proof of Proposition 6 makes use of Lemma 4 and Lemma 5 occurring in the appendix of the work by Eiter et al. (2014) about splitting sets in MCS. For convenience, we recap them here as well as the deﬁnition of a splitting set (which is similar to the notion of a splitting set in answer-set programming).

Deﬁnition 20 (cf. Eiter et al., 2014). A set of contexts U C (M) is a splitting set of an MCS M, if every rule r br(M) is such that Ch (r) U satisﬁes Cb (r) U. More formally, U is a splitting set iff U S {Cb (r) | r br(M), Ch (r) U}.

Lemma 12 (cf. Eiter et al., 2014). Let U be a splitting set of an MCS M and let R1, R2 br(M). Then, U is also a splitting set of M[R1 cf (R2)].

Lemma 13 (cf. Eiter et al., 2014). Let M be an MCS, let B be a set of bridge rules compatible with M, and let U be a splitting set for M[B]. Furthermore, let S = (S1, . . . , Sn) and S = (S 1, . . . , S n) be belief states of M, and let b U R B. Then, S =U S and i U implies ACCi(kbi app(bri(M[B]), S)) = ACCi(kbi app(bri(M[R]), S )).

Proof of Proposition 6. W.l.o.g. let M = (C1, . . . , Cn), let M = (C 1, . . . , C n ), and let Mo = M M . Observe that by construction, there is no bridge rule whose head belongs to M (resp. M ) and whose body contains a belief from M (resp. M). Consequently, U = {1, . . . , n} and U = {n + 1, . . . , n + n } = C (Mo) \ U are both splitting sets of Mo. Let S = (S 1, . . . , S n+n ) be an equilibrium of Mo[ ], which exists by our assumption that all contexts (of M and M ) are consistent without bridge rules; additionally let B = br(Mo) \ D1 cf (D2). : Let (D1, D2) D (Mo) hold. Then there exists a belief state S = (S1, . . . , Sn+n ) such that for every 1 i n + n it holds that Si ACCi(kbi app(bri(Mo[D1, D2]), S)). Consider SU = (S1, . . . , Sn, S n+1, . . . , S n+n ) and observe that SU =U S; hence by Lemma 13 it follows for all i U that

ACCi(kbi app(bri(Mo[B]), S)) = ACCi(kbi app(bri(Mo[R]), SU))

PREFERENCE-BASED INCONSISTENCY MANAGEMENT IN MULTI-CONTEXT SYSTEMS

holds for all b U R B, speciﬁcally for R = b U. Note that U, U , and b U meant here are relative to the MCS Mo[B], where by Lemma 12 U and U are also splitting sets of Mo[B]. Consequently, for all i U it holds that Si ACCi(kbi app(bri(Mo[b U]), SU)) and for all j C (Mo) \ U it holds that S j ACCj(kbj app(brj(Mo[b U]), SU)), because brj(Mo[b U]) = ; thus it holds that SU EQ(Mo[b U]). Recall that b U is deﬁned relative to Mo[B], hence b U = br(M) \ (D1 br(M)) cf (D2 br(M)), i.e., for A1 = D1 br(M) and A2 = D2 br(M) it holds that Mo[b U] = Mo[br(M)\A1 cf (A2)] and it follows that SU EQ(Mo[br(M)\A1 cf (A2)]), i.e., it holds that (A1, A2) D (Mo[br(M)]). Since Mo[br(M)] = M M [ ], Lemma 11 applies, i.e., it holds that (S1, . . . , Sn) EQ(M[A1, D2]) and we conclude that (A1, A2) D (M). The proof that (B1, B2) D (M ) for B1 = D1 I(br(M )) and B2 = D2 I(br(M )) is analogous; it is based on the belief state SU = (S 1, . . . , S n, Sn+1, . . . , Sn+n ) which is a witness of (I(B1), I(B2)) D (Mo[b U ]); applying Corollary 3 (for (M M )[b U ] = M M [B1, B2]) then yields that (B1, B2) D (M ). : Let (A1, A2) D (M) and (B1, B2) D (M ) hold. Then there exists some SA = (SA 1 , . . . , SA n ) EQ(M[A1, A2]) and SB = (SB 1 , . . . , SB n ) EQ(M [B1, B2]). Consider the belief state S = (S1, . . . , Sn+n ) such that Si = SA i for 1 i n and Sn+j = SB j for 1 j n . Observe that S is a belief state of the MCS Md = Mo[A1 I(B1), A2 I(B2)]. Thus it sufﬁces to show S EQ(Md), because this implies that (A1 I(B1), A2 I(B2)) D (M M ). We ﬁrst show that for all 1 i n it holds that Si ACCi(kbi app(bri(Md), S)). Let B = br(Md); hence Md = Md[B], and note that U and U are splitting sets of Md[B] by Lemma 12. Next we consider Md[b U] (with b U relative to Md) and R = b U. Since Md[R] = Md[b U] = (M[A1, A2] M [ ]) and SA EQ(M[A1, A2]), it holds by Lemma 11 that there exist S n+1, . . . , S n+n such that SM = (S1, . . . , Sn, S n+1, . . . , S n+n ) EQ(M[A1, A2] M [ ]), i.e., for all 1 i n it holds that Si ACCi(kbi app(bri(Md[R]), SM)) It holds that SM =U S and b U R B; hence by Lemma 13 it holds for all 1 i n that ACCi(kbi app(bri(Md[B]), S)) = ACCi(kbi app(bri(Md[R]), SM)). Consequently, it holds that Si ACCi(kbi app(bri(Md[B]), S)) for all 1 i n. Second, we show that for all n + 1 j n it holds that Sj ACCi(kbi app(bri(Md), S). Consider Md[b U ] (with b U relative to Md) and R = b U . Since Md[R ] = Md[b U ] = M[ ] M [B1, B2] and SB EQ(M[B1, B2]) hold, it follows by Corollary 3 that there exist S 1, . . . , S n such that SM = (S 1, . . . , S n, Sn+1, . . . , Sn+n ) EQ(M[ ] M [B1, B2]), i.e., for all n + 1 j n it holds that Sj ACCi(kbi app(bri(Md), SM )). Since it holds that SM =U S and b U R B, Lemma 13 applies and it follows that for all n + 1 j n + n it holds that ACCj(kbj app(brj(Md[B]), S)) = ACCj(kbj app(brj(Md[R ]), SM )). Consequently, it holds that Sj ACCj(kbj app(brj(Md[B]), S)) with n + 1 j n + n . In summary, it holds for every 1 i n + n that Si is accepted, i.e, S EQ(Md), hence (A1 I(A2), B1 I(B2)) D (M M ).

Proof of Lemma 3. Observe that 2M = M M and that 2.R = I(R) where I is the mapping wrt. M M. The statement then follows directly from Proposition 6.

Towards proving that D m,tmax applied on M allows to select -minimal, preferred diagnoses of M according to , we use the following lemmas about the set K(D1, D2). Recall that K(D1, D2) is the set of prioritized bridge rules of M that represent the candidate diagnosis (D1, D2) of M,

EITER & WEINZIERL

i.e., K(D1, D2) is as follows:

K(D1, D2) ={in1(r) | r D1} {in1(r) | r / D1}

{in2(r) | r D2} {in2(r) | r / D2}

The next lemma shows that the set K(D1, D2) is unique for every D1, D2 br(M).

Lemma 14. Let M be a clone encoding, D1, D2 br(M), and R = K(D1, D2). Then, there exists no D 1, D 2 br(M) with (D1, D2) = (D 1, D 2) such that R = K(D 1, D 2).

Proof. Towards contradiction, let (D1, D2) = (D 1, D 2) be such that K(D1, D2) = K(D 1, D 2). By (D1, D2) = (D 1, D 2) follows that either D1 = D 1 or D2 = D 2. Let D1 = D 1 and observe that K(D1, D2) {in1(r) | r br(M)} = {in1(r) | r D1} = {in1(r) | r D 1} = K(D 1, D 2) {in1(r) | r br(M)}. Consequently K(D1, D2) = K(D 1, D 2) which contradicts the assumption. The case D2 = D 2 is similar. It therefore follows that for R = K(D1, D2) no D 1, D 2 br(M) with (D1, D2) = (D 1, D 2) exists such that R = K(D 1, D 2).

The next lemma shows that two sets K(D1, D2) and K(D 1, D 2) are incomparable iff (D1, D2) is different from (D 1, D 2).

Lemma 15. Given Mmr(θ,Kp) and some D1, D2, D 1, D 2 br(M), let R = K(D1, D2) and let R = K(D 1, D 2); then R R or R R holds iff (D1, D2) = (D 1, D 2).

Proof. Let M be an MCS, D1, D2, D 1, D 2 br(M), R = K(D1, D2), and R = K(D 1, D 2). Observe that by deﬁnition of K it holds that |R| = |R |. Hence, R R or R R only holds iff R = R . By Lemma 14 it holds that K is injective, i.e., R = R iff (D1, D2) = (D 1, D 2). Consequently, R R or R R holds iff (D1, D2) = (D 1, D 2).

The following lemma shows the relationship between -preferred diagnoses of M and the prioritized-minimal ones of M .

Lemma 16. Given an MCS M and a preference order , D 2br(M) 2br(M) is -preferred iff both (1) t(D) D m(M , br P ) and (2) for every D D m(M , br P ) : D br H t(D) D =br H t(D) hold.

Proof. : Let D be -preferred, then D D (M) holds. We ﬁrst show that t(D) D m(M , br P ) holds: by Proposition 4 and the deﬁnition of M = Mmr(θ,Kp) it holds that (d1(D1 2.D1), d2(D2 2.D2) K(D1, D2) {tmax}) D (M , br P ) iff

1. (D1 2.D1, D2 2.D2) D (2M) holds,

2. θ(D1 2.D1, D2 2.D2, K(D1, D2) {tmax}) holds, and

3. there exists no (D 1 2.D 1, D 2 2.D 2) D (2M) such that (i) (d1(D 1 2.D 1), d2(D 2 2.D 2) K ) (d1(D1 2.D1), d2(D2 2.D2) K(D1, D2) {tmax}) and (ii) θ(D 1 2.D 1, D 2 2.D 2, K ) holds for some K Kp.

We show that each of those statements holds:

PREFERENCE-BASED INCONSISTENCY MANAGEMENT IN MULTI-CONTEXT SYSTEMS

1. Since D D (M) holds, it follows from Lemma 3 that (D1 2.D1, D2 2.D2) D (2M) holds.

2. Recall that θ(R1, R2, R3) for M = (2M)mr(θ,Kp) is deﬁned such that it holds if R1 = D1 2.D1, R2 = D2 2.D2, and R3 = K(D1, D2) {tmax}, hence θ(D1 2.D1, D2 2.D2, K(D1, D2) {tmax}) holds.

3. Towards contradiction, assume that there exists (D 1 2.D 1, D 2 2.D 2) D (2M) and K Kp such that it holds that (d1(D 1 2.D 1), d2(D 2 2.D 2) K ) (d1(D1 2.D1), d2(D2 2.D2) K(D1, D2) {tmax}) and θ(D 1 2.D 1, D 2 2.D 2, K ) holds. Note that from this it follows that K K(D1, D2) {tmax} and from the deﬁnition of θ that K K(D 1, D 2) {tmax}. Hence by Lemma 15, it follows that (D 1, D 2) = (D1, D2). If (D 1, D 2) = (D1, D2) then it holds by deﬁnition of θ that tmax K , i.e., (d1(D1 2.D1), d2(D2 2.D2) K(D1, D2) {tmax}) = (d1(D 1 2.D 1), d2(D 2 2.D 2) K ) which contradicts that the latter is a proper subset of the former. If (D 1, D 2) = (D1, D2) holds, then by deﬁnition of θ it follows that (D 1, D 2) (D1, D2) = (D 1, D 2), which contradicts that (D1, D2) is -preferred. It therefore follows that no such (D 1 2.D 1, D 2 2.D 2) D (2M) exists.

Since all three statements hold, it follows that t(D) D m(M , br P ) holds. It remains to show that T D m(M , br P ) : T br H t(D) T =br H t(D) holds. Assume that T D m(M , br P ) is such that T br H t(D) holds. Then by deﬁnition of θ it holds that T = (d1(T1 2.T 1), d2(T2 2.T 2) K(T1, T2) Tm) for some T1, T2, T 1, T 2 br(M) and Tm {tmax}. Since K(T1, T2) Kp, it holds by T br H t(D) that K(T1, T2) K(D1, D2), hence by Lemma 15 it follows that (T1, T2) = (D1, D2). Since (D1, D2) is -preferred, i.e., there exists no (D 1, D 2) D (M) such that (D 1, D 2) (D1, D2) holds, it follows from the deﬁnition of θ that (T 1, T 2) = (D1, D2) and consequently it holds that Tm = {tmax}. Altogether this means that T = t(D) and thus it holds that T =br H t(D). It therefore holds that T D m(M , br P ) : T br H t(D) T =br H t(D). : Suppose t(D1, D2) D m(M , br P ) and T D m(M , br P ) : T br H t(D) T =br H t(D) with D = (D1, D2) hold. Since t(D1, D2) D m(M , br P ) holds, it follows from Proposition 4 that (d1(D1 2.D1), d2(D2 2.D2)) D (2M), hence by Lemma 3 it holds that (D1, D2) D (M). To show that D is -preferred, consider the set F of diagnoses that are more preferred than D, i.e., F = {D D (M) | D D}. Towards contradiction, assume that F is non-empty, hence there exists some subset-minimal D F, i.e., D F and for all D F holds D D . Next we consider (T 1, T 2) = (d1(D1 D 1), d2(D2 D 2) K(D1, D2)) and observe that θ(D1 D 1, D2 D 2, K(D1, D2)) holds, because D D holds. Since (D1, D2) D (M) and (D 1, D 2) D (M) it holds that (D1 2.D 1, D2 2.D 2) D (2M). Observe that there exists no other D D with D D and D D (M). Therefore, there exists no (D 1, D 2) D (M) such that (d1(D1 2.D 1), d2(D2 2.D 2) K(D1, D2)) (T 1, T 2) and θ(D1 2.D 1, D2 2.D 2, K(D1, D2)) both hold. Thus Proposition 4 applies and it follows that (T 1, T 2) D m(M , br P ). Observe that (T 1, T 2) br H t(D) since T 2 br H = K(D1, D2) {tmax} and for t(D) = (T1, T2) holds T2 br H = K(D1, D2). This directly contradicts that T D m(M , br P ) : T br H t(D) T =br H t(D) holds. Thus the set F cannot be non-empty, i.e., there exists no D D (M) such that D D holds. Therefore, D is - preferred.

EITER & WEINZIERL

Proof of Theorem 3. Recall that D (M, br P , br H) = D D m(M, br P ) D D m(M, br P ) : D br H D D =br H D . Hence, t(D) D (M , br P , br H) holds iff t(D) D m(M , br P ) holds and for every D D m(M , br P ) it holds that D br H t(D) D =br H t(D) . By Lemma 16 this condition holds iff D is -preferred. In summary, D is -preferred iff t(D) D (M , br P , br H) holds.

Proof of Theorem 4. : Let D = (D1, D2) D m, (M) hold. Then D D (M) holds, i.e., D is -preferred and D D (M) holds. From Lemma 16 we then conclude that t(D) D m(M , br P ) and that the following holds: T D m(M , br P ) : T br H t(D) T =br H t(D). By construction of t(D) it furthermore holds that tmax t(D). Hence it remains to show that T D m(M , br P ) : T D m(M , br P ) : T br H T T =br H T tmax T T br(M )\br H t(D) t(D) =br(M )\br H T . Towards contradiction, assume that T D m(M , br P ) exists with T D m(M , br P ) : T br H T T =br H T tmax T and T br(M )\br H t(D). Note that the deﬁnition of θ and tmax T together imply that there exists some D = (D 1, D 2) with D 1, D 2 br(M) such that T = t(D ) holds. Further note that T = t(D ) satisﬁes all conditions of Lemma 16, thus it holds that D D (M) and that D is -preferred. From T = t(D ) br(M )\br H t(D) it follows that (d1(D 1 2.D 1), d2(D 2 2.D 2)) (d1(D1 2.D1), d2(D2 2.D2)) and since d1, d2, and 2. are bijective, it holds that (D 1, D 2) (D1, D2). Since D is -preferred, this contradicts that D is subset-minimal among all -preferred diagnoses, i.e., it contradicts that D D m, (M). Therefore no such T can exist and it holds that t(D) D m,tmax (M , br P , br H). : Let t(D1, D2) D m,tmax (M , br P , br H) hold. Since t(D1, D2) D m(M , br P ) and tmax t(D1, D2) hold, it follows from Lemma 16 that D = (D1, D2) D (M) and that D is -preferred. It remains to show that D is subset-minimal among diagnoses in D (M). Towards contradiction, assume that there exists D D (M) with D D. Since D is - preferred and D D (M) holds, it follows from Lemma 16 that t(D ) D m(M , br P ) and T D m(M , br P ) : T br H t(D ) T =br H t(D ) holds. Let T = t(D ). Then it holds for T that T D m(M, br P ) : T br H T T =br H T tmax T . Let T = t(D). Because d1, d2, and 2. are bijective and D D, it follows that T (br(M)\br H) T T =br(M)\br H T

does not hold. This contradicts that t(D1, D2) D m,tmax (M , br P , br H) holds. Therefore no such D exists and it holds that D is subset-minimal among D (M), i.e., D D m, (M) holds.

A.4 Proofs of Section 6

Proof of Theorem 5. In the remainder of this proof we assume C to be the computational complexity of MCSDm. Membership: In the following we give a polynomial-time reduction p m from MCSDPm to MCSDm. Given an instance of MCSDPm, i.e., given an MCS M, a set br P br(M), and a candidate diagnosis D 2br(M) 2br(M), we deﬁne p m such that

(M, br P , D) 7

( (M, D) if D1 br P = = D2 br P where D = (D1, D2) (M , ( , )) otherwise

where M = (C ), C = (Lasp Σ , kb , br ), br = {(1 : a) .}, and kb = { a.} is such that ( , ) / D m(M ). Intuitively, the reduction checks whether D contains bridge rules from br P

PREFERENCE-BASED INCONSISTENCY MANAGEMENT IN MULTI-CONTEXT SYSTEMS

and if so, maps to an instance which is not in MCSDm. If D contains no bridge rules from br P , then p m simply drops br P . Since the check whether D contains bridge rules of br P is possible in polynomial time, p m is a polynomial-time many-one reduction.

It remains to show that indeed (M, br P , D) is a yes-instance of MCSDPm iff p m (M, br P , D) is a yes-instance of MCSDm.

: Let (M, br P , D) be a yes-instance of MCSDPm, i.e., D D m(M, br P ) holds. Then, D = (D1, D2) is such that D1 br P = = D2 br P , hence p m (M, br P , D) = (M, D). By Proposition 1 it holds that D m(M, br P ) D m(M), hence it follows that D D m(M) holds, i.e., (M, D) is a yes-instance of MCSDm.

: Let p m (M, br P , D) be a yes-instance of MCSDm. Note that it cannot be the case that p m (M, br P , D) = (M , ( , )), because ( , ) / D m(M ) contradicts that p m (M, br P , D) is a yes-instance of MCSDm. Consequently, it holds that p m (M, br P , D) = (M, D) and thus D = (D1, D2) is such that D1 br P = = D2 br P . Furthermore, D D m(M) holds, thus it follows that D D (M, br P ) holds. Assume that D / D m(M, br P ) holds. Then there exists D D such that D D m(M, br P ) holds. By Proposition 1 then follows that D D m(M), which contradicts that D D m(M). Therefore no such D exists and it follows that D D m(M, br P ) holds.

Since p m is a polynomial reduction from MCSDPm to MCSDm, it follows that the computational complexity of MCSDPm is in C, i.e., the same complexity class where MCSDm is in.

Hardness: Let D D m(M) be hard for some complexity class C. Observe that by deﬁnition of diagnoses with protected bridge rules, it holds that D D m(M) is true iff D D m(M, ) is true. Since deciding whether D D m(M) is C-hard, it thus follows that deciding whether D D m(M, br P ) also is C-hard.

Proof of Lemma 4. : Let (M, (D1, D2), br P , br H) be a yes-instance of MCSDPH, i.e., it holds that (D1, D2) D (M, br P , br H). We have to show that (D 1, D 2) D m(M M, br P ) holds.

From (D1, D2) D (M, br P , br H) and (10) it follows that (D1, D2) D m(M, br P ) holds.

By Proposition 1 it then holds that (D1, D2) D m(M), thus there exists S = (S1, . . . , Sn) with S EQ(M[D1, D2]). We now show that (d1(D1 br H), d2(D2 br H)) D m(M , br P ) holds; to that end consider the belief state S = (S1, . . . , Sn, Sn+1, Sn+2) where

Sn+1 = {removedr | r r D1} {uncondr | r D2}

Sn+2 = {not removedr | r D1 \ br H} {uncondr | r D2 \ br H}.

By construction of Cn+2, it holds that

Sn+2 ACCn+2(kbn+2 app(brn+2(M [d1(D1 br H), d2(D2 br H)]), S ).

EITER & WEINZIERL

Consider the set of applicable bridge rules of Cn+1 under S and the candidate diagnosis (D1 br H, D2 br H) (where Rreg = (br(M) \ br P \ br H):

{ϕ (r) | r app(brn+1(M [d1(D1 br H), d2(D2 br H)]), S )}

= {not removedr | r br(M), r / Rreg, r / D1 \ br H}

{not removedr | r br(M), r Rreg, r / D1 br H}

{uncondr | r br(M), r / Rreg, r D2 br H}

{uncondr | r br(M), r Rreg, r D2 \ br H}

= {not removedr | r br(M), r / D1}

{uncondr | r br(M), r D2}

Since Sn+1 = {removedr | r r D1} {uncondr | r D2} and θ(D1, D2, ) holds, it follows from the deﬁnition of Cn+1 (cf. Deﬁnition 12 and Lemma 7) that Sn+1 ACCn+1(kbn+1 H) holds. Following the reasoning in Lemma 6 it is then possible to construct a proof showing that for all 1 i n it holds that

app(bri(M[D1, D2]), S) = app(bri(M [d1(D1 br H), d2(D2 br H)]), S ).

Since the semantics ACCi and knowledge base kbi of each context Ci are the same in M and M , it then follows from S EQ(M[D1, D2]) that for all 1 i n holds Si ACCi(kbi app(bri(M [d1(D1 br H), d2(D2 br H)]), S )). In summary, it holds that S EQ(M [d1(D1 br H), d2(D2 br H)]). Since (D1, D2) D (M) holds, we then conclude from Proposition 6 that (I(D1) d1(D1 br H), I(D2) d2(D2 br H) = (D 1, D 2) D (M M) holds. Note that D 1 br P = = D 2 br P , hence (D 1, D 2) D (M M, br P ) also holds. It remains to show that (D 1, D 2) D m(M M, br P ). Towards contradiction assume that there exists (T1, T2) D (M M, br P ) with (T1, T2) (D 1, D 2), i.e., by construction of M M it either is the case that (T1 I(br(M)), T2 I(br(M)) (D 1 I(br(M)), D 2 I(br(M))) holds or (T1 br M , T2 br M ) (D 1 br M , D 2 br M ) holds. In the former case, Proposition 6 implies that (I 1(T1 I(br(M))), I 1(T2 I(br(M)))) D (M); furthermore, since (D 1 I(br(M)), D 2 I(br(M))) = (D1, D2) it holds that (I 1(T1 I(br(M))), I 1(T2 I(br(M)))) (D1, D2). This contradicts that (D1, D2) D (M, br P , br H). In the latter case, i.e., (T1 br M , T2 br M ) (D 1 br M , D 2 br M ), it holds that (T1 br M , T2 br M ) (br H, br H) since all other bridge rules of br M are contained in br P . Let S be a witnessing equilibrium, i.e., let S = (S1, . . . , Sn+2) EQ(M [(T1 br M , T2 br M )]) hold. Consider the modiﬁcations of bridge rules in br(M) \ br P \ br H which are represented by S, i.e., consider T 1 = {r br(M) \ br P \ br H | not removedr / Sn+2} and T 2 = {r br(M) \ br P \ br H | uncondr Sn+2}. It holds that ((T1 br M ) T 1, (T2 br M ) T 2) is a candidate diagnosis of M. Since S EQ(M [(T1 br M , T2 br M )]) holds and M stems from Mmr(θ,Kp), one can show using Lemma 6 that ((T1 br M ) T 1, (T2 br M ) T 2) D (M, br P ) holds. This contradicts that (D1, D2) D (M, br P , br H), because ((T1 br M ) T 1, (T2 br M ) T 2) br H (D1, D2). Therefore, no such (T1, T2) exists and it holds that (D 1, D 2) D m(M M, br P ).

PREFERENCE-BASED INCONSISTENCY MANAGEMENT IN MULTI-CONTEXT SYSTEMS

: We prove the converse, i.e., we assume that (M, (D1, D2), br P , br H) is not a yes-instance of MCSDPH and show that DPH2DPm(M, (D1, D2), br P , br H) = (M M, (D 1, D 2), br P ) also is not a yes-instance of MCSDPm. By assumption it thus holds that (D1, D2) / D (M, br P , br H) holds. From the def. of D (M, br P , br H) we then obtain that either (i) (D1, D2) / D m(M, br P ) holds or (ii) that there exists (D 1, D 2) D m(M, br P ) with (D 1, D 2) br H (D1, D2). In case (i) (D1, D2) / D m(M, br P ), hence by Proposition 6 it holds that (I(D1) d1(D1 br H), I(D2) d2(D2 br H)) / D m(M M , br P ). In case (ii) (D 1, D 2) D m(M, br P ) with (D 1, D 2) br H (D1, D2). W.l.o.g. we assume that (D 1, D 2) is minimal wrt. br H, i.e., there exists no (D 1, D 2) D m(M, br P ) with (D 1, D 2) br H (D 1, D 2). This means that (M, (D 1, D 2), br P , br H) is a yes-instance of MCSDPH. We can further assume that (D1, D2) D m(M, br P ) from (i). Now consider (T1, T2) = (I(D1) d1(D 1 br H), I(D2) d2(D 2 br H)). Since (M, (D 1, D 2), br P , br H) is a yes-instance of MCSDPH, the direction above can be applied to it; this yields that (d1(D 1 br H), d2(D2 br H)) D m(M , br P ) holds. Applying Proposition 6 and the fact that T1 br P = = T2 br P then implies that (T1, T2) D m(M M, br P ) holds. Note that (T1, T2) (D 1, D 2) holds which in turn implies that (D 1, D 2) / D m(M M, br P ) holds. In other words, (M M, (D 1, D 2), br P ) is not a yes-instance of MCSDPm. In all cases, we showed that DPH2DPm(M, (D1, D2), br P , br H) is not a yes-instance of MCSDPm, which concludes the direction of the proof. In summary, we showed that (M, (D1, D2), br P , br H) is a yes-instance of MCSDPH iff (M M, (D 1, D 2), br P ) = DPH2DPm(M, (D1, D2), br P , br H) is a yes-instance of MCSDPm, i.e.,

DPH2DPm is a reduction from MCSDPH to MCSDPm. Since (M M, (D 1, D 2), br P ) can be computed in time linear in the size of (M, (D1, D2), br P , br H), it furthermore holds that DPH2DPm a polynomial-time reduction.

Proof of Theorem 6. Membership: By Lemma 4 it holds that DPH2DPm is a polynomial-time reduction from MCSDPH to MCSDPm, hence membership immediately follows. Hardness: Let M and D be any MCS and candidate diagnosis, respectively, used for showing hardness of MCSDm for C (i.e., M is the result of the reduction showing C-hardness of MCSDm and D is the diagnosis resulting from the reduction of M ). Now pick br P = br H = . By deﬁnition, it holds for all M, br P , br H and D, that D D (M, br P , br H) implies D D m(M, br P ) which in turn implies D D m(M). Therefore, D D (M , br P , br H ) implies that D D m(M ) holds. Furthermore, since br P = br H = it also follows from the deﬁnition of prioritized-minimal diagnosis and protected diagnosis that D D m(M ) implies D D (M , br P , br H ). In summary, D D m(M ) holds iff D D (M , br P , br H ) holds. Therefore MCSDPH also is C-hard.

Proof of Lemma 5. For membership, we give a reduction p m from MCSDPHtmax to MCSDPH as follows:

(M, D, br P , br H, tmax) 7

( (M, D, br P , br H) if D = (D1, D2), tmax D2 (M , ( , ), br M , ) otherwise

where M is the inconsistent MCS from the proof of Theorem 5, i.e., (M , ( , ), br M , ) is not a yes-instance of MCSDPH since the MCS is inconsistent but all its bridge rules are protected. Clearly, p m is a polynomial-time reduction.

EITER & WEINZIERL

: Let (M, D, br P , br H, tmax) be a yes-instance of MCSDPHtmax , this means that D D (M, br P , br H) and tmax D2 with D = (D1, D2) hold. Then D D (M, br P , br H) also holds, i.e., (M, D, br P , br H) is a yes-instance of MCSDPH. : Let (M, D, br P , br H, tmax) be not a yes-instance of MCSDPHtmax , i.e., let it not be the case that D D (M, br P , br H) and tmax D2 with D = (D1, D2) both hold. In case tmax / D2 it holds that ( , ) / D (M , br M , ) since M is inconsistent but all its bridge rules are protected, i.e., p m maps to a no-instance of MCSDPH. In case tmax D2 holds, it follows that D D (M, br P , br H) does not hold by the assumption. Therefore (M, D, br P , br H) is not a yes-instance of MCSDPH. Hence in all cases, p m (M, br P , br H, tmax) is not a yes-instance of MCSDPH.

Proof of Theorem 8. Since QBF problems correlate to complexity classes in the polynomial hierarchy, we reduce (different) QBF problems to MCSDMPREF to prove the following hardness statements: if CC(M) is hard for ΣP i (ΠP i ) then MCSDMPREF is hard for ΠP i+1 (ΠP i+2) with i 0; and MCSDMPREF is ΠP 2 -hard even if CC(M) and deciding whether D D hold are both in P.

QBF: A formula G is a quantiﬁed Boolean formula (QBF) if it is of the form Q1 X1 . . . Qn Xn : F where for each 1 i n, Qi { , } is a quantiﬁer, Xi is a set of Boolean variables, and F is a propositional formula over the set of variables V = S i {1,...,n} Xi. We assume that the quantiﬁers alternate, i.e., Qi = Qi+1 for all 1 i < n. QBFk denotes all QBF with k 1 quantiﬁers, QBF2, denotes all QBF with 2 quantiﬁers and Q1 = , and QBFk, denotes all QBF with k quantiﬁers and Q1 = . Given a formula G in QBFk, of the form as above, we denote the subformula X3 . . . Qk Xk : F by rem2, (G). Note that for a QBF2, formula G, rem2, (G) = F. For readability and simplicity, we denote the variables X1 by X and the variables X2 by Y . A valuation is an assignment of variables to { , }, we denote a assignment to variables X by VX : X { , }. Let ψ[x/t] denote the substitution of the propositional variable x by t { , } in ψ. Then the substitution by an assignment VX over X = {x1, . . . , xk} is ψ[x1/VX(x1)] . . . [xk/VX(xk)], with shorthand notation ψ[VX]. The semantics of QBF is inductively given in terms of valuations. A QBF G of the above form with n quantiﬁers evaluates to true if: G is quantiﬁer-free (n = 0) and G is a true propositional formula; if Q1 = (Q1 = ) and for all (for some) valuations VX1 it holds that G [VX1] evaluates to true where G = Q2 X2 . . . Qn Xn : F. Note that G being in QBFk implies that G [VX1] is in QBFk 1 for any valuation VX1.

Reduction: We deﬁne a logic Lqbf Σ = (KB, BS, ACC) for QBFs over a set of variables Σ, which enables QBF as a query language (cf. Egly, Eiter, Tompits, & Woltran, 2000) and is based on the idea of combining a database, under the closed-world assumption, with a theory (cf. Bonatti & Eiter, 1995). Formally, KB = 2Q with Q being the set of quantiﬁed Boolean formulas that can be built over Σ, i.e., each kb KB is a set of QBF; BS = { }, i.e., the only belief set is the empty set indicating evaluation to true; and ACC(kb) intuitively takes the conjunction CF of all formulas in kb except those that are unit, i.e., of the form (χ) with some variable χ, creates an assignment V from the unit clauses, and accepts the single belief set if and only if CF[V ] evaluates to true. Formally, ACC(kb) = { } if the QBF CF[V ] evaluates to true with CF = V f {f kb|f is not unit} f and valuation VZ : Z { , } such that V (χ) = if (χ) kb and V (χ) = otherwise where Z is the set of free (un-quantiﬁed) variables of CF. Note that if each f kb is in QBFk then CF[V ] is in QBFk since CF[V ] contains no more quantiﬁer alternations than any f kb. By that, the computational complexity of evaluating ACC

PREFERENCE-BASED INCONSISTENCY MANAGEMENT IN MULTI-CONTEXT SYSTEMS

is in ΣP k and ΠP k if each f kb is in QBFk, and QBFk, , respectively. Also note that the construction of CF[V ] is possible in linear time. We now deﬁne an MCS MG whose single context utilizes the evaluation of rem2, (G) given a valuation of all variables in X and Y . Given a QBFk-formula G with k 2, and X, Y , and rem2, (G) as above. Let br X 1 and br Y 1 be deﬁned as follows:

x X {(1:(x)) ., (1:( x)) .} br Y 1 = [

y Y {(1:(y)) ., (1:( y)) .}

Then MG = (C1) with the context C1 = (Lqbf Σ , kb1, br1), br1 = br X 1 br Y 1 , and kb1 as follows:

χ X Y (χ χ)

χ X Y (χ χ ) rem2, (Gt)

χ Y (χ χ) o

where Gt is equal to G except that every variable χ X Y is replaced with a new variable χ . Intuitively, C1 evaluates the remainder of G if a consistent valuation in terms of χ and χ is given for X Y (ﬁrst line) and it becomes true also for two other cases: (i) no value for any variable in X is given (second line), and (ii) a consistent valuation for X is given and all values for Y are present (third line). Note that br1 and kb1 are both polynomial (even linear) in the size of G. Notation: For a set R of bridge rules ϕ(R) denotes the set of head-formulas of the bridge rules of R, i.e., ϕ(R) = {ϕ (r) | r R}. For H ϕ(br1) we say that H is consistent wrt. a set of variables X if for all χ X it holds that (χ) H iff ( χ) / H. We call H consistent if it is consistent wrt. X Y . If H is consistent, then the corresponding valuation VH : X Y { , } is VH(χ) = if (χ) H and VH(χ) = otherwise. One can show that the semantics of C1 is as follows for any H ϕ(br1):

ACC(kb1 H) =

{ } if H is consistent and rem2, (G)[VH] evaluates to true, or if H ϕ(br X 1 ) = , or if H is consistent wrt. X and H ϕ(br Y 1 ), otherwise.

Intuitively, the above holds for the following reasons: kb1 H is such that all formulas f H are unit clauses, the variables in each clause are distinct, and each variable inside a unit clause is free wrt. kb1, because the only quantiﬁers occur in rem2, (Gt) which does quantify over χ but neither quantiﬁes χ nor χ, for any χ X Y . We use a certain diagnosis of MG, namely Dvalid = (br X 1 , ), to indicate whether G evaluates to true. In order to obtain that Dvalid D m, (MG) iff G evaluates to true, we use the following preference order :

(D1, D2) (D 1, D 2) holds iff D2 = D 2 = , (D1, D2) = Dvalid = (D 1, D 2),

D1 br X 1 = D 1 br X 1 , and D1 br Y 1 D 1 br Y 1 all hold, or

(D1, D2) = (D 1, D 2).

EITER & WEINZIERL

Note that is transitive and reﬂexive, i.e., indeed it is a preference order.

Correctness of Reduction: We now show for any QBF in QBFk, with k 2 that Dvalid D m, (MG) holds iff G evaluates to true. In some abuse of notation, in the following we write M[D] to denote the MCS obtained from modifying M according to a candidate diagnosis D, i.e., M[D] with D = (D1, D2) here denotes M[D1, D2]. Furthermore, if H br(MG) is consistent wrt. a set Z of variables, we denote by V H Z the corresponding valuation, i.e., V H Z (χ) = iff χ ϕ(H) and V H Z (χ) = iff χ ϕ(H) with χ Z. : Let Dvalid D m, (MG) hold. Towards contradiction, assume that G does not evaluate to

true, i.e., there exists a valuation VX for X such that no valuation VY for Y makes rem2, (G)[VX VY ] evaluate to true. Let R br X 1 be such that V ϕ(R) X = VX and consider the diagnosis D = (br X 1 \ R, ). Let H = {ϕ (r) | r app(br1(MG[D]), S )} and observe that H is consistent wrt. X since R is consistent. Since (br X 1 \R) br Y 1 = , it follows that H ϕ(br Y 1 ) = ϕ(br Y 1 ) and it thus holds that { } ACC(kb1 H), i.e., S is an equilibrium of MG[D], hence D D (MG). Further note that D Dvalid holds. Since Dvalid D m, (MG) and D Dvalid, it follows that D / D (MG) holds; i.e. there exists a diagnosis D D (MG) such that D D holds, which implies that D = D. Let D = (D 1, D 2) and D = (D1, D2); from the deﬁnition of and the fact that D = D we obtain that D 2 = , D = Dvalid, D 1 br X 1 = D1 br X 1 , and D 1 br Y 1 D1 br Y 1 all hold. Let H = {ϕ (r) | r app(br1(MG[D ]), S )} and observe that H is consistent wrt. X since D1 is consistent wrt. X and D 1 br X 1 = D1 br X 1 . Since D = D holds, it is the case that D 1 br Y 1 D1 br Y 1 and thus D1 br Y 1 = , i.e., H ϕ(br Y 1 ) = ϕ(br Y 1 ). This contradicts with H ϕ(br Y 1 ) = ϕ(br Y 1 ) established earlier. Therefore no such D exists and consequently no valuation VX exists such that all valuations VY make rem2, (G)[VX VY ] not evaluate to true, i.e., G evaluates to true. : Let G evaluate to true, i.e., for every valuation of X there exists a valuation of Y such that rem2, (G)[VX VY ] evaluates to true. Observe that br1(MG[Dvalid]) = br Y 1 , hence H = app(br1(MG[Dvalid]), S ) is such that H ϕ(br X 1 ) = , thus ACC(kb1 H) = { } and S is a witnessing equilibrium of Dvalid D (MG). Furthermore, since Dvalid is, by deﬁnition of , in no relation to any other candidate diagnosis except itself, it thus follows that Dvalid D (MG). It remains to show that Dvalid is subset-minimal among all diagnoses in D (MG). Consider any D Dvalid, i.e., D = (D 1, ) where D 1 br X 1 . Recall that D is not a diagnosis, if there exists no witnessing equilibrium; since S is the only belief state of MG, it follows that D is a diagnosis if and only if S is an equilibrium of MG[D ]. In the following, let H = app(br1(MG[D ]), S ). Since D 1 br X 1 holds, it follows that H ϕ(br Y 1 ), because for any r br Y 1 it holds that body(r) = { }, i.e., r is applicable in any belief state. Since H ϕ(br Y 1 ) holds, it cannot be the case that H is consistent wrt. Y ; thus H is not consistent. Furthermore, by D 1 br X 1 it follows that H ϕ(br X 1 ) = . By the deﬁnition of ACC it then follows that D only is a diagnosis if H

is consistent wrt. X. Assume that H is consistent wrt. X then V H X is a consistent valuation for variables in X. Since G evaluates to true and all variables in X are -quantiﬁed, there exists a valuation VY for the variables of Y such that rem2, (G)[V H X VY ] evaluates to true . Let R br Y 1 be the set of bridge rules consistent wrt. Y such that V ϕ(R) Y = VY and consider the candidate diagnosis D = (D 1 (br Y 1 \ R), ). Let H = {ϕ (r) | r app(br1(MG[D ]), S )} and observe that H

PREFERENCE-BASED INCONSISTENCY MANAGEMENT IN MULTI-CONTEXT SYSTEMS

is consistent since D 1 and R both are consistent. Furthermore, V H X = V H X and V H Y = VY , thus rem2, (G)[V H X V H Y ] evaluates to true, hence S is an equilibrium of M[D ] and D D (MG) holds.

Now consider whether D D holds: D = (D 1, ), D = (D 1 (br Y 1 \ R), ), D = Dvalid = D , D 1 br X 1 = (D 1 (br Y 1 \ R)) br X 1 , and D 1 br Y 1 (D 1 (br Y 1 \ R)) br Y 1 all hold. Therefore D D holds. Since R br Y 1 holds, it follows that br Y 1 \ R = and by D 1 br X 1 it then follows that (D 1 (br Y 1 \ R)) br Y 1 D 1 br Y 1 does not hold. Therefore D D does not hold and consequently, it holds that D D and D / D (MG). Since D Dvalid was chosen arbitrary, it follows that Dvalid is subset-minimal among all diagnoses in D (MG), hence Dvalid D m, (MG) holds.

In summary, this proves that Dvalid D m, (MG) holds iff G evaluates to true.

Complexity: Observe that deciding whether D D holds for the above clearly is in P. Further note that MG is polynomial in the size of G since kb1 and br1 are both polynomial (even linear) in the size of G. In the following we assume wlog. that all QBFs are in prenex normal form.

Let G be an arbitrary formula in QBF2, , then rem2, (G) contains no quantiﬁers, hence deciding whether rem2, (G) evaluates to true under an assignment for X Y amounts to evaluating a propositional formula under a given assignment; this is possible in P, hence CC(MG) = P. Since Dvalid D m, (MG) iff G evaluates to true, it thus follows that MCSDMPREF is ΠP 2 -hard if CC(M) = P.

Let G be an arbitrary formula in QBFi+2, for i 0, then rem2, (G) contains i quantiﬁers, hence rem2, (G) is a formula of QBFi, and checking whether it evaluates to true is in ΠP i , i.e., CC(MG) being hard for ΠP i is sufﬁcient for MCSDMPREF to decide whether G evaluates to true. Thus MCSDMPREF is ΠP i+2-hard for CC(M) being hard for ΠP i , i 0.

Similarly, if G is an arbitrary formula in QBFi+1, for i 1, then rem2, (G) contains i 1 quantiﬁers, i.e., rem2, (G) is a formula in QBFi 1, . Since QBFi, contains all formulas of QBFi 1, it follows that ΣP i is sufﬁcient for checking whether rem2, (G) evaluates to true. Thus, CC(MG) being hard for ΣP i is sufﬁcient for MCSDMPREF to decide whether G evaluates to true. Thus MCSDMPREF is ΠP i+1-hard for CC(M) = ΣP i , i 1.

In summary it thus follows that if CC(M) is hard for ΣP i (ΠP i ) then MCSDMPREF is hard for ΠP i+1 (ΠP i+2) with i 0 and that MCSDMPREF is ΠP 2 -hard even if CC(M) and deciding whether D D hold are both in P.

For hardness in case that CC(M) = P it is sufﬁcient to use a stratiﬁed logic program and the logic Lasp Σ as the context C1 in the MCS MG. Let G be in QBF2, , then rem2, (G) is a SAT formula and wlog. we assume rem2, (G) to be in CNF. Let F = rem2, (G) = {c1, . . . , cm} be given as a set of clauses each of the form cℓ= (lℓ1 lℓ2 . . . lℓk) with k N. We associate with each clause cℓof this form a set of rules

lp(cℓ) = clause cℓ lℓ1. . . . clause cℓ lℓj.

clause cℓ lℓj+1. . . . clause cℓ lℓk.

where lℓ1 to lℓj are the positive literals and lℓj+1 to lℓk are the negative literals of cℓ.

EITER & WEINZIERL

Finally, C1 = (Lasp Σ , kb1, br1) uses the abstract logic of ASP and kb1 is as follows:

kb1 = { consistent X not inconsistent X .

inconsistent X x, x. x X

consistent Y not inconsistent Y .

inconsistent Y y, y. y Y

ok consistent X , consistent Y , true F.

ok not nonempty intersect.

ok consistent X , not notfull Y .

nonempty intersect x. x X

nonempty intersect x. x X

notfull Y not y. y Y

notfull Y not y. y Y

true F clause c1, . . . , clause ck. for F = {c1, . . . , ck}

} {r lp(cℓ) | cℓ F}

Observe that kb1 is a stratiﬁable logic program while bridge rules only add facts, thus ACC(kb1 H) can be computed in polynomial time. Also note that kb1 is linear in the size of G.

Proof of Corollary 1. For the membership part, observe that the size of the clone-encoding M is polynomial in the size of M. As in M all contexts apart from the observation context have the same knowledge bases and logics as in M, their complexities are in CC(M); thus it remains to show that also the complexity of the observation context is in CC(M). Deﬁnition 17 speciﬁes which belief sets are acceptable for the latter in terms of the following conditions for which the property θ(R1, R2, R3) holds, namely: if R1 = D1 2.D 1, R2 = D2 2.D 2 and either (D1, D2) = (D 1, D 2) and R3 = K(D1, D2) {tmax} or (D 1, D 2) (D1, D2) and R3 = K(D1, D2). The equalities are trivially checked in polynomial time; thus if deciding D D is in ΣP i , then checking all conditions, i.e., whether θ(R1, R2, R2) holds, is in ΣP i ; note in particular that if deciding D D is in P, then deciding D D is in P and consequently deciding D D also is in P. By construction of M , it thus follows that CC(M) = ΣP i . The argument for PSPACE and EXPTIME in place of ΣP i is analogous. By Theorem 4, we have (D1, D2) D m, (M) iff t(D1, D2) D m,tmax (M , br P , br H) and from Theorem 7 it follows that deciding t(D1, D2) D m,tmax (M , br P , br H) is in ΠP i+1 (resp., co NPPSPACE = PSPACE, co NPEXPTIME = EXPTIME); hence deciding (D1, D2) D m, (M) is in ΠP i+1 (resp. PSPACE, EXPTIME). The hardness follows directly from Theorem 8 (resp. an MCS where the acceptability function of some context is hard for PSPACE resp. EXPTIME); hence, MCSDMPREF is complete for ΠP i+1 (resp. PSPACE, EXPTIME).

Proof of Corollary 2. The membership follows from Theorem 7. As for the hardness part, let CC(M) be equal to P, NP, or ΣP i with i 1 then by Theorem 8 MCSDMPREF is hard for ΠP 2 , ΠP 2 , or ΠP i+2, respectively. Let be any preference order on M such that deciding whether D D

PREFERENCE-BASED INCONSISTENCY MANAGEMENT IN MULTI-CONTEXT SYSTEMS

holds is in P. Consider the clone encoding M and any candidate diagnosis (D1, D2). By Theorem 4, we have (D1, D2) D m, (M) iff t(D1, D2) D m,tmax (M , br P , br H). Therefore the clone encoding induces a polynomial-time reduction of MCSDMPREF to MCSDPHm,tmax , because t(D1, D2) and M are both linear in the size of (D1, D2) plus M as well as CC(M ) is P, NP, or ΣP i (i 1) given that CC(M) is P, NP, or ΣP i (i 1). The hardness results of Theorem 8 thus also hold for MCSDPHm,tmax .

Appendix B. Detailed Examples

Example 19. Consider the hospital MCS (cf. Figure 1), where one can see two groups of bridge rules: health-related (r1 and r2) and billing-related (r3, r4, and r5). Assume a preference order is designed under the following two assumptions: ﬁrst, modifying one group of bridge rules potentially modiﬁes all information conveyed by the group (i.e., a correct result depends on all information of a group to be conveyed without modiﬁcation); and second, information of one group might inﬂuence another group, as in the hospital MCS health information inﬂuences billing. Candidate diagnoses then either modify (and possibly break) no group, the billing group, or health and billing group together. Since billing depends on health, it is impossible to modify health without possibly breaking billing. Only the candidate diagnosis ( , ) is of the ﬁrst kind. The second kind consists of all candidate diagnoses (D1, D2) with D1 D2 {r3, r4, r5} and D1 D2 = . All other candidate diagnoses are of the third kind. Preferring those diagnoses which (possibly) break only the least set of groups, then prefers diagnoses of the ﬁrst kind over all others, and the second over the third. Formally, we obtain a preference order U such that (D1, D2) U (D 1, D 2) holds iff one of the following is the case: 1) D1 D2 = , or 2) D1 D2 {r3, r4, r5} and D 1 D 2 = . The resulting MCS clone encoding wrt. U, M U = (C1, C2, C3, C4, C5, C6, C7) is based on two clones of M, where the ﬁrst comprises the contexts C1, C2, C3 and the second the contexts C4, C5, C6. The context C7 ﬁnally is the observation/encoding context. We ﬁrst recall the bridge rules of 2M = M M using the permutation I corresponding to M M. Accordingly br(2M) is:

r1 : (2 : hyperglycemia) (1 : hyperglycemia).

r2 : (2 : allow animal insulin) not (1 : allergic animal insulin).

r3 : (3 : bill animal insulin) (2 : give animal insulin).

r4 : (3 : bill human insulin) (2 : give human insulin).

r5 : (3 : insurance B) (1 : insurance B).

I(r1) : (5 : hyperglycemia) (4 : hyperglycemia).

I(r2) : (5 : allow animal insulin) not (4 : allergic animal insulin).

I(r3) : (6 : bill animal insulin) (5 : give animal insulin).

I(r4) : (6 : bill human insulin) (5 : give human insulin).

I(r5) : (6 : insurance B) (4 : insurance B).

EITER & WEINZIERL

A graphical rendering of M U is given in Figure 5, where for readability only some of the bridge rules of M U are shown. The set of bridge rules of the observation context C7 is as follows:

br7(M U ) = (7 : not removedr1) . (7 : uncondr1) .

(7 : not removedr2) . (7 : uncondr2) .

(7 : not removed I(r4)) . (7 : uncond I(r4)) .

(7 : not removed I(r5)) . (7 : uncond I(r5)) .

(7 : in1(r1)) . (7 : in1(r1)) .

(7 : in2(r1)) . (7 : in2(r1)) .

(7 : in1(r5)) . (7 : in1(r5)) .

(7 : in2(r5)) . (7 : in2(r5)) .

To fully realize the property θ and the preference order U based on real-world entities patient s health/treatment, and billing, we may use for the observation context C7 an ASP program that consists of the following rules:

removedr not not removedr. for all r br(M M) (22)

removedr, not in1(r). for all r {r1, . . . , r5} (23)

not removedr, in1(r). for all r {r1, . . . , r5}

not removedr, not in1(r). for all r {r1, . . . , r5}

removedr, in1(r). for all r {r1, . . . , r5}

uncondr, not in2(r). for all r {r1, . . . , r5}

uncondr, in2(r). for all r {r1, . . . , r5}

not uncondr, not in2(r). for all r {r1, . . . , r5}

uncondr, in2(r). for all r {r1, . . . , r5} (24)

mod(clone1, billing) removedr. for all r {r3, . . . , r5} (25)

mod(clone1, billing) uncondr. for all r {r3, . . . , r5}

mod(clone2, billing) removedr. for all r {I(r3), . . . , I(r5)}

mod(clone2, billing) uncondr. for all r {I(r3), . . . , I(r5)}

mod(clone1, treatment) removedr. for all r {r1, r2}

mod(clone1, treatment) uncondr. for all r {r1, r2}

mod(clone2, treatment) removedr. for all r {I(r1), I(r2)}

mod(clone2, treatment) uncondr. for all r {I(r1), I(r2)} (26)

PREFERENCE-BASED INCONSISTENCY MANAGEMENT IN MULTI-CONTEXT SYSTEMS

mod(clone1, billing) mod(clone1, treatment). (27)

mod(clone2, billing) mod(clone2, treatment). (28)

clones diﬀerent removedr, not removedr . for all r br(M), r I(br(M)) (29)

clones diﬀerent not removedr, removedr . for all r br(M), r I(br(M))

clones diﬀerent uncondr, not uncondr . for all r br(M), r I(br(M))

clones diﬀerent not uncondr, uncondr . for all r br(M), r I(br(M)) (30)

clone1 modiﬁes more mod(clone1, U), not mod(clone2, U). (31)

clone2 modiﬁes more mod(clone2, U), not mod(clone1, U).

clone1 less preferred clone1 modiﬁes more, not clone2 modiﬁes more. (32)

not ismax, clone1 less preferred, clones diﬀerent. (33)

not clone1 less preferred, clones diﬀerent. (34)

The intuition of the above rules is as follows: rules of form (22) expose the diagnoses of both clones; the constraints of form (23) (24) ensure that the diagnosis of the ﬁrst clone is exhibited via prioritized bridge rules; rules of form (25) (26) deduce which units of bridge rules have been modiﬁed in the ﬁrst and second clone; rules (27) and (28) take care of the dependency between the units treatment and billing; rules of form (29) (30) infer whether the diagnosis of the ﬁrst clone is different from the diagnosis of the second clone; rules (31) (32) infer whether the modiﬁed units of the ﬁrst clone is a superset of the modiﬁed units of the second clone, which means the diagnosis of the second clone is more preferred than the one of the ﬁrst clone. Finally, the constraint (33) ensures that tmax is made condition-free if the diagnosis of the second clone is more preferred than the diagnosis of the ﬁrst clone, and the constraint (34) ensures that only comparable diagnoses (or if both diagnoses are equal) yield a diagnosis of the MCS M U .

Allen, T. E. (2016). CP-Nets: From Theory to Practice. Ph.D. thesis, University of Kentucky. http://dx.doi.org/10.13023/ETD.2016.131.

Balduccini, M., & Gelfond, M. (2003). Logic programs with consistency-restoring rules. In Doherty, P., Mc Carthy, J., & Williams, M.-A. (Eds.), Working Papers of the 2003 AAAI Spring Symposium on Logical Formalization of Commonsense Reasoning, pp. 9 18. AAAI Press, Menlo Park, California.

Barilaro, R., Fink, M., Ricca, F., & Terracina, G. (2013). Towards query answering in relational multi-context systems.. In Cabalar, & Son (Cabalar & Son, 2013), pp. 168 173.

Bikakis, A., & Antoniou, G. (2008). Distributed defeasible contextual reasoning in ambient computing. In Aarts, E. H. L., Crowley, J. L., de Ruyter, B. E. R., Gerh auser, H., Pﬂaum, A., Schmidt, J., & Wichert, R. (Eds.), Ambient Intelligence, European Conference, Am I 2008, Nuremberg, Germany, November 19-22, 2008. Proceedings, Vol. 5355 of Lecture Notes in Computer Science, pp. 308 325. Springer.

Bikakis, A., & Antoniou, G. (2010). Defeasible contextual reasoning with arguments in ambient intelligence. IEEE Trans. Knowl. Data Eng., 22(11), 1492 1506.

EITER & WEINZIERL

Bikakis, A., & Antoniou, G. (2011). Partial preferences and ambiguity resolution in contextual defeasible logic. In Delgrande, J. P., & Faber, W. (Eds.), Logic Programming and Nonmonotonic Reasoning - 11th International Conference, LPNMR 2011, Vancouver, Canada, May 16-19, 2011. Proceedings, Vol. 6645 of Lecture Notes in Computer Science, pp. 193 198. Springer.

Bikakis, A., Antoniou, G., & Hassapis, P. (2009). Alternative strategies for conﬂict resolution in multi-context systems. In Iliadis, L. S., Maglogiannis, I., Tsoumakas, G., Vlahavas, I. P., & Bramer, M. (Eds.), Artiﬁcial Intelligence Applications and Innovations III, Proceedings of the 5TH IFIP Conference on Artiﬁcial Intelligence Applications and Innovations (AIAI 2009), April 23-25, 2009, Thessaloniki, Greece, Vol. 296 of IFIP Advances in Information and Communication Technology, pp. 31 40. Springer.

Bikakis, A., Antoniou, G., & Hassapis, P. (2011). Strategies for contextual reasoning with conﬂicts in ambient intelligence. Knowl. Inf. Syst., 27(1), 45 84.

Binas, A., & Mc Ilraith, S. A. (2008). Peer-to-peer query answering with inconsistent knowledge. In Proceedings of the 11th International Conference on Principles of Knowledge Representation and Reasoning, pp. 329 339, Sydney, Australia.

B ogl, M., Eiter, T., Fink, M., & Sch uller, P. (2010). The MCS-IE system for explaining inconsistency in multi-context systems. In Janhunen, T., & Niemel a, I. (Eds.), 12th European Conference on Logics in Artiﬁcial Intelligence (JELIA 2010), Lecture Notes in Artiﬁcial Intelligence, pp. 356 359. Springer.

Bonatti, P. A., & Eiter, T. (1995). Querying disjunctive database through nonmonotonic logics. In Gottlob, G., & Vardi, M. Y. (Eds.), Database Theory - ICDT 95, 5th International Conference, Prague, Czech Republic, January 11-13, 1995, Proceedings, Vol. 893 of Lecture Notes in Computer Science, pp. 68 81. Springer.

Boutilier, C., Brafman, R. I., Domshlak, C., Hoos, H. H., & Poole, D. (2004). CP-nets: A tool for representing and reasoning with conditional ceteris paribus preference statements. J. Artif. Intell. Res. (JAIR), 21, 135 191.

Brafman, R. I., Domshlak, C., Shimony, S. E., & Silver, Y. (2006). Preferences over sets. In Proceedings, The Twenty-First National Conference on Artiﬁcial Intelligence and the Eighteenth Innovative Applications of Artiﬁcial Intelligence Conference, July 16-20, 2006, Boston, Massachusetts, USA, pp. 1101 1106. AAAI Press.

Brewka, G. (2013). Towards reactive multi-context systems.. In Cabalar, & Son (Cabalar & Son, 2013), pp. 1 10.

Brewka, G., & Eiter, T. (2007). Equilibria in heterogeneous nonmonotonic multi-context systems.. In AAAI Conference on Artiﬁcial Intelligence (AAAI), pp. 385 390.

Brewka, G., Eiter, T., & Fink, M. (2011a). Nonmonotonic multi-context systems: A ﬂexible approach for integrating heterogeneous knowledge sources. In Balduccini, M., & Son, T. C. (Eds.), Logic Programming, Knowledge Representation, and Nonmonotonic Reasoning, Vol. 6565 of Lecture Notes in Computer Science, pp. 233 258. Springer.

Brewka, G., Eiter, T., Fink, M., & Weinzierl, A. (2011b). Managed multi-context systems.. In Walsh (Walsh, 2011), pp. 786 791.

Brewka, G., Ellmauthaler, S., & P uhrer, J. (2014a). Multi-context systems for reactive reasoning in dynamic environments. In 21st European Conference on Artiﬁcial Intelligence (ECAI 2014).

PREFERENCE-BASED INCONSISTENCY MANAGEMENT IN MULTI-CONTEXT SYSTEMS

Brewka, G., Ellmauthaler, S., & P uhrer, J. (2014b). Multi-context systems for reactive reasoning in dynamic environments. In Proceedings of the International Workshop on Reactive Concepts in Knowledge Representation (React Know 2014), pp. 23 29.

Brewka, G., Roelofsen, F., & Seraﬁni, L. (2007). Contextual default reasoning. In Veloso, M. M. (Ed.), IJCAI 2007, Proceedings of the 20th International Joint Conference on Artiﬁcial Intelligence, Hyderabad, India, January 6-12, 2007, pp. 268 273.

Brewka, G., Truszczy nski, M., & Woltran, S. (2010). Representing preferences among sets. In Fox, M., & Poole, D. (Eds.), Proceedings of the Twenty-Fourth AAAI Conference on Artiﬁcial Intelligence, AAAI 2010, Atlanta, Georgia, USA, July 11-15, 2010. AAAI Press.

Bylander, T., Allemang, D., Tanner, M. C., & Josephson, J. R. (1991). The computational complexity of abduction. Artiﬁcial Intelligence, 49(1-3), 25 60.

Cabalar, P., & Son, T. C. (Eds.). (2013). Logic Programming and Nonmonotonic Reasoning, 12th International Conference, LPNMR 2013, Corunna, Spain, September 15-19, 2013. Proceedings, Vol. 8148 of Lecture Notes in Computer Science. Springer.

Caire, P., & Bikakis, A. (2011). Enhancing cooperation in distributed information systems using conviviality and multi-context systems. In Sombattheera, C., Agarwal, A., Udgata, S. K., & Lavangnananda, K. (Eds.), Multi-disciplinary Trends in Artiﬁcial Intelligence - 5th International Workshop, MIWAI 2011, Hyderabad, India, December 7-9, 2011. Proceedings, Vol. 7080 of Lecture Notes in Computer Science, pp. 14 25. Springer.

Caire, P., Bikakis, A., & Traon, Y. L. (2013). Information dependencies in MCS: convivialitybased model and metrics. In Boella, G., Elkind, E., Savarimuthu, B. T. R., Dignum, F., & Purvis, M. K. (Eds.), PRIMA 2013: Principles and Practice of Multi-Agent Systems - 16th International Conference, Dunedin, New Zealand, December 1-6, 2013. Proceedings, Vol. 8291 of Lecture Notes in Computer Science, pp. 405 412. Springer.

Calvanese, D., Giacomo, G. D., Lenzerini, M., & Rosati, R. (2004). Logical foundations of peerto-peer data integration. In Beeri, C., & Deutsch, A. (Eds.), PODS, pp. 241 251. ACM.

Dantsin, E., Eiter, T., Gottlob, G., & Voronkov, A. (2001). Complexity and expressive power of logic programming. ACM Computing Surveys, 33(3), 374 425.

Dao-Tran, M., Eiter, T., Fink, M., & Krennwallner, T. (2015). Distributed evaluation of nonmonotonic multi-context systems. J. Artif. Intell. Res. (JAIR), 52, 543 600.

Domshlak, C., Brafman, R. I., & Shimony, S. E. (2001). Preference-based conﬁguration of web page content. In Nebel, B. (Ed.), IJCAI, pp. 1451 1456. Morgan Kaufmann.

Doyle, J., Shoham, Y., & Wellman, M. P. (1991). A logic of relative desire (preliminary report). In Ras, Z. W., & Zemankova, M. (Eds.), Methodologies for Intelligent Systems, 6th International Symposium, ISMIS 91, Charlotte, N.C., USA, October 16-19, 1991, Proceedings, Vol. 542 of Lecture Notes in Computer Science, pp. 16 31. Springer.

Dung, P. M. (1995). On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games. Artif. Intell., 77(2), 321 358.

Egly, U., Eiter, T., Tompits, H., & Woltran, S. (2000). Solving advanced reasoning tasks using quantiﬁed boolean formulas. In Kautz, H. A., & Porter, B. W. (Eds.), Proceedings of the Seventeenth National Conference on Artiﬁcial Intelligence and Twelfth Conference on on

EITER & WEINZIERL

Innovative Applications of Artiﬁcial Intelligence, July 30 - August 3, 2000, Austin, Texas, USA., pp. 417 422. AAAI Press / The MIT Press.

Eiter, T., Fink, M., Sch uller, P., & Weinzierl, A. (2010). Finding explanations of inconsistency in multi-context systems. In Lin, F., Sattler, U., & Truszczy nski, M. (Eds.), Principles of Knowledge Representation and Reasoning: Proceedings of the Twelfth International Conference, KR 2010, Toronto, Ontario, Canada, May 9-13, 2010, pp. 329 339. AAAI Press.

Eiter, T., Fink, M., Sch uller, P., & Weinzierl, A. (2014). Finding explanations of inconsistency in multi-context systems. Artiﬁcial Intelligence, 216(0), 233 274.

Eiter, T., Fink, M., & Weinzierl, A. (2010). Preference-based inconsistency assessment in multicontext systems. In Janhunen, T., & Niemel a, I. (Eds.), Logics in Artiﬁcial Intelligence - 12th European Conference, JELIA 2010, Helsinki, Finland, September 13-15, 2010. Proceedings, Vol. 6341 of Lecture Notes in Computer Science, pp. 143 155. Springer.

Eiter, T., Gottlob, G., & Mannila, H. (1997). Disjunctive datalog. ACM Trans. Database Syst., 22(3), 364 418.

Eiter, T., & ˇSimkus, M. (2015). Linking open-world knowledge bases with nonmonotonic rules. In Calimeri, F., Ianni, G., & Truszczy nski, M. (Eds.), Proceedings of the 13th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR 2015), Vol. 9345 of LNCS, pp. 294 308. Springer.

Ellmauthaler, S. (2013). Generalizing multi-context systems for reactive stream reasoning applications. In Jones, A. V., & Ng, N. (Eds.), Proceedings of the 2013 Imperial College Computing Student Workshop (ICCSW 2013), Open Access Series in Informatics (OASIcs), pp. 17 24. Schloss Dagstuhl Leibniz-Zentrum fuer Informatik.

Ellmauthaler, S., & P uhrer, J. (2014). Asynchronous multi-context systems. In Ellmauthaler, S., & P uhrer, J. (Eds.), Proceedings of the International Workshop on Reactive Concepts in Knowledge Representation (React Know 2014), pp. 31 37.

Faber, W., Leone, N., & Pfeifer, G. (2004). Recursive aggregates in disjunctive logic programs: Semantics and complexity. In European Conference on Logics in Artiﬁcial Intelligence (JELIA), pp. 200 212.

Fink, M., Ghionna, L., & Weinzierl, A. (2011). Relational information exchange and aggregation in multi-context systems. In Delgrande, J. P., & Faber, W. (Eds.), Logic Programming and Nonmonotonic Reasoning - 11th International Conference, LPNMR 2011, Vancouver, Canada, May 16-19, 2011. Proceedings, Vol. 6645 of Lecture Notes in Computer Science, pp. 120 133. Springer.

Gelfond, M., & Lifschitz, V. (1991). Classical negation in logic programs and disjunctive databases. New Generation Computing, 9(3/4), 365 386.

Ghidini, C., & Giunchiglia, F. (2001). Local models semantics, or contextual reasoning=locality+compatibility. Artif. Intell., 127(2), 221 259.

Giunchiglia, F., & Seraﬁni, L. (1994). Multilanguage hierarchical logics or: How we can do without modal logics. Artif. Intell., 65(1), 29 70.

Goldsmith, J., Lang, J., Truszczy nski, M., & Wilson, N. (2008). The computational complexity of dominance and consistency in cp-nets. J. Artif. Intell. Res. (JAIR), 33, 403 432.

PREFERENCE-BASED INCONSISTENCY MANAGEMENT IN MULTI-CONTEXT SYSTEMS

Goncalves, R., Knorr, M., & Leite, J. (2014a). Evolving bridge rules in evolving multi-context systems. In Bulling, N., van der Torre, L. W. N., Villata, S., Jamroga, W., & Vasconcelos, W. (Eds.), Computational Logic in Multi-Agent Systems - 15th International Workshop, CLIMA XV, Prague, Czech Republic, August 18-19, 2014. Proceedings, Vol. 8624 of Lecture Notes in Computer Science, pp. 52 69. Springer.

Goncalves, R., Knorr, M., & Leite, J. (2014b). Evolving multi-context systems. In Schaub, T., Friedrich, G., & O Sullivan, B. (Eds.), ECAI 2014 - 21st European Conference on Artiﬁcial Intelligence, 18-22 August 2014, Prague, Czech Republic - Including Prestigious Applications of Intelligent Systems (PAIS 2014), Vol. 263 of Frontiers in Artiﬁcial Intelligence and Applications, pp. 375 380. IOS Press.

Gottlob, G. (1992). Complexity results for nonmonotonic logics. Journal of Logic and Computation, 2, 397 425.

Inoue, K. (2011). Logic programming for boolean networks.. In Walsh (Walsh, 2011), pp. 924 930.

Jin, Y., Wang, K., & Wen, L. (2012). Possibilistic reasoning in multi-context systems: Preliminary report. In Anthony, P., Ishizuka, M., & Lukose, D. (Eds.), PRICAI 2012: Trends in Artiﬁcial Intelligence - 12th Paciﬁc Rim International Conference on Artiﬁcial Intelligence, Kuching, Malaysia, September 3-7, 2012. Proceedings, Vol. 7458 of Lecture Notes in Computer Science, pp. 180 193. Springer.

Kakas, A. C., Kowalski, R. A., & Toni, F. (1992). Abductive logic programming. J. Log. Comput., 2(6), 719 770.

Kauffman, S. A. (1969). Metabolic stability and epigenesis in randomly constructed genetic nets. Journal of Theoretical Biology, 22(3), 437 467.

Kauffman, S. A. (1993). Origins of Order: Self-Organization and Selection in Evolution. Oxford Univ. Press. Technical monograph.

Knorr, M., Slota, M., Leite, J., & Homola, M. (2014). What if no hybrid reasoner is available? hybrid MKNF in multi-context systems. J. Log. Comput., 24(6), 1279 1311.

Le, T., Son, T. C., & Pontelli, E. (2015). Multi-context systems with preferences. In Chen, Q., Torroni, P., Villata, S., Hsu, J. Y., & Omicini, A. (Eds.), PRIMA 2015: Principles and Practice of Multi-Agent Systems - 18th International Conference, Bertinoro, Italy, October 26-30, 2015, Proceedings, Vol. 9387 of Lecture Notes in Computer Science, pp. 449 466. Springer.

Mc Carthy, J. (1993). Notes on formalizing context. In Bajcsy, R. (Ed.), Proceedings of the 13th International Joint Conference on Artiﬁcial Intelligence. Chamb ery, France, August 28 - September 3, 1993, pp. 555 562. Morgan Kaufmann.

Mu, K., Wang, K., & Wen, L. (2015). Preferential multi-context systems. Co RR, abs/1504.06700.

Reiter, R. (1980). A logic for default reasoning. Artiﬁcial Intelligence, 13, 81 132.

Roelofsen, F., & Seraﬁni, L. (2005). Minimal and absent information in contexts. In Kaelbling, L. P., & Safﬁotti, A. (Eds.), IJCAI-05, Proceedings of the Nineteenth International Joint Conference on Artiﬁcial Intelligence, Edinburgh, Scotland, UK, July 30-August 5, 2005, pp. 558 563. Professional Book Center.

Salcher, F. (2016). Distributed computation of diagnoses for inconsistent multi-context systems. Master s thesis, Vienna University of Technology. To appear.

EITER & WEINZIERL

Sch uller, P., & Weinzierl, A. (2011). Semantic reasoning with SPARQL in heterogeneous multicontext systems. In Salinesi, C., & Pastor, O. (Eds.), Advanced Information Systems Engineering Workshops - CAi SE 2011 International Workshops, London, UK, June 20-24, 2011. Proceedings, Vol. 83 of Lecture Notes in Business Information Processing, pp. 575 585. Springer.

Seraﬁni, L., & Homola, M. (2012). Contextualized knowledge repositories for the semantic web. J. Web Sem., 12, 64 87.

Tasharroﬁ, S., & Ternovska, E. (2014). Generalized multi-context systems. In Baral, C., Giacomo, G. D., & Eiter, T. (Eds.), Principles of Knowledge Representation and Reasoning: Proceedings of the Fourteenth International Conference, KR 2014, Vienna, Austria, July 20-24, 2014. AAAI Press.

Velikova, M., Nov ak, P., Huijbrechts, B., Laarhuis, J., Hoeksma, J., & Michels, S. (2014). An integrated reconﬁgurable system for maritime situational awareness. In Schaub, T., Friedrich, G., & O Sullivan, B. (Eds.), ECAI 2014 - 21st European Conference on Artiﬁcial Intelligence, 18-22 August 2014, Prague, Czech Republic - Including Prestigious Applications of Intelligent Systems (PAIS 2014), Vol. 263 of Frontiers in Artiﬁcial Intelligence and Applications, pp. 1197 1202. IOS Press.

Von Neumann, J., & Morgenstern, O. (1944). Theory of Games and Economic Behavior. Princeton University Press.

Walsh, T. (Ed.). (2011). IJCAI 2011, Proceedings of the 22nd International Joint Conference on Artiﬁcial Intelligence, Barcelona, Catalonia, Spain, July 16-22, 2011. IJCAI/AAAI.

Weinzierl, A. (2014). Inconsistency Management under Preferences for Multi-Context Systems and Extensions. Ph.D. thesis, Vienna University of Technology. http://media.obvsg.at/ p-AC12121980-2001.