The EL family of description logics (DLs) has been designed to provide a restricted syntax for commonly used DL constructors with the goal to guarantee polynomial complexity of reasoning. Yet, polynomial complexity does not always mean that the underlying reasoning procedure is efficient inpractice. In this paper we consider a simple DL ELO from the EL family that admits nominals, and argue that existing polynomial reasoning procedures for ELO can be impractical for many realistic ontologies. To solve the problem, we describe an optimization strategy in which the inference rules required for reasoning with nominals are avoided as much as possible. The optimized procedure is evaluated within the reasoner ELK and demonstrated to perform well in practice.

We consider the setting of ontological database access, where an A-box is given in form of a relational database D and where a Boolean conjunctive query q has to be evaluated against D modulo a T-box Σ formulated in DL-Lite or Linear Datalog+/-. It is well-known that (Σ, q) can be rewritten into an equivalent nonrecursive Datalog program P that can be directly evaluated over D. However, for Linear Datalog+/- or for DL-Lite versions that allow for role inclusion, the rewriting methods described so far result in a nonrecursive Datalog program P of size exponential in the joint size of Σ and q . This gives rise to the interesting question whether such a rewriting necessarily needs to be of exponential size. In this paper we show that it is actually possible to translate (Σ, q ) into a polynomially sized equivalent nonrecursive Datalog program P.

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.

Fuzzy description logics (DLs) have been investigated for over two decades, due to their capacity to formalize and reason with imprecise concepts. Very recently, it has been shown that for several fuzzy DLs, reasoning becomes undecidable. Although the proofs of these results differ in the details of each specific logic considered, they are all based on the same basic idea. In this paper, we formalize this idea and provide sufficient conditions for proving undecidability of a fuzzy DL. We demonstrate the effectiveness of our approach by strengthening all previously-known undecidability results and providing new ones. In particular, we show that undecidability may arise even if only crisp axioms are considered.

While query answering in the presence of description logic (DL) ontologies is a well-studied problem, questions of static analysis such as query containment and query optimization have received less attention. In this paper, we study a rather general version of query containment that, unlike the classical version, cannot be reduced to query answering. First, we allow a restriction to be placed on the vocabulary used in the instance data, which can result in shorter equivalent queries; and second, we allow each query its own ontology rather than assuming a single ontology for both queries, which is crucial in applications to versioning and modularity. We also study global minimization of queries in the presence of DL ontologies, which is more subtle than for classical databases as minimal queries need not be isomorphic.

This paper presents an axiomatic framework for influence diagram computation, which allows reasoning with partially ordered values of utility. We show how an algorithm based on sequential variable elimination can be used to compute the set of maximal values of expected utility (up to an equivalence relation). Formalisms subsumed by the framework include decision making under uncertainty based on multi-objective utility, or on interval-valued utilities, as well as a more qualitative decision theory based on order-of-magnitude probabilities and utilities.

We deal with the problem of how to extend a preference relation over a set X of "objects" to the set of all subsets of X. This problem has been carried out in the tradition of the literature on extending an order on a set to its power set with the objective to analyze the axiomatic structure of families of rankings over subsets. In particular, most of these approaches make use of axioms aimed to prevent any kind of interaction among the objects in X . In this paper, we apply coalitional games to study the problem of extending preferences over a finite set X to its power set 2 X . A coalitional game can be seen as a numerical representation of a preference extension on 2 X . . We focus on a particular class of extensions on 2 X . such that the ranking induced by the Shapley value of each coalitional game representing an extension in this class, coincides with the original preference on X . Some properties of Shapley extensions are discussed, with the objective to justify and contextualize the application of Shapley extensions to the problem of ranking sets of possibly interacting objects.We deal with the problem of how to extend a preference relation over a set X of "objects" to the set of all subsets of X . This problem has been carried out in the tradition of the literature on extending an order on a set to its power set with the objective to analyze the axiomatic structure of families of rankings over subsets. In particular, most of these approaches make use of axioms aimed to prevent any kind of interaction among the objects in X . In this paper, we apply coalitional games to study the problem of extending preferences over a finite set X to its power set 2 X . . A coalitional game can be seen as a numerical representation of a preference extension on 2 X . . We focus on a particular class of extensions on 2 X. such that the ranking induced by the Shapley value of each coalitional game representing an extension in this class, coincides with the original preference on X . Some properties of Shapley extensions are discussed, with the objective to justify and contextualize the application of Shapley extensions to the problem of ranking sets of possibly interacting objects.

We introduce the framework of qualitative optimization problems (or, simply, optimization problems) to represent preference theories. The formalism uses separate modules to describe the space of outcomes to be compared (the generator) and the preferences on outcomes (the selector). We consider two types of optimization problems. They differ in the way the generator, which we model by a propositional theory, is interpreted: by the standard propositional logic semantics, and by the equilibrium-model (answer-set) semantics. Under the latter interpretation of generators, optimization problems directly generalize answer-set optimization programs proposed previously. We study strong equivalence of optimization problems, which guarantees their interchangeability within any larger context. We characterize several versions of strong equivalence obtained by restricting the class of optimization problems that can be used as extensions and establish the complexity of associated reasoning tasks. Understanding strong equivalence is essential for modular representation of optimization problems and rewriting techniques to simplify them without changing their inherent properties.

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).

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.