• English
    • Deutsch
  • English 
    • English
    • Deutsch
  • Login
View Item 
  •   Home
  • Universität Ulm
  • Publikationen
  • View Item
  •   Home
  • Universität Ulm
  • Publikationen
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Optimisation of tableau-based reasoning systems for expressive description logics

Thumbnail
Diss_Steigmiller_201 ... (2.454Mb)
Erstveröffentlichung
2016-06-24
Authors
Steigmiller, Andreas
Referee
Glimm, Birte
Schöning, Uwe
Möller, Ralf
Dissertation


Faculties
Fakultät für Ingenieurwissenschaften, Informatik und Psychologie
Institutions
Institut für Künstliche Intelligenz
Institut für Theoretische Informatik
Abstract
Logic-based knowledge representation formalisms, such as Description Logics, constitute the basis of well-known ontology languages, e.g., the Web Ontology Language, and, thus, are gaining more and more popularity for realising the knowledge and information handling of intelligent systems in various disciplines, e.g., life sciences, medical informatics, the Semantic Web. A particular strength of such logical formalisms is that automated reasoning systems can be used to derive logically implied consequences of the explicitly represented knowledge. Although expressive representation formalisms provide many modelling constructors to represent application domains in detail, they require sophisticated reasoning procedures, such as tableau algorithms, which systematically try to build counter examples in order to refute statements w.r.t. the represented knowledge. In this thesis, we present a range of new optimisation techniques for such tableau-based reasoning systems, which improve the reasoning performance especially for more expressive Description Logics. First, we propose a new absorption technique, where axioms are rewritten such that the non-deterministic processing within the reasoning system is notably reduced. We further extend absorption to enable an efficient handling of so-called nominal schemas, which even allow for expressing arbitrary rule-based knowledge. In addition, we present a tight coupling of tableau algorithms with saturation procedures, which enables a very efficient derivation of many consequences and, thus, results in a pay-as-you-go behaviour, i.e., the reasoning system can dynamically process all those parts very efficiently that are not directly influenced by expressive modelling constructors. Last but not least, we present different caching and parallelisation techniques, which primarily address reasoning with many facts. We integrated the developed optimisation techniques into a new, freely available reasoning system called Konclude and our evaluation with several thousand ontologies shows that these optimisations lead to new performance standards. These results have also been confirmed by international competitions, where Konclude was able to win several awards.
Date created
2016
Subject headings
[GND]: Logik | OWL <Informatik> | Tableau <Logik> | Optimierung
[LCSH]: Description logics | Logic | Ontology | Reasoning; Data processing | Tableau (Computer file) | Absorption
[Free subject headings]: Optimisation | Automated reasoning | OWL | Nominal schemas
[DDC subject group]: DDC 004 / Data processing & computer science
License
Standard
https://oparu.uni-ulm.de/xmlui/license_v3

Metadata
Show full item record

DOI & citation

Please use this identifier to cite or link to this item: http://dx.doi.org/10.18725/OPARU-4003

Steigmiller, Andreas (2016): Optimisation of tableau-based reasoning systems for expressive description logics. Open Access Repositorium der Universität Ulm und Technischen Hochschule Ulm. Dissertation. http://dx.doi.org/10.18725/OPARU-4003
Citation formatter >



Policy | kiz service OPARU | Contact Us
Impressum | Privacy statement
 

 

Advanced Search

Browse

All of OPARUCommunities & CollectionsPersonsInstitutionsPublication typesUlm SerialsDewey Decimal ClassesEU projects UlmDFG projects UlmOther projects Ulm

My Account

LoginRegister

Statistics

View Usage Statistics

Policy | kiz service OPARU | Contact Us
Impressum | Privacy statement