EUVIMEDEUVIMED entdecken
Crossref

NEXP TIME-complete description logics with concrete domains

Carsten Lutz

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →