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

Details
Bibtex

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},
}