The Precise Complexity of Reasoning in $\mathcalALC$ with $\omega$-Admissible Concrete Domains (Extended Version)
<|reference_start|>The Precise Complexity of Reasoning in $\mathcalALC$ with $\omega$-Admissible Concrete Domains (Extended Version): Concrete domains have been introduced in the context of Description Logics to allow references to qualitative and quantitative values. In particular, the class of $\omega$-admissible concrete domains, which includes Allen's interval algebra, the region connection calculus (RCC8), and the rational numbers with ordering and equality, has been shown to yield extensions of $\mathcal{ALC}$ for which concept satisfiability w.r.t. a general TBox is decidable. In this paper, we present an algorithm based on type elimination and use it to show that deciding the consistency of an $\mathcal{ALC}(\mathfrak{D})$ ontology is ExpTime-complete if the concrete domain $\mathfrak{D}$ is $\omega$-admissible and its constraint satisfaction problem is decidable in exponential time.   While this allows us to reason with concept and role assertions, we also investigate feature assertions $f(a,c)$ that can specify a constant $c$ as the value of a feature $f$ for an individual $a$. We show that, under conditions satisfied by all known $\omega$-admissible domains, we can add feature assertions without affecting the complexity.<|reference_end|>
@article{borgwardt2024the,
    title={The Precise Complexity of Reasoning in $\mathcal{ALC}$ with
  $\omega$-Admissible Concrete Domains (Extended Version)},
    author={Stefan Borgwardt, Filippo De Bortoli, Patrick Koopmann},
    journal={arXiv preprint arXiv:2405.19096},
    year={2024},
    archivePrefix={arXiv},
    eprint={2405.19096},
    primaryClass={cs.LO}
}