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 C. Pilière, eds., Proceedings of the ESSLLI-2000 Student Session, August 2000
NExpTime-Complete Description Logics with Concrete Domains
In C. Pilière, eds., Proceedings of the ESSLLI-2000 Student Session, August 2000
- KurzfassungAbstract
Description Logics (DLs) are well-suited for the representation of abstract conceptual knowledge. Concrete knowledge such as knowledge about numbers, time intervals, and spatial regions can be incorporated into DLs by using so-called concrete domains. The basic Description Logics providing concrete domains is ALC(D) which was introduced by Baader and Hanschke. Reasoning with ALC(D) concepts is known to be PSpace-complete if reasoning with the concrete domain D is in PSpace. In this paper, we consider the extension of ALC(D) with acylic TBoxes and inverse roles and examine the computational complexity of the resulting formalism. As lower bounds, we show that there exists a concrete domain P for which reasoning is in PTime such that reasoning with ALC(P) and any of the above two extensions (separately) is NExpTime-hard. This is rather surprising since acyclic TBoxes and inverse roles are known to ``usually not increase the complexity of reasoning. For proving the lower bound, we introduce a NExpTime-complete variant of the Post Correspondence Problem and reduce it to the two logics under consideration. A corresponding upper bound, which states that reasoning with ALC(D) and both above extensions (together) is in NExpTime if reasoning with the concrete domain D is in NP, is proved in the accompanying technical report. - Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory
@inproceedings{ Lutz-ESSLLI-2000,
address = {University of Birmingham},
author = {C. {Lutz}},
booktitle = {Proceedings of the ESSLLI-2000 Student Session},
editor = {C. {Pili\`{e}re}},
month = {August},
title = {NExpTime-Complete Description Logics with Concrete Domains},
year = {2000},
}
