LATPub283: 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 18: | Zeile 18: | ||
}} | }} | ||
{{Publikation Details | {{Publikation Details | ||
|Abstract=Concrete domains are an extension of Description Logics (DLs) that | |Abstract=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 sizes, weights, and durations. In this paper, we are concerned with the complexity of Description Logics providing for concrete domains: starting from the complexity result established in [Lutz 2002b], which states that reasoning with the basic propositionally closed DL with concrete domains ALC(D) is PSpace-complete (provided that some weak conditions are satisfied), we perform an in-depth analysis of the complexity of extensions of this logic. More precisely, we consider five natural and seemingly ``harmless'' extensions of ALC(D) and prove that, for all five extensions, reasoning is NExpTime-complete (again if some weak conditions are satisfied). Thus, we show that the PSpace upper bound for reasoning with ALC(D) cannot be considered robust w.r.t. extensions of the language. | ||
allows to integrate reasoning about conceptual knowledge with | |||
reasoning about ``concrete qualities'' of real-world entities such | |||
as their sizes, weights, and durations. In this paper, we are | |||
concerned with the complexity of Description Logics providing for | |||
concrete domains: starting from the complexity result established in | |||
[Lutz 2002b], which states that reasoning with the basic | |||
propositionally closed DL with concrete domains ALC(D) is | |||
PSpace-complete (provided that some weak conditions are satisfied), | |||
we perform an in-depth analysis of the complexity of extensions of | |||
this logic. More precisely, we consider five natural and seemingly | |||
``harmless'' extensions of ALC(D) and prove that, for all five | |||
extensions, reasoning is NExpTime-complete (again if some weak | |||
conditions are satisfied). | |||
bound for reasoning with ALC(D) cannot be considered robust w.r.t. | |||
extensions of the language. | |||
|ISBN= | |ISBN= | ||
|ISSN= | |ISSN= | ||
| Zeile 52: | Zeile 36: | ||
year = {2004}, | year = {2004}, | ||
} | } | ||
}} | }} | ||
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
ACM Transactions on Computational Logic, 5(4):669-705, 2004
NExpTime-complete Description Logics with Concrete Domains
ACM Transactions on Computational Logic, 5(4):669-705, 2004
- KurzfassungAbstract
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 sizes, weights, and durations. In this paper, we are concerned with the complexity of Description Logics providing for concrete domains: starting from the complexity result established in [Lutz 2002b], which states that reasoning with the basic propositionally closed DL with concrete domains ALC(D) is PSpace-complete (provided that some weak conditions are satisfied), we perform an in-depth analysis of the complexity of extensions of this logic. More precisely, we consider five natural and seemingly ``harmless extensions of ALC(D) and prove that, for all five extensions, reasoning is NExpTime-complete (again if some weak conditions are satisfied). Thus, we show that the PSpace upper bound for reasoning with ALC(D) cannot be considered robust w.r.t. extensions of the language. - Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory
@article{ Lutz-ToCL-04,
author = {Carsten {Lutz}},
journal = {{ACM} Transactions on Computational Logic},
number = {4},
pages = {669--705},
title = {{NExpTime}-complete Description Logics with Concrete Domains},
volume = {5},
year = {2004},
}
