# 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

In C. Pilière, eds.,

**NExpTime-Complete Description Logics with Concrete Domains**In C. Pilière, eds.,

*Proceedings of the ESSLLI-2000 Student Session*, August 2000**Kurzfassung****Abstract**

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:**Automatentheorie

```
@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},
}
```