LATPub181: Unterschied zwischen den Versionen
Aus International Center for Computational Logic
Marcel Lippmann (Diskussion | Beiträge) KKeine Bearbeitungszusammenfassung |
Marcel Lippmann (Diskussion | Beiträge) KKeine Bearbeitungszusammenfassung |
||
| Zeile 1: | Zeile 1: | ||
{{Publikation Erster Autor | {{Publikation Erster Autor | ||
|ErsterAutorVorname= | |ErsterAutorVorname=Carsten | ||
|ErsterAutorNachname=Lutz | |ErsterAutorNachname=Lutz | ||
|FurtherAuthors= | |FurtherAuthors= | ||
| Zeile 20: | Zeile 20: | ||
}} | }} | ||
{{Publikation Details | {{Publikation Details | ||
|Abstract=Description Logics (DLs) are well-suited for the representation of abstract | |Abstract=Description Logics (DLs) are well-suited for the representation of abstract conceptual knowledge. Concrete knowledge such as knowledge about numbers, time intervals, and spatial regions can be incorporated into DLs by using so-called concrete domains. The basic Description Logics providing concrete domains is ALC(D) which was introduced by Baader and Hanschke. Reasoning with ALC(D) concepts is known to be PSpace-complete if reasoning with the concrete domain D is in PSpace. In this paper, we consider the extension of ALC(D) with acylic TBoxes and inverse roles and examine the computational complexity of the resulting formalism. As lower bounds, we show that there exists a concrete domain P for which reasoning is in PTime such that reasoning with ALC(P) and any of the above two extensions (separately) is NExpTime-hard. This is rather surprising since acyclic TBoxes and inverse roles are known to ``usually'' not increase the complexity of reasoning. For proving the lower bound, we introduce a NExpTime-complete variant of the Post Correspondence Problem and reduce it to the two logics under consideration. A corresponding upper bound, which states that reasoning with ALC(D) and both above extensions (together) is in NExpTime if reasoning with the concrete domain D is in NP, is proved in the accompanying technical report. | ||
conceptual knowledge. Concrete knowledge such as knowledge about numbers, time | |||
intervals, and spatial regions can be incorporated into DLs by using so-called | |||
concrete domains. The basic Description Logics providing concrete domains is | |||
ALC(D) which was introduced by Baader and Hanschke. Reasoning with ALC(D) | |||
concepts is known to be PSpace-complete if reasoning with the concrete domain | |||
D is in PSpace. In this paper, we consider the extension of ALC(D) with acylic | |||
TBoxes and inverse roles and examine the computational complexity of the | |||
resulting formalism. | |||
domain P for which reasoning is in PTime such that reasoning with ALC(P) and | |||
any of the above two extensions (separately) is NExpTime-hard. This is rather | |||
surprising since acyclic TBoxes and inverse roles are known to ``usually'' not | |||
increase the complexity of reasoning. | |||
introduce a NExpTime-complete variant of the Post Correspondence Problem and | |||
reduce it to the two logics under consideration. A corresponding upper bound, | |||
which states that reasoning with ALC(D) and both above extensions (together) | |||
is in NExpTime if reasoning with the concrete domain D is in NP, is proved | |||
in the accompanying technical report. | |||
|ISBN= | |ISBN= | ||
|ISSN= | |ISSN= | ||
| Zeile 61: | Zeile 38: | ||
year = {2000}, | year = {2000}, | ||
} | } | ||
}} | }} | ||
Version vom 23. März 2015, 13:24 Uhr
NExpTime-Complete Description Logics with Concrete Domains
Carsten LutzCarsten Lutz
Carsten Lutz
NExpTime-Complete Description Logics with Concrete Domains
In C. Pilière, eds., Proceedings of the ESSLLI-2000 Student Session, August 2000
NExpTime-Complete Description Logics with Concrete Domains
In C. Pilière, eds., Proceedings of the ESSLLI-2000 Student Session, August 2000
- KurzfassungAbstract
Description Logics (DLs) are well-suited for the representation of abstract conceptual knowledge. Concrete knowledge such as knowledge about numbers, time intervals, and spatial regions can be incorporated into DLs by using so-called concrete domains. The basic Description Logics providing concrete domains is ALC(D) which was introduced by Baader and Hanschke. Reasoning with ALC(D) concepts is known to be PSpace-complete if reasoning with the concrete domain D is in PSpace. In this paper, we consider the extension of ALC(D) with acylic TBoxes and inverse roles and examine the computational complexity of the resulting formalism. As lower bounds, we show that there exists a concrete domain P for which reasoning is in PTime such that reasoning with ALC(P) and any of the above two extensions (separately) is NExpTime-hard. This is rather surprising since acyclic TBoxes and inverse roles are known to ``usually not increase the complexity of reasoning. For proving the lower bound, we introduce a NExpTime-complete variant of the Post Correspondence Problem and reduce it to the two logics under consideration. A corresponding upper bound, which states that reasoning with ALC(D) and both above extensions (together) is in NExpTime if reasoning with the concrete domain D is in NP, is proved in the accompanying technical report. - Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory
@inproceedings{ Lutz-ESSLLI-2000,
address = {University of Birmingham},
author = {C. {Lutz}},
booktitle = {Proceedings of the ESSLLI-2000 Student Session},
editor = {C. {Pili\`{e}re}},
month = {August},
title = {NExpTime-Complete Description Logics with Concrete Domains},
year = {2000},
}
