Version vom 23. März 2015, 13:24 Uhr

NExpTime-complete Description Logics with Concrete Domains

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

@@ Zeile 1: / Zeile 1: @@
 {{Publikation Erster Autor
-|ErsterAutorVorname=C.
+|ErsterAutorVorname=Carsten
 |ErsterAutorNachname=Lutz
 |FurtherAuthors=
@@ Zeile 20: / Zeile 20: @@
 }}
 {{Publikation Details
-|Abstract=Concrete domains are an extension of Description Logics (DLs) allowing to
+|Abstract=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.
-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.
 |ISBN=
 |ISSN=
@@ Zeile 51: / Zeile 41: @@
    year = {2001},
 }
 }}

LATPub207: Unterschied zwischen den Versionen

Version vom 23. März 2015, 13:24 Uhr

NExpTime-complete Description Logics with Concrete Domains

Carsten LutzCarsten Lutz