NEXP TIME-complete description logics with concrete domains
ACM Transactions on Computational Logic · 2004-10 · 5 (4) · 669-705
DOI: 10.1145/1024922.1024925 ↗Kurz gefasst
Fachartikel in der Zeitschrift ACM Transactions on Computational Logic, 2004-10. Verfasst von Carsten Lutz. Die Arbeit wurde bisher 38-mal zitiert (Crossref) und nennt 47 Literaturangaben.
Abstract (Originalsprache)
Concrete domains are an extension of Description Logics (DLs) that allow one to integrate reasoning about conceptual knowledge with reasoning about "concrete qualities" of real-world entities such as their sizes, weights, and durations. In this article, 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 with respect to extensions of the language.
Zitieren
APA
Lutz, C. (2004). NEXP TIME-complete description logics with concrete domains. ACM Transactions on Computational Logic, 5(4), 669-705. https://doi.org/10.1145/1024922.1024925
Vancouver
Lutz C. NEXP TIME-complete description logics with concrete domains. ACM Transactions on Computational Logic. 2004;5(4):669-705. doi:10.1145/1024922.1024925
BibTeX
@article{Lutz2004,
author = {Lutz, Carsten},
title = {NEXP TIME-complete description logics with concrete domains},
journal = {ACM Transactions on Computational Logic},
year = {2004},
volume = {5},
number = {4},
pages = {669--705},
doi = {10.1145/1024922.1024925}
}
EUVIMED