{NExpTime}-complete Description Logics with Concrete Domains

C. LutzC. Lutz

Datei:Lutz-IJCAR.ps.gz

Download

C. Lutz
{NExpTime}-complete Description Logics with Concrete Domains
In Rajeev {Goré} and Alexander {Leitsch} and Tobias {Nipkow}, eds., Proceedings of the International Joint Conference on Automated Reasoning, Lecture Notes in Artifical Intelligence, 45--60, 2001. Springer

Details
Bibtex

KurzfassungAbstract
Concrete domains are an extension of Description Logics (DLs) allowing to
integrate reasoning about conceptual knowledge with reasoning about ``concrete properties of objects such as sizes, weights, and durations. It is known that reasoning with ALC(D), the basic DL admitting concrete domains, is PSpace-complete. In this paper, it is shown that the upper bound is not robust: we give three examples for seemingly harmless extensions of ALC(D)---namely acyclic TBoxes, inverse roles, and a role-forming concrete domain constructor---that make reasoning NExpTime-hard. As a corresponding upper bound, we show that reasoning with all three extensions together is in
NExpTime.
Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory

The final publication is available at Springer.

@inproceedings{ Lutz-IJCAR-01,
  address = {Siena, Italy},
  author = {C. {Lutz}},
  booktitle = {Proceedings of the International Joint Conference on Automated Reasoning},
  editor = {Rajeev {Gor\'e} and Alexander {Leitsch} and Tobias {Nipkow}},
  number = {2083},
  pages = {45--60},
  publisher = {Springer Verlag},
  series = {Lecture Notes in Artifical Intelligence},
  title = {{NExpTime}-complete Description Logics with Concrete Domains},
  year = {2001},
}