Managed Multi-Context Systems

1 Introduction

Over the last decades research in knowledge representation and, more generally, information technology has produced a large variety of formats and languages for representing knowledge. A wealth of tools and formalisms is now available, including rather basic ones like databases or the more recent triple-stores, and more expressive ones like ontology languages (e.g., description logics), temporal and modal logics, nonmonotonic logics, or logic programs under answer set semantics, to name just a few (see van Harmelen et al. [2008]). Several are widely used, a development particularly fueled by the advent and continuous growth of the world wide web.

However, the diversity of formalisms also poses some important challenges: What is the best way to benefit from it? How to build systems that need access to heterogeneous knowledge sources, e.g., in ambient intelligence [Bikakis and Antoniou, 2008]? A standardized, universal knowledge representation language certainly cannot be the solution. There are very good reasons for special purpose representation languages, e.g., domain specific modeling needs and complexity.

Nonmonotonic multi-context systems (MCS) [Brewka and Eiter, 2007] provide a promising way to address the challenges above. The basic idea is to leave the diverse formalisms and Michael Fink‡ Antonius Weinzierl‡

∗ Supported by the Vienna Science and Technology Fund (WWTF) project ICT08-020.

‡Vienna University of Technology Institute of Information Systems {eiter,fink,weinzierl}@kr.tuwien.ac.at

knowledge bases (called contexts in this approach for historical reasons [Giunchiglia and Serafini, 1994]) as they are, but to model the necessary information flow among contexts using so-called bridge rules. The latter are similar to logic programming rules (including default negation), but allow access to other contexts in their bodies. This has several advantages: the specification of the information flow is fully declarative; moreover, not only can information be passed from one context to another as is; bridge rules also provide means, e.g., for selection, abstraction and conflict resolution between contexts.

Example 1. Consider a pharmaceutical company producing drugs. A drug effect database C1 holds information about what is the remedy of an illness caused by certain bacteria, also treatments known to be ineffective are stored. To maximize efficiency, the company wants to know all kinds of illness that can be cured by their drugs. A public health RDF-triple store C2 is queried on illness caused by bacteria for which C1 already holds a remedy. Furthermore, probable influence of the drugs on other bacteria is derived which enables more focused clinical trials, i.e., only those effects are tested in the later trial where a likely effect was found. This is realized using an ontology about bacteria C3 and a third party reasoner to derive likely drug effects on other bacteria. To this end, C1 may use a view restricted to the necessary information.

Although MCS are, as we believe, an excellent starting point to address the problems from above, the way they integrate knowledge is still quite limited: if a bridge rule for a context is applicable, then the rule head is simply added to the context's knowledge base (KB). Although this covers the flow of information, it does not capture other operations one may want to perform on context KBs. For instance, rather than simply adding a formula φ, we may want to revise [Peppas, 2008] the KB with φ to avoid inconsistency in the context's belief set; and, we may want to modify only certain parts of KB such that φ is entailed. In Example 1, an update of C1's view to C3 may be wanted (which must be realized inside C3).

For this reason, we introduce in this paper a new, more general form of MCS where such additional operations on knowledge bases can be freely defined; this is akin to management functionality of database systems. We call the additional component context manager and the generalized systems managed multi-context systems (mMCS).

The outline of the paper is as follows: after recalling the necessary background on MCS, we introduce the new framework in Section 3, while Section 4 discusses sample instances. Several aspects of inconsistency management in mMCS are addressed in Section 5 and complexity issues in Section 6.

2 Preliminaries

Multi-Context Systems as defined in Brewka and Eiter [2007] build on an abstract notion of a logic L as a triple (KBL,BSL,ACCL), where KBL is the set of admissible knowledge bases of L, which are sets of KB-elements ("formulas"); BSL is the set of possible belief sets, whose elements are beliefs; and ACCL : KBL → 2BSL is a function describing the semantics of L by assigning each knowledge-base a set of acceptable belief sets.

A multi-context system (MCS) M = (C1, . . . ,Cn) is a collection of contexts Ci = (Li, kbi, bri) where Li is a logic, kbi ∈ KBLi is a knowledge base and bri is a set of bridge rules of the form:

