This paper presents a characterisation of and definitions for the phenomenon of masking in the context of justifications for entailments in ontologies. In essence masking is present within a justification, over a set of justifications, or over a complete ontology when the number of justifications for an entailment does not reflect the number of reasons for that entailment. Four types of masking are defined in this paper: Internal Masking, Cross Masking, External Masking and Shared Core Masking. The results of an empirical study are presented which shows that the phenomenon of masking is prevalent throughout ontologies with non-trivial entailments in the NCBO BioPortal corpus. Out of 72 ontologies, 53 exhibited some form of masking, with 9 ontologies exhibiting internal masking, 23 ontologies exhibiting external masking, and 53 ontologies exhibiting shared core masking.

A bipolar framework is introduced for combining agents' beliefs so as to enable them to reach a common shared position or viewpoint. Our approach exploits the truth-gaps inherent to propositions involving vague concepts, by allowing agents to soften directly conflicting opinions. To this end we adopt a bipolar truth-model for propositional logic characterised by lower and upper valuations on the sentences of the language. According to this model sentences may be absolutely true, absolutely false or borderline (i.e. neither absolutely true nor absolutely false). The added flexibility of a possible truth-gap between absolutely true and absolutely false allows agents with inconsistent viewpoints, in which a proposition p is absolutely true according to one view and absolutely false according to the other, to reach a compromise position in which p is borderline. Within this framework four combination operators are proposed for combining different viewpoints as represented by different valuation pairs. Intuitively, these correspond to compromise positions with different levels of semantic precision (or vagueness). Kleene belief pairs are then introduced as lower and upper measures quantifying epistemic uncertainty about the sentences of the language when valuation pairs provide the underlying truth model. The combination operators on valuation pairs are then extended to belief pairs using a general schema incorporating a probabilistic model of the interaction between agents. The properties of the four operators are then investigated within this extended framework.

We study (i) uniform interpolation for TBoxes that are formulated in the description logic EL and (ii) approximations of TBoxes formulated in more expressive languages. In both cases, we give model-theoretic characterizations based on simulations and cartesian products, and we develop algorithms that decide whether interpolants and approximations exist. We present a uniform approach to both problems, based on a novel amorphous automaton model called EL automata (EA). Using EAs, we also establish a simpler proof of the known result that conservative extensions of EL-TBoxes can be decided in ExpTime.

Belief revision has been extensively studied in the framework of propositional logic, but just recently revision within fragments of propositional logic has gained attention. Hereby it is not only the belief set and the revision formula which are given within a certain language fragment, but also the result of the revision has to be located in the same fragment. So far, research in this direction has been mainly devoted to the Horn fragment of classical logic. In this work, we present a general approach to define new revision operators derived from known operators (as for instance, Satoh's and Dalal's revision operators), such that the result of the revision remains in the fragment under consideration. Our approach is not limited to the Horn case but applicable to any fragment of propositional logic where the models of the formulas are closed under a Boolean function. Thus we are able to uniformly treat cases as dual-Horn, Krom and affine formulas, as well.

In order to meet usability requirements, most logic-based applications provide explanation facilities for reasoning services. This holds also for DLs, where research has focused on the explanation of both TBox reasoning and, more recently, query answering. Besides explaining the presence of a tuple in a query answer, it is important to explain also why a given tuple is missing. We address the latter problem for (conjunctive) query answering over DL-Lite ontologies, by adopting abductive reasoning, that is, we look for additions to the ABox that force a given tuple to be in the result. As reasoning taskswe consider existence and recognition of an explanation, and relevance and necessity of a certain assertion for an explanation. We characterize the computational complexity of these problems for subset minimal and cardinality minimal explanations.

