NExpTime-complete Description Logics with Concrete Domains
From International Center for Computational Logic
NExpTime-complete Description Logics with Concrete Domains
Carsten LutzCarsten Lutz
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
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
- 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
@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},
}