such that kb ∪ {s} is an element of KBLi , cℓ ∈{1, . . . , n}, and pℓ is element of some belief set of BScℓ , for all 1 ≤ ℓ ≤ m. For a bridge rule r, we denote by hd(r) the formula s while body(r) denotes the set {(cℓ1 : pℓ1 ) | 1 ≤ ℓ1 ≤ j} ∪ {not(cℓ2 : pℓ2 ) | j < ℓ2 ≤m}.

Example 2 (ctd). In our running example, C1 is a relational database which contains the information that penicillin remedies pneumonia caused by the bacteria streptococcus pneumoniae and also that azithromycin remedies Legionair's disease caused by legionella pneumophila, effectiveness of both remedies is backed by clinical trials and therefore evident. Also, it contains information that penicillin is ineffective against legionella pneumophila. C2 is an RDF-triple store containing information that streptococcus pneumoniae causes meningitis and legionella pneumonphila causes atypical pneumonia. Formally, the knowledge bases of C1, respectively C2, are:

To incorporate information from C2, C1 uses the following bridge rule connecting existing information about effects on bacteria with illness caused by the same bacteria. The incorporated information is further marked as only being likely, but not clinically tested. The set of bridge rules of C1 is given by:

Here we use for readability and succinctness schematic bridge rules with variables (upper case letters and ) which range over associated sets of constants; they stand for all respective instances (obtainable by value substitution).

A belief state S = (S1, . . . , Sn) for M consists of belief sets Si ∈ BSi, 1 ≤ i ≤ n. A bridge rule r of form (1) is applicable wrt. S, denoted by S |= body(r), iff pℓ ∈ Scℓ

for 1 ≤ ℓ ≤ j and pℓ /∈ Scℓ for j < ℓ ≤ m. We use appi(S) = {hd(r) | r ∈ bri ∧ S |= body(r)} to denote the heads of all applicable bridge rules of context Ci wrt. S.

The semantics of an MCS M is then defined in terms of equilibria, where an equilibrium is a belief state (S1, . . . , Sn) such that Si ∈ ACC i(kbi ∪ appi(S)), 1 ≤ i ≤ n.

Example 3 (ctd). Suppose the possible belief sets in C1 and C2 are all sets of facts (over the respective vocabularies) and the acceptable ones for a knowledge base kb are those holding the facts which logically follow from kb under the respective inference closure inf i, i.e., ACCi(kb)={inf i(kb)}. In our example we have a single equilibrium S = (S1, S2), given by S1 = inf 1(kb1 ∪ app1(S)) = kb1 ∪{treat(pen, str pneu,men, likely), treat(azith, leg pneu, atyp pneu, likely)} and S2 = inf 2(kb2 ∪ app2(S)) = kb2.

3 ManagedMulti-Context Systems

Multi-Context Systems allow us to increase the knowledge base of a context using information from other contexts, but not to operate on it in other ways. Such other operations might be: removal of information; revision with new information, or other complex operations like view-updates of databases; program updates of logic programs; modifications of argumentation frameworks, etc. Notably, those operations are realized by legacy systems, but the MCS framework can not cope with this functionality in a principled way.

To enable such functionality with a clear distinction between the knowledge base and additional operations on it, we introduce the managed Multi-Context Systems framework. The latter extends Multi-Context Systems such that contexts come with an additional managing function which evaluates the aforementioned operations, in analogy to the distinction of a database (DB) and a database management system (DBMS).

Example 4 (ctd). Assume C1's data is offered to a third party C4 for deriving further possible drug effects. To that end, a view "eff " is created containing only the information about which drug effects what bacteria, i.e., (X,B) ∈ eff iff (X,B, , evd) ∈ treat, as information derived fromC4 is also returned through this view, it must be updateable.

C4 is a logic program accessing the ontology C3 on bacteriological relations to deduce probable effects on related bacteria. C1 also holds information on ineffective drugs which should be incorporated into C4 by means of a logic program update. This allows to deduce probable effects on bacteria except for cases where there is already negative evidence.

To accommodate flexible semantics of contexts, we extend the above notion of "logic" to one which has several semantics to choose from. This allows, e.g., that a logic program is evaluated using well-founded semantics instead of stable semantics based on input from other contexts, or switching from classical to paraconsistent semantics.