Following the recent trend of adapting the AGM (Alchourron and Makinson 1985) framework to propositional Horn logic, Delgrande and Peppas (Delgrande and Peppas 2011) give a model theoretic account for revision in the Horn logic set- ting. The current paper complements their work by studying the model theoretic approach for contraction. A model based Horn contraction is constructed and shown to give a model theoretic account to the transitively relational partial meet Horn contraction studied in (Zhuang and Pagnucco 2011). Significantly however, in contrast to (Delgrande and Pep- pas 2011), our model-based characterisation of Horn contrac- tion does not require the property of Horn compliance and totality over preorders. The model based contraction, upon proper restriction, also gives a model theoretic account for the epistemic entrenchment based Horn contraction studied in (Zhuang and Pagnucco 2010a).

An agent will generally have incomplete and possibly inaccurate knowledge about its environment. In addition, such an agent may receive erroneous information, perhaps in being misinformed about the truth of some formula. In this paper we present a general approach to reasoning about action and belief change in such a setting. An agent may carry out actions, but in some cases may inadvertently execute the wrong one (for example, pushing an unintended button). As well, an agent may sense whether a condition holds, and may revise its beliefs after being told that a formula is true. Our approach is based on an epistemic extension to basic action theories expressed in the situation calculus, augmented by a plausibility relation over situations. This plausibility relation can be thought of as characterising the agent's overall belief state; as such it keeps track of not just the formulas that the agent believes to hold, but also the plausibility of formulas that it does not believe to hold. The agent's belief state is updated by suitably modifying the plausibility relation following the execution of an action. We show that our account generalises previous approaches, and fully handles belief revision, sensing, and erroneous actions.

Answering conjunctive queries (CQs) over a set of facts extended with existential rules is a key problem in knowledge representation and databases. This problem can be solved using the chase (aka materialisation) algorithm; however, CQ answering is undecidable for general existential rules, so the chase is not guaranteed to terminate. Several acyclicity conditions provide sufficient conditions for chase termination. In this paper, we present two novel such conditions—model-faithful acyclicity (MFA) and model-summarising acyclicity (MSA)—that generalise many of the acyclicity conditions known so far in the literature. Materialisation provides the basis for several widely-used OWL 2 DL reasoners. In order to avoid termination problems, many of these systems handle only the OWL 2 RL profile of OWL 2 DL; furthermore, some systems go beyond OWL 2 RL, but they provide no termination guarantees. In this paper we investigate whether various acyclicity conditions can provide a principled and practical solution to these problems. On the theoretical side, we show that query answering for acyclic ontologies is of lower complexity than for general ontologies. On the practical side, we show that many of the commonly used OWL 2 DL ontologies are MSA, and that the facts obtained via materialisation are not too large. Thus, our results suggest that principled extensions to materialisationbased OWL 2 DL reasoners may be practically feasible.

McCarthy's strengths as both theoretician and engineer, John McCarthy, famous for his role in the development and explore how these drosophilae shaped his of time-sharing, for inventing the computer research. Since is talk analyzes McCarthy's myriad contributions 2010, she has served as principal investigator of the to artificial intelligence and knowledge representation Evaluation and Knowledge Infrastructure Team for through the set of drosophilae that he proposed, DARPA's Machine Reading Program.

Existing methods for dealing with knowledge updates differ greatly depending on the underlying knowledge representation formalism. When Classical Logic is used, update operators are typically based on manipulating the knowledge base on the model-theoretic level. On the opposite side of the spectrum stand the semantics for updating Answer-Set Programs where most approaches need to rely on rule syntax. Yet, a unifying perspective that could embrace all these approaches is of great importance as it enables a deeper understanding of all involved methods and principles and creates room for their cross-fertilisation, ripening and further development. This paper bridges these seemingly irreconcilable approaches to updates. It introduces a novel monotonic characterisation of rules, dubbed \emph{\RE-models}, and shows it to be a more suitable semantic foundation for rule updates than \SE-models. A generic framework for defining semantic rule update operators is then proposed. It is based on the idea of viewing a program as the \emph{set of sets of \RE-models} of its rules; updates are performed by introducing additional interpretations to the sets of \RE-models of rules in the original program. It is shown that particular instances of the framework are closely related to both belief update principles and traditional approaches to rule updates and enjoy a range of plausible syntactic as well as semantic properties.