Description Logic


Efficient Concept Induction for Description Logics

arXiv.org Artificial Intelligence

Concept Induction refers to the problem of creating complex Description Logic class descriptions (i.e., TBox axioms) from instance examples (i.e., ABox data). In this paper we look particularly at the case where both a set of positive and a set of negative instances are given, and complex class expressions are sought under which the positive but not the negative examples fall. Concept induction has found applications in ontology engineering, but existing algorithms have fundamental performance issues in some scenarios, mainly because a high number of invokations of an external Description Logic reasoner is usually required. In this paper we present a new algorithm for this problem which drastically reduces the number of reasoner invokations needed. While this comes at the expense of a more limited traversal of the search space, we show that our approach improves execution times by up to several orders of magnitude, while output correctness, measured in the amount of correct coverage of the input instances, remains reasonably high in many cases. Our approach thus should provide a strong alternative to existing systems, in particular in settings where other systems are prohibitively slow.


A Description Logic Framework for Commonsense Conceptual Combination Integrating Typicality, Probabilities and Cognitive Heuristics

arXiv.org Artificial Intelligence

We propose a nonmonotonic Description Logic of typicality able to account for the phenomenon of concept combination of prototypical concepts. The proposed logic relies on the logic of typicality ALC TR, whose semantics is based on the notion of rational closure, as well as on the distributed semantics of probabilistic Description Logics, and is equipped with a cognitive heuristic used by humans for concept composition. We first extend the logic of typicality ALC TR by typicality inclusions whose intuitive meaning is that "there is probability p about the fact that typical Cs are Ds". As in the distributed semantics, we define different scenarios containing only some typicality inclusions, each one having a suitable probability. We then focus on those scenarios whose probabilities belong to a given and fixed range, and we exploit such scenarios in order to ascribe typical properties to a concept C obtained as the combination of two prototypical concepts. We also show that reasoning in the proposed Description Logic is EXPTIME-complete as for the underlying ALC.


On Limited Conjunctions in Polynomial Feature Logics, with Applications in OBDA

AAAI Conferences

Standard reasoning problems are complete for EXPTIME in common feature-based description logics-ones in which all roles are restricted to being functional. We show how to control conjunctions on left-hand-sides of subsumptions in such a way so as to ensure polynomial time complexity. In particular, we present a PTIME algorithm for reasoning about knowledge base consistency. We then show how the resulting description logic allows features to be partial, not just total functions. Algorithms for polynomial-time query answering are presented. The above, in combination with referring expressions, provide a richer capability for ontology-based data access to relational data sources.


A Comprehensive Framework for Controlled Query Evaluation, Consistent Query Answering and KB Updates in Description Logics

AAAI Conferences

In this extended abstract we discuss the relationship between confidentiality-preserving frameworks and inconsistency-tolerant repair and update semantics in Description Logics (DL). In particular, we consider the wellknown problems of Consistent Query Answering, Controlled Query Evaluation, and Knowledge Base Update in DL and introduce a unifying framework that can be naturally instantiated to capture significant settings for the above problems, previously investigated in the literature. It is a declarative approach to manage inconsistency that has been extensively studied in both databases and knowledge bases (KBs) (Bertossi 2011; Bienvenu and Bourgaux 2016). The crucial notions for CQA are those of repair and consistent answers. Several notions of minimality can be adopted, which in general give rise to the existence of several repairs.


Finite Query Answering in Expressive Description Logics with Transitive Roles

AAAI Conferences

We study the problem of finite ontology mediated query an-swering (FOMQA), the variant of OMQA where the represented world is assumed to be finite, and thus only finite models of the ontology are considered. We adopt the most typical setting with unions of conjunctive queries and ontologies expressed in description logics (DLs). The study of FOMQA isrelevant in settings that are not finitely controllable. This is the case not only for DLs without the finite model property, but also for those allowing transitive role declarations. When transitive roles are allowed, evaluating queries is challenging: FOMQA is undecidable for SHOIF and only known to be decidable for the Horn fragment of ALCIF. We show decidability of FOMQA for three proper fragments of SOIF: SOI, SOF, and SIF. Our approach is to characterise models relevant for deciding finite query entailment. Relying on a certain regularity of these models, we develop automata-based decision procedures with optimal complexity bounds.