Definition 1. A logic suite LS = (BSLS,KBLS,ACCLS) consists of the set BSLS of possible belief sets, the set KBLS of well-formed knowledge-bases, and a nonempty set ACCLS of possible semantics of LS, i.e, ACCLS ∈ ACCLS implies ACCLS : KBLS → 2BSLS .

For a logic suite LS, FLS = {s ∈ kb | kb ∈ KBLS} is the set of formulas occurring in its knowledge bases.

Definition 2. A management base is a set of operation names (briefly, operations) OP.

Intuitively, a management base is the set of commands that can be executed on formulas, e.g., addition of, revision with, etc. a formula. For a logic suite LS and a management base OP, let F OP LS = {o(s) | o ∈ OP, s ∈ FLS} be the set of operational statements that can be built from OP and FLS .

The semantics of such statements is given by a management function. A management function maps a set of operational statements and a knowledge base to pairs of a modified knowledge base and a semantics. It allows to not only add formulas to a context, but to specify any desired operations to be applied on formulas and a context.

Definition 3. A management function over a logic suite LS and a management base OP is a function mng : 2F OP LS × KBLS → 2(KBLS×ACCLS ) \ {∅}.

Bridge rules for context Ci are now of form (1) as for MCS, but with the head expression s being an operational statement for the management function mngi of Ci; let OPi be the management base of Ci, then s ∈ F OPi LSi .

Example 5 (ctd). Regarding C1, an operation "insert" is introduced and the management function mng1 is defined such that tuples inserted into the view eff are transformed to treat tuples; formally, mng1(O, kb1) = {(kb1 ∪ N ∪ V, ACC1)} where N = {treat(⃗t) | insert(treat(⃗t)) ∈ O}, V = {treat(X,B, I, est) | insert(eff (X,B)) ∈ O ∧ treat( ,B, I, ) ∈ kb1 ∪N} and kb1 is extended by the following view definition: eff (X,B) ← treat(X, ,B, evd).

For C4, the operations are OP4 ={upd, add} and mng4 adds all formulas in add as facts and the resulting program is updated according to formulas in upd by the method given in Alferes et al. [2002], which avoids inference of conflicting information (see Ex. 7 for details). Thus, mng4 always selects the stable model semantics of dynamic logic programs.

A managed MCS (mMCS) is then an MCS where each context additionally comes with a management function and bridge rule heads are operational statements.

Definition 4. A managed Multi-Context System M is a collection (C1, . . . ,Cn) of managed contexts where, for 1 ≤ i ≤ n, each managed context Ci is a quintuple Ci = (LSi, kbi, bri,OPi,mngi) such that

• LSi = (BSLSi ,KBLSi ,ACCLSi ) is a logic suite,
• kbi ∈ KBLSi is a knowledge base,
• bri is a set of bridge rules for Ci,
• OPi is a management base, and
• mngi is a management function over LSi and OPi.

As for ordinary MCS, a belief state S = (S1, . . . , Sn) of M is a belief set for every context, i.e., Si ∈ BSLSi . Again, by appi(S) = {hd(r) | r ∈ bri ∧ S |= body(r)} we denote the set of applicable heads of bridge rules, which is a set of operational statements.

The semantics of mMCS is now in terms of equilibria.

Definition 5. Let M =(C1, . . . ,Cn) be an mMCS. A belief state S =(S1, . . . , Sn) is an equilibrium of M iff for every 1 ≤ i ≤ n there exists some (kb ′i ,ACCLSi )∈ mngi(appi(S), kbi) such that Si ∈ ACCLSi (kb ′i ).

Observe that an ordinary context Ci =(Li, kbi, bri) with logic Li = (BSLi , KBLi , ACCLi ) can be easily turned into a managed context C ′ i = (LS i ′ , kbi, br ′i ,OPi, addi) over LS i = (BS Li , KBLi , {ACC Li }), where OP i = {add i} and addi interprets add(f) as addition of f, i.e., addi(O, kbi) = {(kbi ∪ {s | add(s) ∈ O}, ACCLi )} and br ′i ={add(s) ← body(r) | r ∈ bri ∧ hd(r) = s}. We call C ′ i the management version of Ci and for convenience we identify both. Managed MCS thus generalize ordinary MCS.

