NExpTime-complete Description Logics with Concrete Domains

Aus International Center for Computational Logic
Wechseln zu:Navigation, Suche

Toggle side column

NExpTime-complete Description Logics with Concrete Domains

Carsten LutzCarsten Lutz
NExpTime-complete Description Logics with Concrete Domains


Carsten Lutz
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: Automatentheorie
@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},
}