A Parameterized Complexity View on Description Logic Reasoning

AAAI Conferences

Description logics are knowledge representation languages that have been designed to strike a balance between expressivity and computational tractability. Many different description logics have been developed, and numerous computational problems for these logics have been studied for their computational complexity. However, essentially all complexity analyses of reasoning problems for description logics use the one-dimensional framework of classical complexity theory. The multi-dimensional framework of parameterized complexity theory is able to provide a much more detailed image of the complexity of reasoning problems. In this paper we argue that the framework of parameterized complexity has a lot to offer for the complexity analysis of description logic reasoning problems---when one takes a progressive and forward-looking view on parameterized complexity tools. We substantiate our argument by means of three case studies. The first case study is about the problem of concept satisfiability for the logic ALC with respect to nearly acyclic TBoxes. The second case study concerns concept satisfiability for ALC concepts parameterized by the number of occurrences of union operators and the number of occurrences of full existential quantification. The third case study offers a critical look at data complexity results from a parameterized complexity point of view. These three case studies are representative for the wide range of uses for parameterized complexity methods for description logic problems.


Making Repairs in Description Logics More Gentle

AAAI Conferences

The classical approach for repairing a Description Logic ontology O in the sense of removing an unwanted consequence c is to delete a minimal number of axioms from O such that the resulting ontology O' does not have the consequence c. However, the complete deletion of axioms may be too rough, in the sense that it may also remove consequences that are actually wanted. To alleviate this problem, we propose a more gentle notion of repair in which axioms are not deleted, but only weakened. On the one hand, we investigate general properties of this gentle repair method. On the other hand, we propose and analyze concrete approaches for weakening axioms expressed in the Description Logic EL.


Finite Query Answering in Expressive Description Logics with Transitive Roles

arXiv.org Artificial Intelligence

We study the problem of finite ontology mediated query answering (FOMQA), the variant of OMQA where the represented world is assumed to be finite, and thus only finite models of the ontology are considered. We adopt the most typical setting with unions of conjunctive queries and ontologies expressed in description logics (DLs). The study of FOMQA is relevant in settings that are not finitely controllable. This is the case not only for DLs without the finite model property, but also for those allowing transitive role declarations. When transitive roles are allowed, evaluating queries is challenging: FOMQA is undecidable for SHOIF and only known to be decidable for the Horn fragment of ALCIF. We show decidability of FOMQA for three proper fragments of SOIF: SOI, SOF, and SIF. Our approach is to characterise models relevant for deciding finite query entailment. Relying on a certain regularity of these models, we develop automata-based decision procedures with optimal complexity bounds.


Probably approximately correct learning of Horn envelopes from queries

arXiv.org Artificial Intelligence

We propose an algorithm for learning the Horn envelope of an arbitrary domain using an expert, or an oracle, capable of answering certain types of queries about this domain. Attribute exploration from formal concept analysis is a procedure that solves this problem, but the number of queries it may ask is exponential in the size of the resulting Horn formula in the worst case. We recall a well-known polynomial-time algorithm for learning Horn formulas with membership and equivalence queries and modify it to obtain a polynomial-time probably approximately correct algorithm for learning the Horn envelope of an arbitrary domain.


Consensus Mining – A Guided Group Decision Process for the German Coalition Negotiations

AAAI Conferences

The paper focuses on the applicability of a consensus mining model for group decision making. There seem to be no mechanism for translating different preferences of rational individuals or homogeneous preferences of groups into a coherent group preference that is not either itself irrational or dictatorial. Therefore, we are expanding the opinion mining architecture OMA, which brings opinions with weighted description logics into a ranking, to include incomplete fuzzy preference relations. In this work we will verify how feasible fuzzy modeling algorithms are in the German coalition negotiations in autumn 2017.