Can I read The Precise Complexity of Reasoning in $\mathcal{ALC}$ with $\omega$-Admissible Concrete Domains (Extended Version) on EtoBox?

The Precise Complexity of Reasoning in $\mathcal{ALC}$ with $\omega$-Admissible Concrete Domains (Extended Version) by Borgwardt, Stefan; De Bortoli, Filippo; Koopmann, Patrick is a scholarly article available to read on EtoBox.

What is The Precise Complexity of Reasoning in $\mathcal{ALC}$ with $\omega$-Admissible Concrete Domains (Extended Version) about?

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.

Author

Borgwardt, Stefan; De Bortoli, Filippo; Koopmann, Patrick

Published

2024

Language

EN