Proposition 1. LetM = (C1, . . . , Cn) be an MCS and M ′ = (C ′1 , . . . , C ′m) the mMCS where each C ′ i is the management version of Ci. Then S is an equilibrium of M iff S is an equilibrium of M ′ .

Example 6 (ctd). A bacteria DL ontology C3 and a generalized logic program C4 to derive further possible drug effects are added, using suitable logics and semantics (belief sets for C3 contain standard TBox subsumption inferences subs(kb)). Their knowledge bases are

As C2 and C3 have no bridge rules, they are simply cast into their management versions. C4 gets bridge rules

and the bridge rules of C1 are adapted: their heads use now the insert operation, and further rules that incorporate probable drug effects from C4 are added:

The resulting mMCS Mph = (C1, C2, C3, C4) has one equilibrium S = (S1, S2, S3, S4) where, omitting for brevity atoms of the form not a in S4, S2 = inf 2(kb2) = kb2, S3 = subs(kb3),

eff (azith, str pneu), eff (azith, leg pneu), eff (azith, leg pneu), isa(str pneu, bact),

4 Sample Instantiations

We consider instantiations of our framework, first discussing relational databases, logic programs, and belief revision. Second, we capture argumentation context systems by mMCSs.

Relational Databases. For relational databases, our running example already shows how a management function is used to realize view-updates. Many other operations on databases may be realized using managed contexts. In fact, e.g., the SQL language, ΣSQL, can be accomodated: a context whose management base is built upon ΣSQL and a management function mngSQL which realizes the SQL semantics. This allows to use SQL in an mMCS. Observe that the implementation of mngSQL is rather trivial, as existing implementations of SQL can be used via suitable interfaces, e.g., MySQL, Oracle DB, etc. In our running example, the respective view statement is:

CREATE VIEW eff AS SELECT drug, bacteria FROM treat WHERE credibility = evd;

To realize ordered sequences of SQL statements one may use timestamps in bridge rules handled by mngSQL.

Belief Revision. Change of logical theories and knowledge bases is a long-standing area in logic and AI. Central operations on beliefs are expansion, contraction, revision and update (see Peppas [2008] for an excellent survey).

Let L be a logic with set L of formulas and semantics ACCL, and let rev : 2L × L → 2L be a revision operator for theories in L. We may define a management function mngrev for the management base {revise}, e.g., as follows: mngrev(O, kb) = {(rev(kb, {φ1 ∧ . . . ∧ φn | revise(φi) ∈ O}), ACCL)}. Here, multiple revisions (n ≥ 2) are handled by conjunction; other realizations (e.g., iteration) exist.

Logic Programming. Various extensions of logic programs have been proposed, e.g., updates of logic programs [Alferes et al., 2002] which we use in our running example, debuggingsupport [Brain et al., 2007], or meta-reasoning support. Many of them are realized using meta-programming, i.e., they transform a logic program Pe and additional input I, into a logic program Pt, such that solutions to the problem given by Pe and I are obtained from Pt (without altering the semantics). In the mMCS framework, we can achieve this directly using a management function mng such that, for a program Pe and operational statements O encoding I, mng(O, Pe) = {(Pt, ACCLP )} where Pt is assembled from Pe and O, and ACCLP is the employed semantics of logic programs.

Example 7 (ctd). Suppose C4 uses the update semantics of Alferes et al. [2002], i.e., the semantics of upd is given by the respective program transformation. For the operational statement upd(not eff (pen, leg pneu)) which is applicable in the belief state S of Example 6, the relevant rules are

The ground instance (3) is rejected (not contained in the transformed program), intuitively because it is in conflict with the more recent information represented by (2). Therefore, the stable model does not contain eff (pen, leg pneu).

The ability of the management function to choose among different semantics allows one to flexibly select a suitable logic program semantics depending on the belief state.

E.g., one may enforce for a program in context Ci that paraconsistent semantics as in Sakama and Inoue [1995] is used if it has an inconsistent belief set, and answer set semantics otherwise. It is achieved by self-referential bridge rules mode pas(b) ← (i : ⊥) and mode as(b) ← not(i : ⊥), where ⊥ encodes inconsistency and mode x the semantic mode of use.

