Defeasible inheritance networks are a non-monotonic framework that deals with hierarchical knowledge. On the other hand, rational closure is acknowledged as a landmark of the preferential approach to non-monotonic reasoning. We will combine these two approaches and define a new non-monotonic closure operation for propositional knowledge bases that combines the advantages of both. Then we redefine such a procedure for Description Logics (DLs), a family of logics well-suited to model structured information. In both cases we will provide a simple reasoning method that is built on top of the classical entailment relation and, thus, is amenable of an implementation based on existing reasoners. Eventually, we evaluate our approach on well-known landmark test examples.

It is a classic result in database theory that conjunctive query (CQ) answering, which is NP-complete in general, is feasible in polynomial time when restricted to acyclic queries. Subsequent results identified more general structural properties of CQs (like bounded treewidth) which ensure tractable query evaluation. In this paper, we lift these tractability results to knowledge bases formulated in the lightweight description logics DL-Lite and ELH. The proof exploits known properties of query matches in these logics and involves a query-dependent modification of the data. To obtain a more practical approach, we propose a concrete polynomial-time algorithm for answering acyclic CQs based on rewriting queries into datalog programs. A preliminary evaluation suggests the interest of our approach for handling large acyclic CQs.

We propose a variant of Alternating-time Temporal Logic (ATL) grounded in the agents' operational know-how, as defined by their libraries of abstract plans. In our logic, it is possible to refer to "rational" strategies for agents developed under the Belief-Desire-Intention agent paradigm. This allows us to express and verify properties of BDI systems using ATL-type logical frameworks.

Nonmonotonic Description Logic (DL) programs support rule-based reasoning on top of Description Logic ontologies, using a well-defined query interface. However, the interaction of the rules and the ontology may cause inconsistency such that no answer set (i.e. model) exists. We thus consider repairing DL-programs, i.e., changing formulas to obtain consistency. Viewing the data part of the ontology as the source of inconsistency, we define program repairs and repair answer sets based on changes to it. We analyze the complexity of the notion, and we extend an algorithm for evaluating DL-programs to compute repair answer sets, under optional selection of preferred repairs. The extension involves a generalized ontology repair problem, in which the entailment and non-entailment of sets of queries with updates to the ontology must be achieved. While this is intractable in general, we identify for the Description Logic DL-Lite_A some tractable classes of preferred repairs that are useful in practice.

Description Logic Knowledge and Action Bases (KABs) have been recently introduced as a mechanism that provides a semantically rich representation of the information on the domain of interest in terms of a DL KB and a set of actions to change such information over time, possibly introducing new objects. In this setting, decidability of verification of sophisticated temporal properties over KABs, expressed in a variant of first-order mu-calculus, has been shown. However, the established framework treats inconsistency in a simplistic way, by rejecting inconsistent states produced through action execution. We address this problem by showing how inconsistency handling based on the notion of repairs can be integrated into KABs, resorting to inconsistency-tolerant semantics. In this setting, we establish decidability and complexity of verification.

Conjunctive regular path queries are an expressive extension of the well-known class of conjunctive queries and have been extensively studied in the database community. Somewhat surprisingly, there has been little work aimed at using such queries in the context of description logic (DL) knowledge bases, and all existing results target expressive DLs, even though lightweight DLs are considered better-suited for data-intensive applications. This paper aims to bridge this gap by providing algorithms and tight complexity bounds for answering two-way conjunctive regular path queries over DL knowledge bases formulated in lightweight DLs of the DL-Lite and EL families.

One of the most advanced approaches to querying data in the presence of ontologies is to make use of relational database systems, rewriting the original query and the ontology into a new query that is formulated in SQL or, equivalently, in first-order logic (FO). For ontologies written in many standard description logics (DLs), however, such FO-rewritings are not guaranteed to exist. We study FO-rewritings and their existence for a basic class of queries and for ontologies formulated in Horn DLs such as Horn-SHI and EL. Our results include characterizations of the existence of FO-rewritings, tight complexity bounds for deciding whether an FO-rewriting exists (ExpTime and PSpace), and tight bounds on the (worst-case) size of FO-rewritings, when presented as a union of conjunctive queries.

In spatio-temporal reasoning, granularity is one of the factors to be considered when aiming at an effective and efficient representation of space and time. There is a large body of work which addresses the issue of granularity by representing space and time on a qualitative level. Other approaches use a predefined scale which implicitly determines granularity (e.g., seconds, minutes, hours, days, month, etc.). However, there are situations where the right level of granularity is unknown in the beginning, and is only determined in the problem solving process itself. This is the case in machine learning, where the learner has to find a representation for a problem and with that the right granularity for representing space and time. This paper introduces an algorithm which determines the most appropriate level of granularity during training. It uses several description logic learners as the learners, and the positive and negative examples presented to them as the determinators for refining coarse temporal representations to the most appropriate level of granularity.

Knowledge base exchange is an important problem in the area of data exchange and knowledge representation, where one is interested in exchanging information between a source and a target knowledge base connected through a mapping. In this paper, we study this fundamental problem for knowledge bases and mappings expressed in OWL 2 QL, the profile of OWL 2 based on the description logic DL-Lite_R. More specifically, we consider the problem of computing universal solutions, identified as one of the most desirable translations to be materialized, and the problem of computing UCQ-representations, which optimally capture in a target TBox the information that can be extracted from a source TBox and a mapping by means of unions of conjunctive queries. For the former we provide a novel automata-theoretic technique, and complexity results that range from NP to EXPTIME, while for the latter we show NLOGSPACE-completeness.

This article compares Defeasible Description Logics (DDL) and Topological Approach to reason on Ontologies with exceptions. DDL is integration between Description Logics and Defeasible Logics to deal with monotonic and non-monotonic parts of the knowledge bases respectively. Topological approach tries to reason on inconsistent knowledge bases using the conventional topological operators e.g., interior, exterior, border and closure. We develop neo-Topology based on topological operators and we make major development and improvements of current Topological approach by properly introducing the ``Thickness Border'' with strong inference rules. We proof the validity of the inference rules using set operations. We demonstrate both approaches with appropriate example. We show the advantages and disadvantages of both approaches.