The Experts below are selected from a list of 360 Experts worldwide ranked by ideXlab platform
Thomas Lukasiewicz - One of the best experts on this subject based on the ideXlab platform.
-
a novel combination of answer set programming with Description Logics for the semantic web
IEEE Transactions on Knowledge and Data Engineering, 2010Co-Authors: Thomas LukasiewiczAbstract:We present a novel combination of disjunctive programs under the answer set semantics with Description Logics for the Semantic Web. The combination is based on a well-balanced interface between disjunctive programs and Description Logics, which guarantees the decidability of the resulting formalism without assuming syntactic restrictions. We show that the new formalism has very nice semantic properties. In particular, it faithfully extends both disjunctive programs and Description Logics. Furthermore, we describe algorithms for reasoning in the new formalism, and we give a precise picture of its computational complexity. We also define the well-founded semantics for the normal case, where normal programs are combined with tractable Description Logics, and we explore its semantic and computational properties. In particular, we show that the well-founded semantics approximates the answer set semantics. We also describe algorithms for the problems of consistency checking and literal entailment under the well-founded semantics, and we give a precise picture of their computational complexity. As a crucial property, in the normal case, consistency checking and literal entailment under the well-founded semantics are both tractable in the data complexity, and even first-order rewritable (and thus can be done in LogSpace in the data complexity) in a special case that is especially useful for representing mappings between ontologies.
-
managing uncertainty and vagueness in Description Logics for the semantic web
Journal of Web Semantics, 2008Co-Authors: Thomas Lukasiewicz, Umberto StracciaAbstract:Ontologies play a crucial role in the development of the Semantic Web as a means for defining shared terms in web resources. They are formulated in web ontology languages, which are based on expressive Description Logics. Significant research efforts in the semantic web community are recently directed towards representing and reasoning with uncertainty and vagueness in ontologies for the Semantic Web. In this paper, we give an overview of approaches in this context to managing probabilistic uncertainty, possibilistic uncertainty, and vagueness in expressive Description Logics for the Semantic Web.
-
expressive probabilistic Description Logics
Artificial Intelligence, 2008Co-Authors: Thomas LukasiewiczAbstract:The work in this paper is directed towards sophisticated formalisms for reasoning under probabilistic uncertainty in ontologies in the Semantic Web. Ontologies play a central role in the development of the Semantic Web, since they provide a precise definition of shared terms in web resources. They are expressed in the standardized web ontology language OWL, which consists of the three increasingly expressive sublanguages OWL Lite, OWL DL, and OWL Full. The sublanguages OWL Lite and OWL DL have a formal semantics and a reasoning support through a mapping to the expressive Description Logics SHIF(D) and SHOIN(D), respectively. In this paper, we present the expressive probabilistic Description Logics P-SHIF(D) and P-SHOIN(D), which are probabilistic extensions of these Description Logics. They allow for expressing rich terminological probabilistic knowledge about concepts and roles as well as assertional probabilistic knowledge about instances of concepts and roles. They are semantically based on the notion of probabilistic lexicographic entailment from probabilistic default reasoning, which naturally interprets this terminological and assertional probabilistic knowledge as knowledge about random and concrete instances, respectively. As an important additional feature, they also allow for expressing terminological default knowledge, which is semantically interpreted as in Lehmann's lexicographic entailment in default reasoning from conditional knowledge bases. Another important feature of this extension of SHIF(D) and SHOIN(D) by probabilistic uncertainty is that it can be applied to other classical Description Logics as well. We then present sound and complete algorithms for the main reasoning problems in the new probabilistic Description Logics, which are based on reductions to reasoning in their classical counterparts, and to solving linear optimization problems. In particular, this shows the important result that reasoning in the new probabilistic Description Logics is decidable/computable. Furthermore, we also analyze the computational complexity of the main reasoning problems in the new probabilistic Description Logics in the general as well as restricted cases.
-
a novel combination of answer set programming with Description Logics for the semantic web
European Semantic Web Conference, 2007Co-Authors: Thomas LukasiewiczAbstract:We present a novel combination of disjunctive logic programs under the answer set semantics with Description Logics for the Semantic Web. The combination is based on a well-balanced interface between disjunctive logic programs and Description Logics, which guarantees the decidability of the resulting formalism without assuming syntactic restrictions. We show that the new formalism has very nice semantic properties. In particular, it faithfully extends both disjunctive programs and Description Logics. Furthermore, we describe algorithms for reasoning in the new formalism, and we give a precise picture of its computational complexity. We also provide a special case with polynomial data complexity.
Umberto Straccia - One of the best experts on this subject based on the ideXlab platform.
-
Defeasible inheritance-based Description Logics
Journal of Artificial Intelligence Research, 2013Co-Authors: Giovanni Casini, Umberto StracciaAbstract: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.
-
defeasible inheritance based Description Logics
International Joint Conference on Artificial Intelligence, 2011Co-Authors: Giovanni Casini, Umberto StracciaAbstract:Defeasible inheritance networks are a nonmonotonic framework that deals with hierarchical knowledge. On the other hand, rational closure is acknowledged as a landmark of the preferential approach. 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, a family of Logics well-suited to model structured information. In both cases we will provide a simple reasoning method that is build on top of the classical entailment relation.
-
reasoning within fuzzy Description Logics
arXiv: Artificial Intelligence, 2011Co-Authors: Umberto StracciaAbstract:Description Logics (DLs) are suitable, well-known, Logics for managing structured knowledge. They allow reasoning about individuals and well defined concepts, i.e., set of individuals with common properties. The experience in using DLs in applications has shown that in many cases we would like to extend their capabilities. In particular, their use in the context of Multimedia Information Retrieval (MIR) leads to the convincement that such DLs should allow the treatment of the inherent imprecision in multimedia object content representation and retrieval. In this paper we will present a fuzzy extension of ALC, combining Zadeh's fuzzy logic with a classical DL. In particular, concepts becomes fuzzy and, thus, reasoning about imprecise concepts is supported. We will define its syntax, its semantics, describe its properties and present a constraint propagation calculus for reasoning in it.
-
rational closure for defeasible Description Logics
European Conference on Logics in Artificial Intelligence, 2010Co-Authors: Giovanni Casini, Umberto StracciaAbstract:In the field of non-monotonic Logics, the notion of rational closure is acknowledged as a landmark, and we are going to see that such a construction can be characterised by means of a simple method in the context of propositional logic. We then propose an application of our approach to rational closure in the field of Description Logics, an important knowledge representation formalism, and provide a simple decision procedure for this case.
-
Fuzzy Description Logics with general t-norms and datatypes
Fuzzy Sets and Systems, 2009Co-Authors: Fernando Bobillo, Umberto StracciaAbstract:Fuzzy Description Logics (DLs) are a family of Logics which allow the representation of (and the reasoning within) structured knowledge affected by vagueness. Although a relatively important amount of work has been carried out in the last years, current fuzzy DLs still present several limitations. In this work we face two problems: the common restriction to Zadeh and Lukasiewicz fuzzy Logics and the inability to deal with datatypes different from fuzzy sets. In particular, we propose a semantics based on the use of a general left-continuous t-norm and an involutive negation (specially focused on Product logic) and, furthermore, we show how to handle functional concrete roles relating individuals of the domain and strings, real or integer numbers.
Carsten Lutz - One of the best experts on this subject based on the ideXlab platform.
-
fusions of Description Logics and abstract Description systems
arXiv: Artificial Intelligence, 2011Co-Authors: Franz Baader, Carsten Lutz, Holger Sturm, Frank WolterAbstract:Fusions are a simple way of combining Logics. For normal modal Logics, fusions have been investigated in detail. In particular, it is known that, under certain conditions, decidability transfers from the component Logics to their fusion. Though Description Logics are closely related to modal Logics, they are not necessarily normal. In addition, ABox reasoning in Description Logics is not covered by the results from modal Logics. In this paper, we extend the decidability transfer results from normal modal Logics to a large class of Description Logics. To cover different Description Logics in a uniform way, we introduce abstract Description systems, which can be seen as a common generalization of Description and modal Logics, and show the transfer results in this general setting.
-
probabilistic Description Logics for subjective uncertainty
Principles of Knowledge Representation and Reasoning, 2010Co-Authors: Carsten Lutz, Lutz SchroderAbstract:We propose a new family of probabilistic Description Logics (DLs) that, in contrast to most existing approaches, are derived in a principled way from Halpern's probabilistic first-order logic. The resulting probabilistic DLs have a two-dimensional semantics similar to certain popular combinations of DLs with temporal logic and are well-suited for capturing subjective probabilities. Our main contribution is a detailed study of the complexity of reasoning in the new family of probabilistic DLs, showing that it ranges from PTIME for weak variants based on the lightweight DL EL to undecidable for some expressive variants based on the DL ALC.
-
the complexity of conjunctive query answering in expressive Description Logics
International Joint Conference on Automated Reasoning, 2008Co-Authors: Carsten LutzAbstract:Conjunctive query answering plays a prominent role in applications of Description Logics (DLs) that involve instance data, but its exact complexity was a long-standing open problem. We determine the complexity of conjunctive query answering in expressive DLs between $\mathcal{ALC}$ and $\mathcal{SHIQ}$, and thus settle the problem. In a nutshell, we show that conjunctive query answering is 2 ExpTime -complete in the presence of inverse roles, and only ExpTime -complete without them.
-
temporal Description Logics a survey
International Symposium on Temporal Representation and Reasoning, 2008Co-Authors: Carsten Lutz, Frank Wolter, M ZakharyashevAbstract:We survey temporal Description Logics that are based on standard temporal Logics such as LTL and CTL. In particular, we concentrate on the computational complexity of the satisfiability problem and algorithms for deciding it.
-
conservative extensions in expressive Description Logics
International Joint Conference on Artificial Intelligence, 2007Co-Authors: Carsten Lutz, Dirk Walther, Frank WolterAbstract:The notion of a conservative extension plays a central role in ontology design and integration: it can be used to formalize ontology refinements, safe mergings of two ontologies, and independent modules inside an ontology. Regarding reasoning support, the most basic task is to decide whether one ontology is a conservative extension of another. It has recently been proved that this problem is decidable and 2ExpTime-complete if ontologies are formulated in the basic Description logic ALC. We consider more expressive Description Logics and begin to map out the boundary between Logics for which conservativity is decidable and those for which it is not. We prove that conservative extensions are 2ExpTime-complete in ALCQI, but undecidable in ALCQIO. We also show that if conservative extensions are defined model-theoretically rather than in terms of the consequence relation, they are undecidable already in ALC.
Ulrike Sattler - One of the best experts on this subject based on the ideXlab platform.
-
An overview of tableau algorithms for Description Logics. Studia Logica, 2001. To appear. An abridged version appeared in Tableaux 2000, volume 1847
2015Co-Authors: Franz Baader, Ulrike SattlerAbstract:Abstract. Description Logics are a family of knowledge representation formalisms that are descended from semantic networks and frames via the system Kl-one. During the last decade, it has been shown that the important reasoning problems (like subsumption and satisfiability) in a great variety of Description Logics can be decided using tableau-like algorithms. This is not very surprising since Description Logics have turned out to be closely related to propositional modal Logics and Logics of programs (such as propositional dynamic logic), for which tableau procedures have been quite successful. Nevertheless, due to different underlying intuitions and applications, most Description Logics differ significantly from run-of-the-mill modal and program Logics. Consequently, the research on tableau algorithms in Description Logics led to new techniques and results, which are, however, also of interest for modal logicians. In this article, we will focus on three features that play an important rôle in Description Logics (number restrictions, ter-minological axioms, and role constructors), and show how they can be taken into account by tableau algorithms
-
chapter 3 Description Logics
Foundations of Artificial Intelligence, 2008Co-Authors: Franz Baader, Ian Horrocks, Ulrike SattlerAbstract:Publisher Summary This chapter discusses Description Logics (DLs), which are a family of logic-based knowledge representation languages that can be used to represent the terminological knowledge of an application domain in a structured and formally well-structured way. It discusses their provenience and history and explains the way the field has developed. It describes the basic DL ALC in some detail, including definitions of syntax, semantics, and basic reasoning services, and discusses important extensions such as inverse roles, number restrictions, and concrete domains. It discusses (1) the relationship between DLs and other formalisms, in particular first order and modal Logics, (2) the most commonly used reasoning techniques, in particular tableau, resolution, and automata based techniques, and (3) the computational complexity of basic reasoning problems. After reviewing some of the most prominent applications of DLs, in particular ontology language applications, the chapter discusses other aspects of DL research.
-
reasoning in Description Logics by a reduction to disjunctive datalog
Journal of Automated Reasoning, 2007Co-Authors: Ullrich Hustadt, Boris Motik, Ulrike SattlerAbstract:As applications of Description Logics proliferate, efficient reasoning with knowledge bases containing many assertions becomes ever more important. For such cases, we developed a novel reasoning algorithm that reduces a $\mathcal{SHIQ}$ knowledge base to a disjunctive datalog program while preserving the set of ground consequences. Queries can then be answered in the resulting program while reusing existing and practically proven optimization techniques of deductive databases, such as join-order optimizations or magic sets. Moreover, we use our algorithm to derive precise data complexity bounds: we show that $\mathcal{SHIQ}$ is data complete for NP, and we identify an expressive fragment of $\mathcal{SHIQ}$ with polynomial data complexity.
-
conjunctive query answering for Description Logics with transitive roles
International Workshop Description Logics, 2006Co-Authors: Birte Glimm, Ian Horrocks, Ulrike SattlerAbstract:An important reasoning task, in addition to the standard DL reasoning services, is conjunctive query answering. In this paper, we present algorithms for conjunctive query answering in the expressive Description Logics SHQ and SHOQ. In particular, we allow for transitive (or nonsimple) roles in the query body, which is a feature that is not supported by other existing conjunctive query answering algorithms. For SHQ, we achieve this by extending the logic with a restricted form of ↓ binders and state variables as known from Hybrid Logics. We also highlight, why the addition of inverse roles makes the task of finding a decision procedure for conjunctive query answering more complicated.
-
data complexity of reasoning in very expressive Description Logics
International Joint Conference on Artificial Intelligence, 2005Co-Authors: Ullrich Hustadt, Boris Motik, Ulrike SattlerAbstract:Data complexity of reasoning in Description Logics (DLs) estimates the performance of reasoning algorithms measured in the size of the ABox only. We show that, even for the very expressive DL SHIQ, satisfiability checking is data complete for NP. For applications with large ABoxes, this can be a more accurate estimate than the usually considered combined complexity, which is EXPTIME-complete. Furthermore, we identify an expressive fragment, Horn-SHIQ, which is data complete for P, thus being very appealing for practical usage.
Franz Baader - One of the best experts on this subject based on the ideXlab platform.
-
metric temporal Description Logics with interval rigid names
Frontiers of Combining Systems, 2017Co-Authors: Franz Baader, Stefan Borgwardt, Patrick Koopmann, Ana Ozaki, Veronika ThostAbstract:In contrast to qualitative linear temporal Logics, which can be used to state that some property will eventually be satisfied, metric temporal Logics allow to formulate constraints on how long it may take until the property is satisfied. While most of the work on combining Description Logics (DLs) with temporal Logics has concentrated on qualitative temporal Logics, there has recently been a growing interest in extending this work to the quantitative case. In this paper, we complement existing results on the combination of DLs with metric temporal Logics over the natural numbers by introducing interval-rigid names. This allows to state that elements in the extension of certain names stay in this extension for at least some specified amount of time.
-
An overview of tableau algorithms for Description Logics. Studia Logica, 2001. To appear. An abridged version appeared in Tableaux 2000, volume 1847
2015Co-Authors: Franz Baader, Ulrike SattlerAbstract:Abstract. Description Logics are a family of knowledge representation formalisms that are descended from semantic networks and frames via the system Kl-one. During the last decade, it has been shown that the important reasoning problems (like subsumption and satisfiability) in a great variety of Description Logics can be decided using tableau-like algorithms. This is not very surprising since Description Logics have turned out to be closely related to propositional modal Logics and Logics of programs (such as propositional dynamic logic), for which tableau procedures have been quite successful. Nevertheless, due to different underlying intuitions and applications, most Description Logics differ significantly from run-of-the-mill modal and program Logics. Consequently, the research on tableau algorithms in Description Logics led to new techniques and results, which are, however, also of interest for modal logicians. In this article, we will focus on three features that play an important rôle in Description Logics (number restrictions, ter-minological axioms, and role constructors), and show how they can be taken into account by tableau algorithms
-
fusions of Description Logics and abstract Description systems
arXiv: Artificial Intelligence, 2011Co-Authors: Franz Baader, Carsten Lutz, Holger Sturm, Frank WolterAbstract:Fusions are a simple way of combining Logics. For normal modal Logics, fusions have been investigated in detail. In particular, it is known that, under certain conditions, decidability transfers from the component Logics to their fusion. Though Description Logics are closely related to modal Logics, they are not necessarily normal. In addition, ABox reasoning in Description Logics is not covered by the results from modal Logics. In this paper, we extend the decidability transfer results from normal modal Logics to a large class of Description Logics. To cover different Description Logics in a uniform way, we introduce abstract Description systems, which can be seen as a common generalization of Description and modal Logics, and show the transfer results in this general setting.
-
Description Logics
Reasoning Web. Semantic Technologies for Information Systems, 2009Co-Authors: Franz BaaderAbstract:Description Logics (DLs) are a well-investigated family of logic-based knowledge representation formalisms, which can be used to represent the conceptual knowledge of an application domain in a structured and formally well-understood way. They are employed in various application domains, such as natural language processing, configuration, and databases, but their most notable success so far is the adoption of the DL-based language OWL as standard ontology language for the semantic web. This article concentrates on the problem of designing reasoning procedures for DLs. After a short introduction and a brief overview of the research in this area of the last 20 years, it will on the one hand present approaches for reasoning in expressive DLs, which are the foundation for reasoning in the Web ontology language OWL DL. On the other hand, it will consider tractable reasoning in the more light-weight DL $\mathcal{EL}$, which is employed in bio-medical ontologies, and which is the foundation for the OWL 2 profile OWL 2 EL.
-
chapter 3 Description Logics
Foundations of Artificial Intelligence, 2008Co-Authors: Franz Baader, Ian Horrocks, Ulrike SattlerAbstract:Publisher Summary This chapter discusses Description Logics (DLs), which are a family of logic-based knowledge representation languages that can be used to represent the terminological knowledge of an application domain in a structured and formally well-structured way. It discusses their provenience and history and explains the way the field has developed. It describes the basic DL ALC in some detail, including definitions of syntax, semantics, and basic reasoning services, and discusses important extensions such as inverse roles, number restrictions, and concrete domains. It discusses (1) the relationship between DLs and other formalisms, in particular first order and modal Logics, (2) the most commonly used reasoning techniques, in particular tableau, resolution, and automata based techniques, and (3) the computational complexity of basic reasoning problems. After reviewing some of the most prominent applications of DLs, in particular ontology language applications, the chapter discusses other aspects of DL research.