Argumentation Context Systems. Argumentation context systems (ACS) [Brewka and Eiter, 2009] are homogeneous: all reasoning components are Dung argumentation frameworks (AFs) [Dung, 1995]. Yet, in this restricted setting they provide some functionality which is relevant here: bridge rules not only extend context AFs, they may also invalidate arguments or attack relations, they may even select a semantics; moreover, they provide ways of resolving inconsistent updates.

This additional functionality is achieved by introducing for each context a mediator Med = (br , inc), which consists of a set br of bridge rules plus an inconsistency handling method inc. The heads of bridge rules are expressions in a genuine update description language. Based on inc, Med collects the heads of applicable bridge rules and returns one or several consistent sets of update statements, called acceptable updates.

A state S assigns to each context an update Ui and a set of arguments Asi. Equilibria (here called acceptable states) satisfy the following condition: each Asi must be an acceptable set of arguments for the context's AF updated with Ui, and Ui must be acceptable in S. It is not difficult to reconstruct this approach in the framework of mMCS. For each context Ci we choose Oi such that expressions of the ACS update language become operational statements. Furthermore, the management function mngi must capture the meaning of the update expressions and the mediator's consistency handling method. Due to space limitations we cannot provide more detail but want to point out that acceptable ACS states and equilibria of the respective mMCS are in 1-to-1 correspondence.

5 InconsistencyManagement

Different forms of inconsistency can arise in mMCS:

1. Nonexistence of equilibria: this global form of inconsistency was investigated in Eiter et al. [2010] for MCS.
2. Local inconsistency: even if equilibria exist, they may contain inconsistent belief sets. This presupposes an adequate notion of consistency (for belief sets and sets of formulas). In most context logics such a notion exists or is easily defined.
3. Operator inconsistency: the operations in the heads of applicable bridge rules are conflicting, e.g., operations like add(p) and delete(p), or add(p) and add(¬p).

Handling inconsistencies of type 2 and 3 is one of the motivations that led to the development of mMCS. For type 1 inconsistencies the techniques from Eiter et al. [2010] can be adapted and, given suitable context managers, yield more adequate and precise means for diagnosis.

5.1 Local consistency

We now demonstrate how local consistency can be achieved by using adequate managers. We call a management function mng local consistency (lc-) preserving iff, for each set O of operational statements and each KB kb, in every pair (kb ′ , ACC) ∈ mng(O, kb) the KB kb ′ is consistent. Furthermore, an mMCSM is locally consistent iff in each equilibrium S = (S1, . . . , Sn) of M, all Si are consistent belief sets.

Proposition 2. Let M be an mMCS such that all management functions are lc-preserving. Then M is locally consistent.

How to define lc-preserving managers? To simplify matters we assume all contexts are based on propositional logic with classical consistency and semantics, given by ACCpl , and consider a single operator add with the obvious meaning. We proceed by: (1) selecting a base revision operator rev satisfying consistency preservation (revising a propositional KB with a consistent formula always results in a consistent KB); (2) picking maximal consistent subsets of the formulas to be added. Let FO = {p | add(p) ∈ O} and let MC(FO) be the set of maximal consistent subsets of FO. Now define mng(O, kb) = {(rev (kb, ∧ F) , ACCpl ) | F ∈ MC(FO)} .

This management function is obviously lc-preserving. Further refinements, e.g., based on additional preferences among bridge rules, are straightforward.

5.2 Global consistency

Previous work on inconsistency management in MCS (cf. Eiter et al. [2010]) introduced two basic notions: diagnoses and explanations. The former is consistency-based and intuitively characterizes bridge rules and corresponding modifications to obtain a consistent MCS, the latter is entailment-based and gives bridge rules that create resp. inhibit inconsistency. Both notions extend to mMCS.

Let brM denote the set of all bridge rules of an mMCS M, let hd(R) = {hd(r) | r ∈ R} for R ⊆ brM, and let M[R] denote the mMCS where only bridge rules in R occur.

A diagnosis is a pair of sets of bridge rules, such that: if the rules in the first set are deactivated, and the rules in the second set are added in unconditional form (an extremal form of strengthening sufficient to detect culprit rules) the mMCS becomes consistent (i.e., admits an equilibrium). Formally, given an mMCS M, a diagnosis of M is a pair (D1,D2), D1, D2 ⊆ brM, s.t. M[brM \ D1 ∪ hd(D2)] ̸|= ⊥. D±(M) is the set of all such diagnoses and D±m(M) denotes the set of all pointwise subset-minimal diagnoses.

