Preference logics and AI preference representation languages are both concerned with reasoning about preferences on combinatorial domains, yet so far these two streams of research have had little interaction. This paper contributes to the bridging of these areas. We start by constructing a "prototypical" preference logic, which combines features of existing preference logics, and then we show that many well-known preference languages, such as CP-nets and its extensions, are natural fragments of it. After establishing useful characterizations of dominance and consistency in our logic, we study the complexity of satisfiability in the general case as well as for meaningful fragments, and we study the expressive power as well as the relative succinctness of some of these fragments.

Description Logics (DLs) are knowledge representation formalisms that provide, for example, the logical underpinning of the W3C OWL standards. Conjunctive queries (CQs), the standard query language in databases, have recently gained significant attention for querying DL knowledge bases. Several different techniques are available for a wide range of DLs. Nevertheless, for OWL 1 DL and OWL 2 DL, decidability of CQ entailment is an open problem. So far, the combination of nominals, inverse roles, and number restrictions caused unsolvable problems. We tackle this problem and present a decidability result for entailment of unions of CQs in a DL with all three problematic constructors. For queries with only simple roles, our result also shows decidability in the logic that underpins OWL 1 DL and we believe that the presented results will pave the way for further progress towards CQ entailment decision procedures for OWL.

We investigate the computational complexity of axiom pinpointing, which is the task of finding minimal subsets of a Description Logic knowledge base that have a given consequence. We consider the problems of enumerating such subsets with and without order, and show hardness results that already hold for the propositional Horn fragment, or for the Description Logic EL. We show complexity results for several other related decision and enumeration problems for these fragments that extend to more expressive logics. In particular we show that hardness of these problems depends not only on expressivity of the fragment but also on the shape of the axioms used.

This is a case-study in knowledge representation. We analyze the 'one hundred prisoners and a lightbulb' puzzle. In this puzzle it is relevant what the agents (prisoners) know, how their knowledge changes due to observations, and how they affect the state of the world by changing facts, i.e., by their actions. These actions depend on the history of previous actions and observations. Part of its interest is that all actions are local, i.e. not publicly observable, and part of the problem is therefore how to disseminate local results to other agents, and make them global. The various solutions to the puzzle are presented as protocols (iterated functions from agent's local states, and histories of actions, to actions). The computational aspect is about average runtime termination under conditions of random ('fair') scheduling. The paper consists of three parts. First, we present different versions of the puzzle, and their solution. This includes a probabilistic version, and a version assuming synchronicity (the interval between prisoners' interrogations is known). The latter is very informative for the prisoners, and allows different protocols (with faster expected termination). Then, we model the puzzle in an epistemic logic incorporating dynamic operators for the effects of information changing events. Such events include both informative actions, where agents become more informed about the non-changing state of the world, and factual changes, wherein the world and the facts describing it change themselves as well. Finally, we give the expected termination results of several protocols when assuming random scheduling. This paper integrates the literature and presents novel contributions. Novel are: Firstly, Protocol 2 and Protocol 4. Secondly, the modelling in dynamic epistemic logic in its entirety - we do not know of a case study that combines factual and informational dynamics in a setting of non-public events, or of a similar proposal to handle asynchronous behaviour in a dynamic epistemic logic. Thirdly, our computational results on Protocol 2 and results from the manuscript from author Wu.

By logical proportion, we mean a statement that expresses a semantical equivalence between two pairs of propositions. In these pairs, each element is compared to the other in terms of similarities and/or dissimilarities. An example of such a proportion is the well known analogical proportion: a is to b as c is to d . Analogical proportions have been recently characterized in logical terms, but there are many other proportions that are worth of interest. Some of them can be related to the analogical pattern, others are related to semantical equivalence between conditional objects and express statements such as a ressembles to b and differs from b in the same way as c with respect to d. We show that there are 5 direct proportions, including the analogical one and 4 others having a conditional object flavor, where the change (if any) from a to b goes in the same direction as the change from c to d (if any), together with 5 reverse proportions obtained by switching c and d. Moreover, there exists only one auto-reverse proportion called paralogy and stating that what a and b have in common, c and d have it as well. It is then established that there is none other proportion than these ones (with the exception of 4 degenerated ones) that satisfies a natural “full identity” requirement. The paper proposes a structured and unified view of these logical proportions and discusses their characteristic properties. It extends previous works where only proportions related to analogy were considered. It also explores the use of these logical proportions in transduction-like inference, where new items are classified on the basis of already classified items without trying to induce a generic model, considering similarities and differences between items only. Taking advantage of different proportions, a transduction procedure is proposed.

