On Expansion and Contraction of DLLite Knowledge Bases. Knowledge bases (KBs) are not static entities: new information constantly appears and some of the previous knowledge becomes obsolete. In order to reflect this evolution of knowledge, KBs should be expanded with the new knowledge and contracted from the obsolete one. This problem is wellstudied for propositional but much less for firstorder KBs. In this work we investigate knowledge expansion and contraction for KBs expressed in DLLite, a family of description logics (DLs) that underlie the tractable fragment OWL 2 QL of the Web Ontology Language OWL 2. We start with a novel knowledge evolution framework and natural postulates that evolution should respect, and compare our postulates to the wellestablished AGM postulates. We then review wellknown model and formulabased approaches for expansion and contraction for propositional theories and show how they can be adapted to the case of DLLite. In particular, we show intrinsic limitations of modelbased approaches: besides the fact that some of them do not respect the postulates we have established, they ignore the structural properties of KBs. This leads to undesired properties of evolution results: evolution of DLLite KBs cannot be captured in DLLite. Moreover, we show that wellknown formulabased approaches are also not appropriate for DLLite expansion and contraction: they either have a high complexity of computation, or they produce logical theories that cannot be expressed in DLLite. Thus, we propose a novel formulabased approach that respects our principles and for which evolution is expressible in DLLite. For this approach we also propose  :247,time deterministic algorithms to compute evolution of DLLite KBs when evolution affects only factual data.

The Bayesian Ontology Language mathcal BELBEL We introduce the new probabilistic description logic (DL) mathcal BEL BEL, which extends the lightweight DL mathcal ELEL with the possibility of expressing uncertainty about the validity of some knowledge. Contrary to other probabilistic DLs, mathcal BELBEL is designed to represent classical knowledge that depends on an uncertain context; that is, some of the knowledge may hold or not depending on the current situation. The probability distribution of these contexts is expressed by a Bayesian network (BN). We study different reasoning problems in mathcal BELBEL, providing tight complexity bounds for all of them. One particularly interesting property of our framework is that reasoning can be decoupled between the logical (i.e., mathcal ELEL), and the probabilistic (i.e., the BN) components. We later generalize all the notions presented to introduce Bayesian extensions of arbitrary ontology languages. Using the decoupling property, we are able to provide tight complexity bounds for reasoning in the Bayesian extensions of many other DLs. We provide a detailed analysis of our formalism w.r.t. the assumptions made and compare it with the existing approaches.