An explanation is a pair of sets of bridge rules, such that their presence, resp. non-applicability, causes a relevant inconsistency in the given mMCS. Formally, given an mMCS M, an explanation of M is a pair (E1, E2) of sets E1, E2 ⊆ brM s.t. for all (R1, R2) where E1 ⊆ R1 ⊆ brM and R2 ⊆ brM \E2, it holds that M[R1 ∪ hd(R2)] |= ⊥. E±(M) denotes the set of all inconsistency explanations of M, and E±m(M) the set of all pointwise subset-minimal ones.

Example 8 (ctd). Suppose to improve Mph by adding a further bridge rule r1 : insert(t)← not(4 : t) to br1, where t =ineff (water, leg pneu). It should ensure that water is considered ineffective, even if C4 does not derive this. The resulting mMCS M ′ph is inconsistent: if t ̸∈ S4, then t ∈ S1 must hold, implying t ∈ S4, a contradiction; if t ∈ S4 then t ̸∈ S1 follows, which implies t ̸∈ S4, again a contradiction.

Let r2 be the rule of form upd(t)←(1 : t) in br4. Then M ′ph has one minimal explanation, ({r1, r2}, {r1, r2}), and 4 minimal diagnoses: ({r1}, ∅), ({r2}, ∅), (∅, {r1}), (∅, {r2}).

One of the basic functions of context managers is to ensure an acceptable belief set of a context regardless of its applicable operational statements. We call a context Ci with knowledge base kbi in an mMCs M totally coherent iff for every belief state S of M some (kb ′ , ACC i) ∈ mng i(appi(S), kbi) exists s.t. ACCi(kb ′ ) ̸= ∅; and Ci totally incoherent iff no belief state S fulfills the previous condition.

Note that any context with an lc-preserving management function is totally coherent; the opposite need not be the case.

Example 9 (ctd). All contexts of Mph and M ′ph are totally coherent. Indeed, for C2 and C3 this holds trivially, as they have no bridge rules. Similarly, for C1 each insertion of tuples yields a knowledge base with an acceptable belief set (as eff and ineff may share tuples, the belief set may be regarded to be inconsistent). For C4 we observe that the logic program has no stable model only if eff (X, B) and not eff (X, B) are derived for some (X, B). The atom not eff (X, B) however, can only hold for atoms added through the upd operation whose semantics guarantees that eff (X, B) is no longer derivable. Therefore C4 has always an acceptable belief set.

This shows that total coherence can not prevent inconsistency of the whole mMCS caused by cyclic information flow.

On the other hand, context managers can ensure the existence of diagnoses. To guarantee the existence of a diagnosis for an MCSM, Eiter et al. [2010] require that M[∅] is consistent. For mMCS we can replace this premise by the considerably weaker assumption that no context is totally incoherent.

Proposition 3. Let M be an inconsistent mMCS. Then D±(M) ̸= ∅ iff no context of M is totally incoherent.

The following proposition establishes that all possible inconsistencies are caused by cycles given that all context managers are totally coherent. Note, however, that not every cycle causes inconsistency, and that due to potential nonmonotonicity inside contexts the number of negative beliefs in a cycle is not relevant. Let M = (C1, . . . ,Cn) be an mMCS, we write ref r(i, j) iff r is a bridge rule of context Ci and (Cj: p) occurs in the body of r. For an mMCS M and r1, . . . , rk ∈ brM, we say that (r1, . . . , rk) forms a cycle iff ref r1 (i1, i2), . . . , ref rk-1 (ik-1, ik), and ref rk (ik, i1) hold.

Proposition 4. Let M be an inconsistent mMCS with totally coherent contexts. Then for every minimal explanation (E1, E2) ∈ E±m(M) there exists a cycle (r1, . . . , rk) such that E1 = {r1, . . . , rk}.

The (indirect) proof hinges on the following observations: if no cycle of rules in E1 causes inconsistency, then there exists a 'leave' context C causing inconsistency, contradicting total coherence; by minimality the cycle contains all r ∈ E1.

