The complexity of description logics with concrete domains

Lutz, Carsten; Baader, Franz

doi:HT013327603

The complexity of description logics with concrete domains

Lutz, Carsten (Author)

2002

Verantwortlichkeitsangabevorgelegt von Carsten Lutz

ImpressumAachen : Publikationsserver der RWTH Aachen University 2002

UmfangII, 216 S. : graph. Darst.

Aachen, Techn. Hochsch., Diss., 2002

Genehmigende Fakultät
Fak01

Hauptberichter/Gutachter
Baader, Franz (Thesis advisor)

Tag der mündlichen Prüfung/Habilitation
2002-02-08

Online
URN: urn:nbn:de:hbz:82-opus-3032
URL: https://publications.rwth-aachen.de/record/60053/files/Lutz_Carsten.pdf

Einrichtungen

Fakultät für Mathematik, Informatik und Naturwissenschaften (100000)

Inhaltliche Beschreibung (Schlagwörter)
Informatik (frei) ; Wissensrepräsentation (frei) ; Terminologische Logik (frei) ; Erfüllbarkeitsproblem (frei) ; Unentscheidbarkeit (frei) ; Berechnungskomplexität (frei)

Thematische Einordnung (Klassifikation)
DDC: 004

Kurzfassung
Konkrete Bereiche sind eine Erweiterung von Beschreibungslogiken (BLen), die eine Integration des Schließens über konzeptuelles Wissen mit dem Schließen über „konkrete Eigenschaften” von Objekten erlaubt. Solche konkreten Eigenschaften können z.B. das Alter, das Gewicht, die Form und die zeitliche Ausdehnung von Objekten sein. In dieser Arbeit wird eine umfassende Komplexitätsanalyse von BLen durchgeführt, die mit konkreten Bereichen ausgestattet sind. Die wichtigsten Resultate dieser Untersuchung können wie folgt beschrieben werden: (i) Schließen in ALC(D), der grundlegenden BL mit konkreten Bereichen, ist PSpace-vollständig wenn Schließen mit dem konkreten Bereich D in PSpace ist; (ii) für viele scheinbar „harmlose” Erweiterungen von ALC(D), wie z.B. um azyklische TBoxen, Rollenkonjunktion oder inverse Rollen, steigt die Komplexität des Schließens von PSpace-vollständig auf NExpTime-vollständig an, zumindest für eine große Klasse von konkreten Bereichen; und (iii) obwohl im allgemeinen die Kombination von konkreten Bereichen und generellen TBoxen zur Unentscheidbarkeit des Schließens führt, gibt es einen interessanten temporalen konkreten Bereich, der mit generellen TBoxen kombiniert werden kann, ohne die Entscheidbarkeit des Schließens zu verlieren. Dieser konkrete Bereich kann zur Konstruktion einer sehr ausdrucksstarken temporalen Beschreibungslogik verwendet werden, die Intervalle als zeitliches Primitiv verwendet. Als weiteres Thema werden Beschreibungslogiken betrachtet, die über Gleichheits- und Ungleichheitsoperatoren auf Attributketten verfügen. Es stellt sich heraus, dass ein enger Zusammenhang zwischen solchen Logiken und BLen mit konkreten Bereichen besteht: in den meisten Fällen stimmt die Komplexität des Schließens in einer Logik mit konkreten Bereichen mit der Komplexität des Schließens in der korrespondierenden BL mit (Un)gleichheit von Attributketten überein.

Concrete domains are an extension of Description Logics (DLs) that allows to integrate reasoning about conceptual knowledge with reasoning about "concrete qualities" of real world entities such as their age, weight, shape, and temporal extension. In this thesis, we perform an in-depth analysis of the computational complexity of reasoning with DLs that are equipped with concrete domains. The main results are that (i) reasoning with ALC(D), the basic DL ALC extended with a concrete domain D, is PSpace-complete if reasoning with D is in PSpace; (ii) for many seemingly "harmless" extensions of ALC(D), such as the extension with acyclic TBoxes, role conjunction, and inverse roles, the complexity of reasoning leaps from PSpace-completeness to NExpTime-completeness---at least for a large class of concrete domains; and (iii) although, in general, the combination of concrete domains and general TBoxes leads to undecidability of reasoning, there exists an interesting temporal concrete domain that can be combined with general TBoxes without sacrificing decidability. This concrete domain is used to devise a rather powerful interval-based temporal Description Logic. As a side-track, we illuminate the connection between Description Logics equipped with concrete domains and DLs providing for so-called feature agreement and disagreement constructors. Indeed, this connection turns out to be quite close: in most cases, the complexity of reasoning with a DL providing for concrete domains is identical to the complexity of reasoning with the corresponding DL that offers feature (dis)agreements.

Fulltext:
PDF
(additional files)