Towards Inconsistency Management in Reactive Multi-Context Systems Gerhard Brewka1 and Stefan Ellmauthaler1 and Ricardo Gonçalves2 and Matthias Knorr2 and João Leite2 and Jörg Pührer1 Abstract. In this paper, we begin by introducing reactive multi- over immediate nutrition. Naturally, if Dave is not gone long enough, context systems (rMCSs), a framework for reactive reasoning in and no sensor shows any potential problems (smoke, gas, fire, etc.), the presence of heterogeneous knowledge sources. In particular, then the system should seamlessly take no action. Another illustrative we show how to integrate data streams into multi-context systems example would be a situation where the system observes that Dave’s (MCSs) and how to model the dynamics of the systems, based on smart watch is indicating a high heart rate (tachycardia), in which two types of bridge rules. We then discuss various methods for han- case it would request Dave to measure his blood pressure (hyperten- dling inconsistencies, a problem that occurs with reasoning based on sion) – calling for assistance if Dave ignores the request – and, based multiple knowledge sources that need to be integrated, with a special on the measurements, determine whether to raise an alarm, calling focus on non-existence of equilibria. an ambulance for example, or whether the readings are caused by some infection already under treatment or a decongestant that Dave recently took, in which case nothing would need to be done. 1 Introduction The wide and increasing availability of machine-processable data The requirements posed by novel applications such as the one just de- and knowledge – fueled by initiatives such as the Semantic Web, scribed, together with the availability of a vast number of knowledge Linked Open Data, and the Internet of Things, among others – has bases – written using many different formalisms – and streams of prepared the ground and called for a new class of dynamic, rich, data/events produced by sensors/detectors, has led modern research knowledge-intensive applications. Such new applications require au- in knowledge representation and reasoning to face two fundamental tomated reasoning based on the integration of several heterogeneous problems: dealing with the integration of heterogeneous data and knowledge bases – possibly overlapping, independently developed, knowledge, and dealing with the dynamics of such novel knowledge and written in distinct languages with different semantic assumptions based systems. – together with data/event streams produced by sensors and detec- tors, to support automation and problem-solving, to enforce traceable Integration The first problem stems from the availability of and correct decisions, and to facilitate the internalization of relevant knowledge bases written in many different languages and formats dynamic data and knowledge. developed over the last decades, from the rather basic ones, such as Consider, for example, a scenario where Dave, an elderly person relational databases or the more recent triple-stores, to the more ex- suffering from dementia, lives alone in an apartment equipped with pressive ones, such as ontology languages (e.g., description logics), various sensors, e.g., smoke detectors, cameras, and body sensors temporal and modal logics, non-monotonic logics, or logic programs measuring relevant body functions (e.g., pulse, blood pressure, etc.). under answer set semantics, to name just a few. Each of these for- An assisted living application in such a scenario could leverage the malisms was developed for different purposes and with different de- information continuously received from the sensors, together with sign goals in mind. Whereas some of these formalisms could be com- Dave’s medical records stored in a relational database, a biomedical bined to a new, more expressive formalism, with features from its health ontology with information about diseases, their symptoms and constituents – such as dl-programs [13] and Hybrid MKNF [31, 27] treatments, represented in some description logic, some action policy which, to different extent, combine description logics and logic pro- rules represented as a non-monotonic logic program, to name only a grams under answer set semantics –, in general this is simply not few, and use it to detect relevant events, suggest appropriate action, feasible, either due to the mismatch between certain assumptions un- and even raise alarms, while keeping a history of relevant events and derlying their semantics, or because of the high price to pay, often Dave’s medical records up to date, thus allowing him to live on his in terms of complexity, sometimes even in terms of decidability. It is own despite his condition. For example, after detecting that Dave left nowadays widely accepted that there simply is no such thing as a sin- the room while preparing a meal, the system could warn him about gle universal, general purpose knowledge representation language. the situation in case he does not return soon. It could also even turn What seems to be needed is a principled way of integrating knowl- the stove off in case it detects that Dave fell asleep, not wanting to edge expressed in different formalisms. wake him up because his current treatment/health status values rest Multi-context systems (MCSs) provide a general framework for 1 this kind of integration. The basic idea underlying MCSs is to leave Institute of Computer Science, Leipzig University, Germany, email: {brewka|ellmauthaler|puehrer}@informatik.uni-leipzig.de. the diverse formalisms and knowledge bases untouched, and to use 2 NOVA LINCS & Departamento de Informática, Universidade NOVA de so-called bridge rules to model the flow of information among differ- Lisboa, Portugal, email: {rjrg|mkn|jleite}@fct.unl.pt. ent parts of the system. An MCS consists of reasoning units – called contexts for historical reasons [22] – where each unit is equipped tions we envision, such as those that need to integrate heterogeneous with a collection of bridge rules. In a nutshell, the bridge rules al- knowledge bases. Additionally, reacting to the streams of incoming low contexts to “listen” to other contexts, that is to take into account information is only part of the dynamic requirements of our appli- beliefs held in other contexts. cations. In many cases, the incoming information is processed only Bridge rules are similar to logic programming rules (including de- once, perhaps requiring complex reasoning using various knowledge fault negation), with an important difference: they provide means to bases to infer the right way to react, and does not have to be dealt access other contexts in their bodies. Bridge rules not only allow for with again – e.g., concluding that nothing needs to be done after de- a fully declarative specification of the information flow, but they also termining that the tachycardia is caused by the decongestant recently allow information to be modified instead of being just passed along taken by Dave. In other cases, it is important that these observations as is. Using bridge rules we may translate a piece of information into not only influence the current reaction of the system – do nothing the language/format of another context, pass on an abstraction of the in the previous example – but, at the same time, be able to change original information, leaving out unnecessary details, select or hide the knowledge bases in a more permanent way, i.e., allowing for the information, add conclusions to a context based on the absence of internalization of knowledge. For example, relevant observations re- information in another one, and even use simple encodings of pref- garding Dave’s health status should be added to his medical records, erences among parent contexts. such as for example that he had an episode of tachycardia caused by Historically, MCSs went through several development steps until a decongestant, and, in the future, maybe even revise such episode if they reached their present form. Advancing work in [21, 30] aiming it is found that Dave had forgotten to take the decongestant after all. to integrate different inference systems, monotonic heterogeneous Other more sophisticated changes in the knowledge bases include, multi-context systems were defined in [22], with reasoning within for example, an update to the biomedical health ontology whenever as well as across monotonic contexts. The first, still somewhat lim- new treatments are found, the revision of the policy rules whenever ited attempts to include non-monotonic reasoning were done in [33] some exceptions are found, etc. EVOLP [1] extends logic program- and [10], where default negation in the rules is used to allow for rea- ming under answer set semantics with the possibility to specify its soning based on the absence of information from a context. evolution, through successive updates, in reaction to external obser- The non-monotonic MCSs of [7] substantially generalize previous vations. It is nevertheless limited to a single knowledge representa- approaches, by accommodating heterogeneous and both monotonic tion formalism and to a single operation (update). and non-monotonic contexts, hence capable of integrating, among In this paper, we aim to address these challenges. We develop a many others, “typical” monotonic logics like description logics or system that allows us to integrate heterogeneous knowledge bases temporal logics, and non-monotonic formalisms like Reiter’s default with streams of incoming information and to use them for continu- logic, logic programs under answer set semantics, circumscription, ous online reasoning, reacting, and evolving the knowledge bases by defeasible logic, or theories in autoepistemic logic. The semantics of internalizing relevant knowledge. To this end, we introduce reactive nonmonotonic MCSs is defined in terms of equilibria: a belief set for Multi-Context Systems (rMCSs). These systems build upon mMCSs each context that is acceptable for its knowledge base augmented by and thus provide their functionality for integrating heterogeneous the heads of its applicable bridge rules. knowledge sources, admitting also relevant operations on knowledge More recently, the so-called managed MCSs (mMCSs) [8] ad- bases. In addition, rMCSs can handle continuous streams of input dressed a limitation of MCSs in the way they integrate knowledge data. Equilibria remain the fundamental underlying semantic notion, between contexts. Instead of simply adding the head of an applicable but the focus now lies on the dynamic evolution of the systems. In a bridge rule to the context’s knowledge base, which could cause some nutshell, given an initial configuration of knowledge bases, that is, an inconsistency, mMCSs allow for operations other than addition, such initial knowledge base for each context, a specific input stream will as, for instance, revision and deletion, hence dealing with the prob- lead to a corresponding stream of equilibria, generated by respective lem of consistency management within contexts. updates of the knowledge bases. Contrary to standard MCSs which possess only one type of bridge rules modeling the information flow Dynamics The second problem stems from the shift from static which needs to be taken into account when equilibria are computed knowledge-based systems that assume a one-shot computation, usu- (or the operations that need to be applied in case of mMCSs), rMCSs ally triggered by a user query, to open and dynamic scenarios where have an additional, different type of bridge rules, distinguished by the there is a need to react and evolve in the presence of incoming infor- occurrence of the operator next in the head. These rules are used to mation. specify how the configuration of knowledge bases evolves whenever Indeed, traditional knowledge-based systems – including the dif- an equilibrium was computed. ferent variants of MCSs mentioned above – focus entirely on static The reactive Multi-Context Systems (rMCSs) presented here com- situations, which is the right thing for applications such as for in- bine and unify the two adaptations of multi-context systems for dy- stance expert systems, configuration or planning problems, where the namic environments in [9] and [24], independently developed by dif- available background knowledge changes rather slowly, if at all, and ferent subsets of the authors. The approach presented here general- where all that is needed is the solution of a new instance of a known izes these earlier approaches and substantially improves on the pre- problem. However, the new kinds of applications we consider are sentation of the underlying concepts. becoming more and more important, and these require continuous The occurrence of inconsistencies within frameworks that aim at online reasoning, including observing and reacting to events. integrating knowledge from different sources cannot be neglected, There are some examples of systems developed with the purpose even more so in dynamic settings where knowledge changes over of reacting to streams of incoming information, such as Reactive time. Even with the power of management operations that allow the ASP [19, 18], C-SPARQL [5], Ontology Streams [29] and ETALIS specification of e.g. belief revision operations, many reasons remain [2], to name only a few. However, they are very limited in the kind why rMCSs may fail to have an equilibria stream, traceable to in- of knowledge that can be represented, and the kind of reasoning al- dividual contexts, their interaction through the bridge rules, or their lowed, hence unsuitable to address the requirements of the applica- interaction with the input streams, which can render the entire system useless. In this paper, we will address the problem of inexistent equi- ontologies, BS d is the set of deductively closed subsets of L, and libria streams, also known as global inconsistency, following differ- accd maps every kb ∈ KB d to {E}, where E is the set of formulas ent strategies, such as repairing the rMCS, or even relaxing the notion in L entailed by kb. of equilibria stream so that it can go through inconsistent states. As an example for a non-deterministic formalism, consider logic The paper is organized as follows. In Section 2, we introduce re- programs under the answer set semantics [20]. Given a set of active MCSs, our framework for reactive reasoning in the presence ground, i.e., variable-free, atoms A, we consider the logic La = of heterogeneous knowledge sources. In particular, we show how to hKB a , BS a , acca i, such that KB a is the set of all logic programs integrate data streams into mMCSs and how to model the dynam- over A. The set of possible belief sets is given by the set BS a = 2A ics of our systems, based on two types of bridge rules. Reasoning of possible answer sets and the function acca maps every logic pro- based on multiple knowledge sources that need to be integrated faces gram to the set of its answer sets. the problem of potential inconsistencies. Section 3 discusses various Given a set E of entries, a simple logic for storing elements from methods for handling inconsistencies, with a special focus on non- E can be realized by the logic Ls = hKB s , BS s , accs i, such that existence of equilibria. We conclude and point out future directions KB s = BS s = 2E , and accs maps every set E 0 ⊆ E to {E 0 }. of work in Section 4. Such Ls can, e.g., be used to represent a simple database logic. We will call a logic of this type a storage logic. 2 Reactive Multi-Context Systems In addition to a logic that captures language and semantics of a Reactive multi-context systems (rMCSs) make use of basic ideas formalism to be integrated in an rMCS, a context also describes how from managed multi-context systems (mMCSs) [8] which extend a knowledge base belonging to the logic can be manipulated. To this multi-context systems (MCSs) as defined by Brewka and Eiter [7] end, we make use of a management function similar as in managed by management capabilities. In particular, similar to mMCSs, we multi-context systems [8]. will make use of a management function and bridge rules that al- Definition 1 (Context) A context is a triple C = hL, OP , mngi low for conflict resolution between contexts as well as a fine-grained where declarative specification of the information flow between contexts. To not unnecessarily burden the reader with repetetive material on • L = hKB , BS , acci is a logic, these common components, we abstain from recalling the details of • OP is a set of operations, mMCSs first. It will be clear from the presentation when new con- • mng : 2OP × KB → KB is a management function. cepts/ideas specific to rMCSs will be presented. For an indexed context Ci we will write Li = hKB i , BS i , acci i, OP i , and mngi to denote its components. Note that we leave the ex- 2.1 Specifying the Components of an rMCS act nature of the operations in OP unspecified. They can be seen as Similar as for previous notions of MCSs, we build on an abstract no- mere labels that determine how the management function should ma- tion of a logic, which is a triple L = hKB , BS , acci, where KB nipulate the knowledge base: we use subsets OP 0 of OP as the first is the set of admissible knowledge bases of L, which are sets whose argument of the management function that maps a knowledge base elements are called knowledge base formulas; BS is the set of pos- to an updated version depending on the presence or absence of oper- sible belief sets, where elements in belief sets are called beliefs; and ations in OP 0 . Thus, it is the management function that implements acc : KB → 2BS is a function describing the semantics of L by the semantics of the operations. We use a deterministic management assigning to each knowledge base a set of acceptable belief sets.3 function rather than a non-deterministic one as used in mMCS [8]. Note that it is straightforward to adapt our definitions to use non- Example 1 We illustrate how different formalisms can be repre- deterministic management functions as well. However, as they are sented by the notion of a logic. The logics presented below will serve not essential to our approach, we here refrain from doing so to keep as blueprints for the logics we use in examples throughout the pa- notation simpler. per. First, consider the case of classical propositional logic. Given a propositional signature Σ, we denote by F the set of all well- Example 2 Consider the assisted living scenario from the Introduc- formed propositional formulas over Σ. To represent entailment in tion and remember that we target a system that recognizes potential classical propositional logic over signature Σ, we consider the logic threats caused by overheating of the stove in Dave’s kitchen. We use Lp = hKB p , BS p , accp i, such that the admissible knowledge bases the context Cst to monitor the stove. Its logic Lst is a storage logic are given by the set KB p = 2F . Since propositional logic aims at taking E = {pw, tm(cold ), tm(hot)} as the set of entries, repre- modeling ideal rational reasoning, we identify the set of possible be- senting the stove’s power status (on if pw is present, and off other- lief sets BS p with the set of deductively closed sets of formulas over wise) and a qualitative value for its temperature (cold/hot). At all Σ. Finally, accp maps every kb ∈ KB p to {E}, where E is the set times, the current temperature and power state of the stove should be of formulas entailed by kb. stored in a knowledge base over Lst . Thus, the context provides the Quite similar in spirit are description logics (DLs) as (commonly operations decidable) fragments of first-order logic [4]. Given a DL language L, we consider the logic Ld = hKB d , BS d , accd i where KB d is OP st = {setPower(off ), setPower(on), the set of all well-formed DL knowledge bases over L, also called setTemp(cold ), setTemp(hot)} 3 To ease readability, throughout the paper, we will often use the following to update the information in the knowledge base. convention when writing symbols: single entities are lower-case, while sets Before defining the management function we need to clarify what of entities and structures with different components are upper-case; in ad- dition, sequences of those are indicated in sans serif, while notions with we want this function to achieve. We assume the existence of a single a temporal dimension are written in calligraphic letters (only upper-case, temperature sensor constantly providing a measurement which trig- such as S or I); finally, operators and functions are bold. gers exactly one of the setTemp operations. For this reason, there is no need for the management function to care about persistence of the Definition 3 (Reactive Multi-Context System) A reactive Multi- temperature value, or about conflicting information. The power in- Context System (rMCS) is a tuple M = hC, IL, BRi, where formation, on the other hand, is based on someone toggling a switch, so we definitely need persistence of the fluent pw. • C = hC1 , . . . , Cn i is a tuple of contexts; The semantics of the operations is thus given, for OP 0 ⊆ OP st , • IL = hIL1 , . . . , ILk i is a tuple of input languages; by the management function mngst (OP 0 , kb) = • BR = hBR 1 , . . . , BR n i is a tuple such that each BR i , i ∈ {1, . . . , n}, is a set of bridge rules for Ci over C and IL. {pw | setPower(on) ∈ OP 0 ∨ (pw ∈ kb ∧ setPower(off ) 6∈ OP 0 )}∪ Example 3 We continue by using context Cst from Example 2 as {tm(t) |setTemp(t) ∈ OP 0 }. the single context of the rMCS Mex3 = hhCst i, hILex3 i, hBR ex3 ii.4 As discussed above, the function simply inserts the current qualita- The input language ILex3 = {switch} is used to report whether the tive temperature value. For the power, it ensures that the stove is switch for changing the power state of the stove has been turned. The considered on whenever it is switched on, and also when it is not bridge rules in BR ex3 are given by being switched off and already considered on in the given knowl- next(setPower(on)) ← ex3::switch, not st:pw. edge base kb. The second alternative implements persistence. Note that whenever both conflicting setPower operations are in OP 0 , next(setPower(off )) ← ex3::switch, st:pw. setPower(on) “wins”, that is, pw will be in the knowledge base. and react to switching the stove on or off: depending on the current This is justified by the application: the damage of, say, unnecessarily power state of the stove that is stored in a knowledge base associated turning off the electricity is a lot smaller than that of overlooking a to Cst , whenever the switch is activated, the bridge rules derive an potential overheating of the stove. update of the knowledge base where the power state is reversed. Assume we have a knowledge base kb = {tm(cold )}. Then, an update with the set OP = {setPower(on), setTemp(hot)} of op- erations would result in the knowledge base mngst (OP , kb) = 2.2 Reacting to External Inputs - Semantics of {pw, tm(hot)}. rMCSs Contexts exchange information by manipulating their associated To define the semantics of rMCSs, we first focus on the static case knowledge bases using the management function. The central de- of a single time instant, and only subsequently introduce the corre- vice for that is given by bridge rules that are rules similar in spirit sponding dynamic notions for reacting to inputs changing over time. to those in logic programming and that determine which operations We start with the evaluation of bridge rules, for which we need to from OP i to apply to kb i in a context Ci . In this work, we are inter- know current beliefs and current external information. The former is ested in systems composed of contexts whose behavior may not only captured by the notion of a belief state denoted by a tuple of belief depend on other contexts, but also on input from the outside. Like sets – one for each context – similar as in previous work on multi- communication between contexts, also external information is incor- context systems. porated by means of bridge rules. To keep the approach as abstract as possible, all we require is that inputs are elements of some for- Definition 4 (Belief State) Let M = hhC1 , . . . , Cn i, IL, BRi be an mal input language IL. Moreover, we allow for situations where in- rMCS. Then, a belief state for M is a tuple B = hB1 , . . . , Bn i such put comes from different sources with potentially different input lan- that Bi ∈ BS i , for each i ∈ {1, . . . , n}. We use BelM to denote the guages and thus consider tuples hIL1 , . . . , ILk i of input languages. set of all beliefs states for M . Definition 2 (Bridge Rule) Let C = hC1 , . . . , Cn i be a tuple of In addition, to also capture the current external information, we contexts and IL = hIL1 , . . . , ILk i a tuple of input languages. A introduce the notion of an input. bridge rule for Ci over C and IL, i ∈ {1, . . . , n}, is of the form Definition 5 (Input) Let M = hC, hIL1 , . . . , ILk i, BRi be an op ←a1 , . . . , aj , not aj+1 , . . . , not am (1) rMCS. Then an input for M is a tuple I = hI1 , . . . , Ik i such that such that op = op or op = next(op) for op ∈ OP i , j ∈ Ii ⊆ ILi , i ∈ {1, . . . , k}. The set of all inputs for M is denoted by {0, . . . , m}, and every atom a` , ` ∈ {1, . . . , m}, is one of the fol- InM . lowing: We are now ready to define when literals (in bridge rule bodies) • a context atom c:b with c ∈ {1, . . . , n} and b ∈ B for some B ∈ are satisfied. BS c , or Definition 6 (Satisfaction of Literals) Let M = hC, IL, BRi be an • an input atom s::b with s ∈ {1, . . . , k} and b ∈ ILs . rMCS such that C = hC1 , . . . , Cn i and IL = hIL1 , . . . , ILk i. For a bridge rule r of the form (1) hd(r) denotes op, the head of r, Given an input I = hI1 , . . . , Ik i for M and a belief state B = while bd(r) = {a1 , . . . , aj , not aj+1 , . . . , not am } is the body of hB1 , . . . , Bn i for M , we define the satisfaction of literals given I r. A literal is either an atom or the default negation of an atom, and and B as: we also differentiate between context literals and input literals. • hI, Bi |= a` if a` is of the form c:b and b ∈ Bc ; Roughly, a set of bridge rules for Ci describes which operations • hI, Bi |= a` if a` is of the form s::b and b ∈ Is ; to apply to its knowledge base kb i depending on whether currently • hI, Bi |= not a` if hI, Bi 6|= a` . available beliefs and external inputs match the literals in the body. We define and discuss their precise semantics later in Section 2.2. Bridge Let r be a bridge rule for Ci over C and IL. Then rules can be seen as the glue that binds the contexts in an rMCS to- gether. Thus, we are now ready to define reactive multi-context sys- 4 Throughout the paper we sometimes use labels (such as st in C ) instead st tems. of numerical indices in our examples. • hI, Bi |= bd(r) if hI, Bi |= l for every l ∈ bd(r). With all this in place, we can finally show how an rMCS behaves in the presence of external information that changes over time. For If hI, Bi |= bd(r), we say that r is applicable under I and B. The op- this purpose, we assume that an rMCS receives data in a stream of erations encoded in the heads of applicable bridge rules in an rMCS inputs, i.e., an input for each time instant, and we represent individual determine which knowledge base updates should take place. We col- time instants by natural numbers. These can be interpreted as logical lect them in two disjoint sets. time instants that do not necessarily represent specific physical time Definition 7 (Applicable Bridge Rules) Let M = hC, IL, BRi be points. In particular, we do not assume that every pair of consecutive an rMCS such that C = hC1 , . . . , Cn i and BR = hBR1 , . . . , BRn i. natural numbers represents equidistant physical time spans. Given an input I for M and a belief state B for M , we define, for each i ∈ {1, . . . , n}, the sets Definition 11 (Input Stream) Let M = hC, IL, BRi be an rMCS such that IL = hIL1 , . . . , ILk i. An input stream for M (until τ ) is a • appnow i (I, B) = {hd(r) | r ∈ BR i , hI, Bi |= bd(r), hd(r) ∈ function I : [1..τ ] → InM where τ ∈ N ∪ {∞}. OP i }; • appnext i (I, B) = {op | r ∈ BR i , hI, Bi |= bd(r), hd(r) = We will conveniently omit the term “until τ ” whenever the limit of next(op)}. the stream is irrelevant. Conversely, we will provide an explicit τ , when we are only interested in the first τ time instants or when we Intuitively, the operations in appnow i (I, B) are used for computing want to state that the input stream is infinite (in case τ = ∞). Clearly, temporary changes that influence the semantics of an rMCS for a an input stream for M until τ also fully determines an input stream single point in time. The operations in appnext (I, B) on the other i for M until τ 0 for every 1 ≤ τ 0 < τ . hand are used for changing knowledge bases over time. They are not For any stream, we commonly represent the functional notation by used for computing the current semantics but are applied in the next a superscript, e.g., given an input stream I and t ∈ [1..τ ], we will point in time depending on the current semantics. This continuous use I t to denote I(t), i.e., the input hI1 , . . . , Ik i for M at time t. We change of knowledge bases over time is the reason why, unlike in also term stream the restriction of an input stream I to a single input previous work on MCSs, we do not consider knowledge bases as language ILi , which can be understood as a function Ii : [1..τ ] → part of the contexts to which they are associated but store them in a 2ILi that is fully determined by I. separate configuration structure defined next. Note that I t encapsulates (input) data for every input language of Definition 8 (Configuration of Knowledge Bases) Let M . Hence, we assume that, at every time instant, we have informa- M = hC, IL, BRi be an rMCS such that C = hC1 , . . . , Cn i. A con- tion from every external source of the rMCS. This synchronous ap- figuration of knowledge bases for M is a tuple KB = hkb 1 , . . . , kb n i proach is required since the evaluation of a bridge rule may depend such that kb i ∈ KB i , for each i ∈ {1, . . . , n}. We use ConM to on the availability of information from multiple streams. One possi- denote the set of all configurations of knowledge bases for M . bility for modeling external sources that do not continuously provide information is setting Ist to the empty set for representing a lack of The semantics of an rMCS for a single time instant is given in input from the source with language ILs at time t. terms of its equilibria. The semantics of an rMCS over time is given by its equilibria Definition 9 (Equilibrium) Let M = hhC1 , . . . , Cn i, IL, BRi be streams for a given initial configuration of knowledge bases and an an rMCS, KB = hkb 1 , . . . , kb n i a configuration of knowledge bases input stream for the system. for M , and I an input for M . Then, a belief state B = hB1 , . . . , Bn i Definition 12 (Equilibria Stream) Let M = hC, IL, BRi be an for M is an equilibrium of M given KB and I if, for each i ∈ rMCS, KB a configuration of knowledge bases for M , and I an in- {1, . . . , n}, we have that put stream for M until τ where τ ∈ N ∪ {∞}. Then, an equilibria Bi ∈ acci (kb 0 ), where kb 0 = mngi (appnow i (I, B), kb i ). stream of M given KB and I is a function B : [1..τ ] → BelM such that Example 4 Consider rMCS Mex3 from Example 3 and the config- uration KB = hkb st i of knowledge bases for Mex3 with kb st = ∅, • Bt is an equilibrium of M given KBt and I t , where KBt is in- representing that the stove is turned off. Moreover, consider the in- ductively defined as put I = h{switch}i for Mex3 and the belief state B = h∅i for – KB1 = KB Mex3 . As both bridge rules in BR ex3 use the next operator, we have appnow st (I, B) = ∅ and consequently, following the defini- – KBt+1 = updM (KBt , I t , Bt ). tion of the management function mngst in Example 2, kb st re- mains unchanged, i.e., mngst (appnow We will also refer to the function KB : [1..τ ] → ConM as the con- st (I, B), kb st ) = kb st . Thus, accst (mngst (appnow (I, B), kb st )) = {∅}. It follows that B is an figurations stream of M given KB, I, and B. st equilibrium of Mex3 given KB and I. Note that the limit τ of an equilibria stream is aligned with that of Based on an equilibrium at the current time instant, we can com- the given input stream. Following the definition, it is easy to see that pute an updated configuration of knowledge bases using the update if we have an equilibria stream B of M given KB and I, then the function as introduced in the following. substream of B of size τ 0 , with τ 0 ≤ τ , is an equilibria stream of M given KB and I 0 , where I 0 is the substream of I of size τ 0 . This Definition 10 (Update Function) Let M = hC, IL, BRi be an implies that, conversely, each extension of the input stream can only rMCS such that C = hC1 , . . . , Cn i, KB = hkb 1 , . . . , kb n i a lead to equilibria streams that extend those obtained given the origi- configuration of knowledge bases for M , I an input for M , and nal input stream. B a belief state for M . Then, the update function for M is de- fined as updM (KB, I, B) = hkb 01 , . . . , kb 0n i, such that, for each Example 5 Reconsider rMCS Mex3 , KB, and B from Example 4, as i ∈ {1 . . . , n}, kb 0i = mngi (appnext i (I, B), kb i ). well as an input stream I until 3 with I 1 = h{switch}i, I 2 = h∅i, and I 3 = h{switch}i. There is an equilibria stream B of Mex3 context is incoherent. To deal with such situations, we relax the con- given KB and I. Note that the input I 1 coincides with input I from cept of equilibria stream and introduce the notion of partial equilib- Example 4. As B is the only equilibrium of Mex3 given KB and I, we ria stream, which essentially allows the non-existences of equilibria have that B1 = B. at some time points. It turns out that partial equilibria streams always As we have appnextst (I, B) = {setPower(on)}, the update func- exist thus solving the problem of global inconsistency for rMCSs. tion provides the following configuration of knowledge bases for time In [12] the authors addressed the problem of global inconsistency instant 2 (with KB1 = KB): in the context of mMCSs. Just as we do here, they begin by establish- ing sufficient conditions for the existence of equilibria. Then, they KB2 = updMex3 (KB1 , I 1 , B1 ) = define the notions of diagnosis and explanation, the former corre- = hmngst (appnext (I, B), kb)i = h{pw}i. sponding to rules that need to be altered to restore consistency, and st the latter corresponding to combinations of rules that cause inconsis- Thus, switching the power state at time 1 leads to an updated tency. These two notions turn out to be dual of each other, and some- knowledge base indicating that the stove is on at time 2. The table how correspond to our notion of repair, the main difference being in Fig. 1 summarizes the equilibria stream and the configurations that, unlike in [12], we opt not to allow the (non-standard) strengthen- stream given KB and I. Note that, due to the choice of logic and ing of bridge-rule to restore consistency, and, of course, that fact that since all bridge rules use the next operator, equilibria necessarily our repairs need to take into account the dynamic nature of rMCSs. coincide with the corresponding knowledge base at each time step. We start by introducing two notions of global consistency differing only on whether we consider a particular input stream or all possible t KBt It Bt appnext (I t , Bt ) input streams. st 1 h∅i h{switch}i h∅i {setPower(on)} Definition 13 Let M be an rMCS, KB a configuration of knowledge 2 h{pw}i h∅i h{pw}i ∅ bases for M , and I an input stream for M . Then, M is consistent 3 h{pw}i h{switch}i h{pw}i {setPower(off )} with respect to KB and I if there exists an equilibria stream of M given KB and I. M is strongly consistent with respect to KB if, for every input stream I for M , M is consistent with respect to KB and Figure 1: Streams and applicable operations for Mex3 I. Obviously, for a fixed configuration of knowledge bases, strong consistency implies consistency w.r.t. any input stream, but not vice- versa. 3 Inconsistency Management Unfortunately, verifying strong consistency is in general highly The occurrence of inconsistencies within frameworks that aim at in- complex since it requires checking all possible equilibria streams. tegrating knowledge from different sources cannot be neglected, even Nevertheless, we can establish conditions that ensure that an rMCS more so in dynamic settings where knowledge changes over time. M is strongly consistent with respect to a given configuration of There are many reasons why rMCSs may fail to have an equilibria knowledge bases KB, hence guaranteeing the existence of an equi- stream. These include the absence of an acceptable belief set for one libria stream independently of the input. It is based on two notions – of its contexts given its current knowledge base at some point in time, totally coherent contexts and acyclic rMCSs – that together are suffi- some occurring conflict between the operations in the heads of bridge cient to ensure (strong) consistency. rules, or simply because the input stream is such that the configura- Total coherence imposes that each knowledge base of a context tion of the flow of information within the rMCS, namely its bridge always has at least one acceptable belief set. rules, prevent the existence of such an equilibria stream. In a real world situation, an rMCS without an equilibria stream is essentially Definition 14 A context Ci is totally coherent if acci (kb) 6= ∅, for useless. Not only can it not be used at the first time point equilibria every kb ∈ KB i . ceased to exist, but it also cannot recover, even if what caused the The second notion describes cycles between contexts which may problem was the particular input at that time point, which is bound be a cause of inconsistency. Acyclic rMCSs are those whose bridge to subsequently change into some other input that would no longer rules have no cycles. cause any trouble. This is so because an equilibria stream requires the existence of an equilibrium at every time point. Definition 15 Given an rMCS M = hhC1 , . . . , Cn i, IL, BRi, /M In this section, we address the problem of inexistent equilibria is the binary relation over contexts of M such that (Ci , Cj ) ∈ /M streams, also known as global inconsistency. We begin by defining a if there is a bridge rule r ∈ BR i and j:b ∈ bd(r) for some b. If notion of coherence associated with individual contexts which allows (Ci , Cj ) ∈ /M , also denoted by Ci /M Cj , we say that Ci depends us to first establish sufficient conditions for the existence of equilib- on Cj in M , dropping the reference to M whenever unambiguous. ria streams, and then abstract away from problems due to specific incoherent contexts and focus on those problems essentially caused Definition 16 An rMCS M is acyclic if the transitive closure of /M by the way the flow of information in rMCSs is organized through is irreflexive. its bridge rules. We introduce the notion of a repair, which modi- We can show that these two conditions together are indeed suffi- fies an rMCS by changing its bridge rules at some particular point cient to ensure strong consistency. in time in order to obtain some equilibria stream, which we dub re- paired equilibria stream. We establish sufficient conditions for the Proposition 1 Let M = hhC1 , . . . , Cn i, IL, BRi be an acyclic existence of repaired equilibria streams and briefly discuss different rMCS such that every Ci , 1 ≤ i ≤ n, is totally coherent, and KB a possible strategies to define such repairs. However, repaired equilib- configuration of knowledge bases for M . Then, M is strongly con- ria streams may not always exist either, e.g., because some particular sistent with respect to KB. A similar property holds for consistent mMCSs, which indicates This relation can be straightforwardly used to check whether a re- that the extension to rMCSs as such does not decrease the likelihood pair is minimal, and we can restrict ourselves to adopting minimal re- of existence of an equilibria stream. Nevertheless, these conditions pairs. However, there may be good reasons to adopt non-minimal re- are rather restrictive since there are many useful cyclic rMCSs which pairs, e.g., so that they can be determined as we go, or so that deleted only under some particular configurations of knowledge bases and bridge rules are not reinstated, etc. Even though investigating specific input streams may have no equilibria streams. types of repairs falls outside the scope of this paper, we nevertheless To deal with these, and recover an equilibria stream, one possi- present and briefly discuss some possibilities. bility is to repair the rMCSs by locally, and selectively, eliminating some of its bridge rules. Towards introducing the notion of repair, Definition 19 (Types of Repairs) Let R be a repair for some rMCS given an rMCS M = hhC1 , . . . , Cn i, IL, BRi,Swe denote by brM M given KB and I. We say that R is a: the set of all bridge rules of M , i.e., brM = 1≤i≤n BR i . More- Minimal Repair if there is no repair Ra for M given KB and I over, given a set R ⊆ brM , denote by M [R] the rMCS obtained such that Ra < R. from M by restricting the bridge rules to those not in R. Global Repair if Ri = Rj for every i, j ≤ τ . Definition 17 (Repair) Let M = hC, IL, BRi be an rMCS, KB a Minimal Global Repair if R is global and there is no global repair configuration of knowledge bases for M , and I an input stream for Ra for M given KB and I such that Ra < R. M until τ where τ ∈ N ∪ {∞}. Then, a repair for M given KB and Incremental Repair if Ri ⊆ Rj for every i ≤ j ≤ τ . I is a function R : [1..τ ] → 2brM such that there exists a function Minimally Incremental Repair if R is incremental and there is no B : [1..τ ] → BelM such that incremental repair Ra and j ≤ τ such that Ria ⊂ Ri for every i ≤ j. • Bt is an equilibrium of M [Rt ] given KBt and I t , where KBt is inductively defined as Minimal repairs perhaps correspond to the ideal situation in the – KB1 = KB sense that they never unnecessarily remove bridge rules. In some – KBt+1 = updM [Rt ] (KBt , I t , Bt ). circumstances, it may be the case that if a bridge rule is somehow involved in some inconsistency, it should not be used at any time We refer to B as a repaired equilibria stream of M given KB, I and point, leading to the notion of global repair. Given the set of all re- R. pairs, checking which are global is also obviously less complex than Note the generality of this notion, which considers to be a re- checking which are minimal. A further refinement – minimal global pair essentially any sequence of bridge rules (defined by the repair repairs – would be to only consider repairs that are minimal among function R) that, if removed from the rMCS at their corresponding the global ones, which would be much simpler to check than check- time point, will allow for an equilibrium at that time point. This may ing whether it is simply minimal. Note that a minimal global repair include repairs that unnecessarily eliminate some bridge rules, and is not necessarily a minimal repair. One of the problems with these even the empty repair i.e. the repair R∅ such that Rt∅ = ∅ for ev- types of repairs is that we can only globally check whether they are ery t, whenever M already has an equilibria stream given KB and I. of that type, i.e., we can only check once we know the entire in- This ensures that the set of repaired equilibria streams properly ex- put stream I. This was not the case with plain repairs, as defined in tends the set of equilibria streams, since equilibria streams coincide Def. 17, which could be checked as we go, i.e., we can determine with repaired equilibria streams given the empty repair. what bridge rules to include in the repair at a particular time point by having access to the input stream I up to that time point only. Proposition 2 Every equilibria stream of M given KB and I is a This is important so that rMCSs can be used to effectively react to repaired equilibria stream of M given KB, I and the empty repair their environment. The last two types of repairs defined above allow R∅ . for just that. Incremental repairs essentially impose that removed bridge rules cannot be reused in the future, i.e., that the set of re- It turns out that for rMCSs composed of totally coherent contexts, moved bridge rules monotonically grows with time, while minimally repaired equilibria streams always exist. incremental repairs further impose that only minimal sets of bridge Proposition 3 Let M = hhC1 , . . . , Cn i, IL, BRi be an rMCS such rules can be added at each time point. Other types of repairs could that each Ci , i ∈ {1, . . . , n}, is totally coherent, KB a configuration be defined, e.g., by defining some priority relation between bridge of knowledge bases for M , and I an input stream for M until τ . rules, some distance measure between subsets of bridge rules and Then, there exists R : [1..τ ] → 2brM and B : [1..τ ] → BelM such minimize it when considering the repair at consecutive time points, that B is a repaired equilibria stream given KB, I and R. among many other options, whose investigation we leave for future work. Repairs could also be extended to allow for the strengthen- Whenever repair operations are considered in the literature, e.g., ing of bridge rules, besides their elimination, generalizing ideas from in the context of databases [3], there is a special emphasis on seeking [12] and [8] where the extreme case of eliminating the entire body of repairs that are somehow minimal, the rational being that we want to bridge rules as part of a repair is considered. change things as little as possible to regain consistency. In the case Despite the existence of repaired equilibria streams for large of repairs of rMCS, it is easy to establish an order relation between classes of systems, two problems remain: first, computing a repair them, based on a comparison of the bridge rules to be deleted at each may be excessively complex, and second, there remain situations time point. where no repaired equilibria stream exists, namely when the rMCS Definition 18 Let Ra and Rb be two repairs for some rMCS M contains contexts that are not totally coherent. The second issue given a configuration of knowledge bases for M , KB and I, an input could be dealt with by ensuring that for each non-totally coherent stream for M until τ . We say that Ra ≤ Rb if Ria ⊆ Rib for every context there would be some bridge rule with a management opera- i ≤ τ , and that Ra < Rb if Ra ≤ Rb and Ria ⊂ Rib for some tion in its head that would always restore consistency of the context, i ≤ τ. and that such rule could always be activated through a repair (for example, by adding a negated reserved atom to its body, and another systems for dynamic environments in [9] and [24], which general- bridge rule with that atom in its head and an empty body, so that izes and substantially improves on the presentation of the underlying removing this latter rule through a repair would activate the manage- concepts of these earlier approaches. Building upon mMCSs, rMCSs ment function and restore consistency of the context). But this would inherit their functionality for integrating heterogeneous knowledge require special care in the way the system is specified, and its analysis sources, admitting also relevant operations on knowledge bases. In would require a very complex analysis of the entire system including addition, rMCSs can handle continuous streams of input data. Equi- the specific behavior of management functions. In practice, it would libria remain the fundamental underlying semantic notion, but the be quite hard – close to impossible in general – to ensure the exis- focus now lies on the dynamic evolution of the systems. tence of repaired equilibria streams, and we would still be faced with Since we cannot ignore the possibility that inconsistencies may oc- the first problem, that of the complexity of determining the repairs. cur, which result in the absence of equilibria at certain time points ul- A solution to this problem is to relax the notion of equilibria timately rendering the entire system useless, we addressed this prob- stream so that it does not require an equilibrium at every time point. lem first by showing sufficient conditions on the contexts and the This way, if no equilibrium exists at some time point, the equilibria bridge rules that ensure the existence of an equilibria stream. In the stream would be undefined at that point, but possibly defined again in cases where these conditions are not met, we presented two possible subsequent time points. This leads to the following notion of partial solutions, one following an approach based on repairs – essentially equilibria stream. the selective removal of bridge rules to regain an equilibria stream – and a second by relaxing the notion of equilibria stream to ensure Definition 20 (Partial Equilibria Stream) Let M = hC, IL, BRi that intermediate inconsistent states can be recovered from. be an rMCS, KB a configuration of knowledge bases for M , and There is much more to be done with respect to rMCSs, some of I an input stream for M until τ where τ ∈ N ∪ {∞}. Then, a which we are already working on. partial equilibria stream of M given KB and I is a partial function Nondeterminism is inherent to rMCSs due to, e.g., the flow of in- B : [1..τ ] 9 BelM such that formation between contexts established by bridge rules. This can be overcome by introducing preferences on equilibria using, e.g., prefer- • Bt is an equilibrium of M given KBt and I t , where KBt is in- ence functions as proposed in [14], or simply by preferring equilibria ductively defined as that represent minimal change between states, as proposed in [25]. – KB1 = KB One might also adopt language constructs for expressing preferences ( in ASP such as optimization statements [17] or weak constraints [11], updM (KBt , I t , Bt ), if Bt is not undefined. – KBt+1 = which essentially assign a quality measure to equilibria. One way of KBt , otherwise. avoiding nondeterminism is by applying an alternative, skeptical se- • or Bt is undefined. mantics – the well-founded semantics – along the lines of what was proposed in [28]. As expected, this is a proper generalisation of the notion of equi- An alternative to deal with inconsistent states is to follow a para- libria stream: consistent approach, as proposed for hybrid knowledge bases in [16, 26]. Also, just as with EVOLP [1] and explored in [23], we could Proposition 4 Every equilibria stream of M given KB and I is a allow the bridge rules to change with time, strengthening the evolv- partial equilibria stream of M given KB and I ing and adaptation capabilities of rMCSs. Finally, we need to compare our system with related work, in- And it turns out that partial equilibria streams always exist. cluding two of the most relevant approaches w.r.t. stream reason- ing, namely LARS (Logic-based framework for Analyzing Rea- Proposition 5 Let M be an rMCS, KB a configuration of knowledge soning over Streams) [6] and STARQL [32]. Additionally, in [15] bases for M , and I an input stream for M until τ . Then, there exists the authors defined Asynchronous MCSs (aMCSs) a framework for B : [1..τ ] 9 BelM such that B is a partial equilibria stream given loosely coupling knowledge representation formalisms. Contrarily KB and I. to rMCSs, the semantics is not defined in terms of equilibria but instead an asynchronous semantics is defined assuming that every One final word to note is that partial equilibria streams not only context delivers output whenever available. Establishing bridges be- allow us to deal with situations where equilibria do not exist at some tween both systems would also shed new light into the synchroniza- time instants, but they also open the ground to consider other kinds tion problems associated with combining dynamic knowledge bases. of situations where we do not wish to consider equilibria at some time point, for example because we were not able to compute them on time, or simply because we do not wish to process the input at ev- ery time point, e.g., whenever we just wish to sample the input with a lower frequency than it is generated. If we wish to restrict that par- ACKNOWLEDGEMENTS tial equilibria streams only relax equilibria streams when necessary, i.e., when equilibria do not exist at some time point, we can further impose the following condition on Def. 20: We would like to thank the reviewers for their comments, which helped improve this paper. R. Gonçalves, M. Knorr and J. Leite were Bt is undefined ⇒ there is no equilibrium of M given KBt and I t . partially supported by FCT under strategic project NOVA LINCS (PEst/UID/CEC/04516/2013). R. Gonçalves was partially supported by FCT grant SFRH/BPD/100906/2014 and M. Knorr by FCT grant 4 Conclusions SFRH/BPD/86970/2012. Moreover, G. Brewka, S. Ellmauthaler, and In this paper, we introduced reactive Multi-Context Systems (rMCSs), J. Pührer were partially supported by the German Research Founda- a combination and unification of the two adaptations of multi-context tion (DFG) under grants BR-1817/7-1 and FOR 1513. References [21] Fausto Giunchiglia, ‘Contextual reasoning’, Epistemologia, XVI, 345– 364, (1993). [1] José Júlio Alferes, Antonio Brogi, João Alexandre Leite, and Luı́s Mo- [22] Fausto Giunchiglia and Luciano Serafini, ‘Multilanguage hierarchical niz Pereira, ‘Evolving logic programs’, in Procs. of JELIA, eds., Sergio logics or: How we can do without modal logics’, Artif. Intell., 65(1), Flesca, Sergio Greco, Nicola Leone, and Giovambattista Ianni, volume 29–70, (1994). 2424 of LNCS, pp. 50–61. Springer, (2002). [23] Ricardo Gonçalves, Matthias Knorr, and João Leite, ‘Evolving bridge [2] D. Anicic, S. Rudolph, P. Fodor, and N. Stojanovic, ‘Stream reasoning rules in evolving multi-context systems’, in Procs. of CLIMA, eds., Nils and complex event processing in ETALIS’, Semantic Web, 3(4), 397– Bulling, Leendert W. N. van der Torre, Serena Villata, Wojtek Jamroga, 407, (2012). and Wamberto Weber Vasconcelos, volume 8624 of LNCS, pp. 52–69. [3] Marcelo Arenas, Leopoldo E. Bertossi, and Jan Chomicki, ‘Consis- Springer, (2014). tent query answers in inconsistent databases’, in Procs. of PODS, eds., [24] Ricardo Gonçalves, Matthias Knorr, and João Leite, ‘Evolving multi- Victor Vianu and Christos H. Papadimitriou, pp. 68–79. ACM Press, context systems’, in Procs. of ECAI, pp. 375–380, (2014). (1999). [25] Ricardo Gonçalves, Matthias Knorr, and João Leite, ‘Minimal change [4] The Description Logic Handbook: Theory, Implementation, and Ap- in evolving multi-context systems’, in Procs. of EPIA, eds., Fran- plications, eds., Franz Baader, Diego Calvanese, Deborah L. McGuin- cisco C. Pereira, Penousal Machado, Ernesto Costa, and Amı́lcar Car- ness, Daniele Nardi, and Peter F. Patel-Schneider, Cambridge Univer- doso, volume 9273 of LNCS, pp. 611–623. Springer, (2015). sity Press, 2nd edn., 2007. [26] Tobias Kaminski, Matthias Knorr, and João Leite, ‘Efficient paracon- [5] D. Barbieri, D. Braga, S. Ceri, E. Della Valle, and M. Grossniklaus, ‘C- sistent reasoning with ontologies and rules’, in Procs. of IJCAI, eds., SPARQL: a continuous query language for RDF data streams’, Int. J. Qiang Yang and Michael Wooldridge, pp. 3098–3105. AAAI Press, Semantic Computing, 4(1), 3–25, (2010). (2015). [6] Harald Beck, Minh Dao-Tran, Thomas Eiter, and Michael Fink, [27] Matthias Knorr, José Júlio Alferes, and Pascal Hitzler, ‘Local closed ‘LARS: A logic-based framework for analyzing reasoning over world reasoning with description logics under the well-founded seman- streams’, in Procs. of AAAI, eds., Blai Bonet and Sven Koenig, pp. tics’, Artif. Intell., 175(9-10), 1528–1554, (2011). 1431–1438. AAAI Press, (2015). [28] Matthias Knorr, Ricardo Gonçalves, and João Leite, ‘On efficient evolv- [7] Gerhard Brewka and Thomas Eiter, ‘Equilibria in heterogeneous non- ing multi-context systems’, in Procs. of PRICAI, eds., Duc Nghia Pham monotonic multi-context systems’, in Procs. of AAAI, pp. 385–390. and Seong-Bae Park, volume 8862 of LNCS, pp. 284–296. Springer, AAAI Press, (2007). (2014). [8] Gerhard Brewka, Thomas Eiter, Michael Fink, and Antonius Weinzierl, [29] Freddy Lécué and Jeff Z. Pan, ‘Predicting knowledge in an ontology ‘Managed multi-context systems’, in Procs. of IJCAI, ed., Toby Walsh, stream’, in Procs. of IJCAI, ed., Francesca Rossi, pp. 2662–2669. IJ- pp. 786–791. IJCAI/AAAI, (2011). CAI/AAAI, (2013). [9] Gerhard Brewka, Stefan Ellmauthaler, and Jörg Pührer, ‘Multi-context [30] John McCarthy, ‘Generality in artificial intelligence’, Commun. ACM, systems for reactive reasoning in dynamic environments’, in Procs. of 30(12), 1029–1035, (1987). ECAI, pp. 159–164, (2014). [31] Boris Motik and Riccardo Rosati, ‘Reconciling description logics and [10] Gerhard Brewka, Floris Roelofsen, and Luciano Serafini, ‘Contextual rules’, Journal of the ACM, 57(5), 93–154, (2010). default reasoning’, in Procs. of IJCAI, ed., Manuela M. Veloso, pp. [32] Özgür L. Özçep, Ralf Möller, Christian Neuenstadt, Dmitriy Zhelez- 268–273, (2007). nayakow, Evgeny Kharlamov, Ian Horrocks, Thomas Hubauer, and [11] Francesco Buccafurri, Nicola Leone, and Pasquale Rullo, ‘Strong and Mikhail Roshchin, ‘D5.1 Executive Summary: A semantics for tempo- weak constraints in disjunctive datalog’, in Procs. of LPNMR, eds., ral and stream-based query answering in an OBDA context’, Technical Jürgen Dix, Ulrich Furbach, and Anil Nerode, volume 1265 of LNCS, report, Optique FP7-ICT-2011-8-318338 Project, (2013). pp. 2–17. Springer, (1997). [33] Floris Roelofsen and Luciano Serafini, ‘Minimal and absent informa- [12] Thomas Eiter, Michael Fink, Peter Schüller, and Antonius Weinzierl, tion in contexts’, in Procs. of IJCAI, eds., Leslie Pack Kaelbling and ‘Finding explanations of inconsistency in multi-context systems’, Artif. Alessandro Saffiotti, pp. 558–563. Professional Book Center, (2005). Intell., 216, 233–274, (2014). [13] Thomas Eiter, Giovambattista Ianni, Thomas Lukasiewicz, Roman Schindlauer, and Hans Tompits, ‘Combining answer set programming with description logics for the semantic web’, Artif. Intell., 172(12-13), 1495–1539, (2008). [14] Stefan Ellmauthaler, ‘Generalizing multi-context systems for reactive stream reasoning applications’, in Procs. of ICCSW, eds., Andrew V. Jones and Nicholas Ng, volume 35 of OASICS, pp. 19–26. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany, (2013). [15] Stefan Ellmauthaler and Jörg Pührer, ‘Asynchronous multi-context sys- tems’, in Advances in Knowledge Representation, Logic Programming, and Abstract Argumentation - Essays Dedicated to Gerhard Brewka on the Occasion of His 60th Birthday, eds., Thomas Eiter, Hannes Strass, Miroslaw Truszczynski, and Stefan Woltran, volume 9060 of LNCS, pp. 141–156. Springer, (2015). [16] Michael Fink, ‘Paraconsistent hybrid theories’, in Procs. of KR, eds., Gerhard Brewka, Thomas Eiter, and Sheila A. McIlraith. AAAI Press, (2012). [17] M. Gebser, R. Kaminski, B. Kaufmann, M. Ostrowski, T. Schaub, and S. Thiele, A users guide to gringo, clasp, clingo, and iclingo, Potassco Team, 2010. [18] Martin Gebser, Torsten Grote, Roland Kaminski, Philipp Obermeier, Orkunt Sabuncu, and Torsten Schaub, ‘Stream reasoning with answer set programming: Preliminary report’, in Procs. of KR, eds., Gerhard Brewka, Thomas Eiter, and Sheila A. McIlraith, pp. 613–617. AAAI Press, (2012). [19] Martin Gebser, Torsten Grote, Roland Kaminski, and Torsten Schaub, ‘Reactive answer set programming’, in Procs. of LPNMR, eds., James P. Delgrande and Wolfgang Faber, volume 6645 of LNCS, pp. 54–66. Springer, (2011). [20] Michael Gelfond and Vladimir Lifschitz, ‘Classical negation in logic programs and disjunctive databases’, New Generation Comput., 9(3/4), 365–386, (1991).