Example 10 (ctd). For M ′ph and its minimal explanations E±m(M ′ph ) = {({r1, r2}, {r1, r2})}, (r1, r2) is a cycle.

Importantly, for acyclic-in particular for hierarchicmMCS, total coherency is sufficient for global consistency.

Corollary 1. Any acyclic, mMCS with totally coherent contexts has an equilibrium.

6 Complexity

We consider here the consistency problem CONS(M), i.e., given an mMCS M = (C1, . . . ,Cn), decide whether it has some equilibrium. For this, we can utilize output-projected belief states similar as in Eiter et al. [2010]. For context Ci, let OUTi be the set of all beliefs p occurring in the body of some bridge rule in M. Then, the output-projection of a belief state S = (S1, . . . , Sn) of M is the belief state S′ = (S′1 , . . . , S′n ), S′ i = Si ∩ OUTi, for 1 ≤ i ≤ n. For consistency checking, we can concentrate on output-projections of equilibria:

Proposition 5. An mMCSM = (C1, . . . , Cn) is consistent iff some output-projected belief state S′ = (S′1 , . . . , S′n ), exists such that, for all 1 ≤ i ≤ n, S′ i ∈ {Si ∩ OUTi | Si ∈ ACC i(kb ′i ) ∧ (kb ′i , ACC i) ∈ mng i(appi(S′ ), kbi)}.

Generalizing Eiter et al. [2010], let the context complexity of Ci be the complexity of the following problem:

• (CC) Decide, given a set Oi of operator statements and S′ i ⊆ OUTi, whether some (kb ′i ,ACCi) ∈ mngi(Oi, kbi) and Si ∈ ACCi(kb ′i ) exist s.t. S′ i = Si ∩ OUT i.

Here, Ci is explicitly represented by kbi and bri, and the logic suite is implicit, i.e., an oracle decides existence of Si. The context complexity CC(M) of an mMCS M is a (smallest) upper bound for the context complexity classes of all Ci.

Depending on CC(M), the complexity of consistency checking for some complexity classes is shown in the following table, where i ≥ 1, and entries denote membership results, resp. completeness results if CC is hard for some Ci:

Using simple insert/delete management, an example of CC(M) in P would be an mMCS built on defeasible logic (cf. Maher [2001]), and one for NP (resp., ΣP2 ) using normal (disjunctive) answer set programs. Argumentation context systems [Brewka and Eiter, 2009] provide examples of mMCSs with context complexity in ΔP3 ; examples for PSPACE and EXPTIME can be found, e.g., among modal and description logics. Such contexts also have respective hard instances.

Problem CC intuitively consists of two subproblems: (MC) compute some (kb ′i ,ACCi) ∈ mngi(Oi, kbi) and (EC) decide whether Si ∈ ACCi(kb ′i ) exists s.t. S′ i = Si ∩OUTi. However, it makes sense to analyze consistency depending on CC: often MC is solvable in polynomial time (perhaps nondeterministically and/or with the help of an oracle) or polynomial space, but kb ′i may become exponentially large (e.g., using a KB update or revision operator), nevertheless its explicit construction is avoidable for solving EC. If the output of MC remains polynomial, then the complexity of CC can suitably be characterized in terms of MC (e.g., maximal consistent subsets of a propositional theory) and EC. We leave more detailed results for an extended version.

7 Conclusion

Zhao et al. [2009] point out that simplified MCSs, where all bridge rules are of the form a ← (ci : a), are important for practical matters. Such MCSs are less expressive, as complex rule bodies and negation (thus nonmonotonic information flow) are not supported. In the presence of context managers, however, an analogous restriction does not impair expressivity: using, e.g., bridge rules o(ci,a)(b) ← (ci : a) with designated operations o(ci,a), the management functions can emulate any bridge rule (1). In fact, every MCS M can be easily transformed into such an mMCS M ′ having the same equilibria.

An interesting issue for future work are refined semantics for mMCS to discriminate among equilibria, such as an extension of minimal or grounded equilibria [Brewka and Eiter, 2007] to mMCS. Moreover, as mMCS may yield alternative knowledge bases, preference of equilibria may be based on preference of alternatives. In particular for consistency restoring, minimality of change seems natural. Investigating this and developing mMCS implementations are on our agenda.