Databases and related information systems can benefit from the use of ontologies to enrich the data with general background knowledge. The DL-Lite family of ontology languages was specifically tailored towards such ontology-based data access, enabling an implementation in a relational database management system (RDBMS) based on a query rewriting approach. In this paper, we propose an alternative approach to implementing ontology-based data access in DL-Lite. The distinguishing feature of our approach is to allow rewriting of both the query and the data. We show that, in contrast to the existing approaches, no exponential blowup is produced by the rewritings. Based on experiments with a number of real-world ontologies, we demonstrate that query execution in the proposed approach is often more efficient than in existing approaches, especially for large ontologies. We also show how to seamlessly integrate the data rewriting step of our approach into an RDBMS using views (which solves the update problem) and make an interesting observation regarding the succinctness of queries in the original query rewriting approach.

Ontologies can be used to provide an enriched vocabulary for the formulation of queries over instance data. We identify query emptiness and predicate emptiness as two central reasoning services in this context. Query emptiness asks whether a given query has an empty answer over all data sets formulated in a given signature. Predicate emptiness is defined analogously, but quantifies universally over all queries that contain a given predicate. In this paper, we determine the computational complexity of query emptiness and predicate emptiness in the EL, DL-Lite, and ALC-families of description logics, investigate the connection to ontology modules, and perform a practical case study to evaluate the new reasoning services.

In this paper, we consider propositional Topological logics are a family of languages for representing topological logics with connectedness, i.e. topological and reasoning about topological data. The non-logical logics in which the only logical connectives are the usual primitives of these languages stand for various topological Boolean operators, but where there is a non-logical primitive relations and operations, and their valid formulas encode our expressing the property of topological connectedness knowledge about those relations and operations. Consider, (or a variant thereof). We show that such topological logics for example, the six relations illustrated in Figure 1. By em-are typically sensitive both to the spaces they are interpreted over and--more particularly--to the subsets of those spaces over which their variables are allowed to range.

In this paper, I defend a multiplicative approach that distinguishes statues from amounts of matter, political entities from physical ones, qua entities (e.g. John qua Alitalia passenger) from players (e.g. John), etc. I develop a theory of levels which is based on the primitive notions of level, parthood, and grounding (a kind of existential dependence) and that is used to characterize more specific relations like constitution, inherence, and abstraction. I neither aim to propose a `definitive' theory of levels nor to commit to their ontological or conceptual nature. Hence, the adjective `ontological' used in the title does not qualify the nature of the entities that belong to levels but the way the notion of level is characterized, i.e. in terms of general and philosophically well-founded notions. By keeping away from a purely realist attitude, I can then discuss the adequacy of some alternative first-order theories to account for three puzzling scenarios.

Existing action calculi provide rich, declarative formalisms for reasoning about actions. BDI-based programming languages like AgentSpeak, on the other hand, are procedural and geared towards practical applications of cognitive agents. In this paper, we close the gap between these two lines of research by integrating action calculi and AgentSpeak programs. Specifically, we develop a new and purely declarative semantics for AgentSpeak, which paves the way for combining this language with any suitable action calculus in a strictly modular fashion. As the main technical result, we prove that the new declarative semantics is correct wrt. the standard operational semantics for AgentSpeak. This provides the basis for a modular integration of a BDI-based agent programming language with sophisticated methods for reasoning about actions.