On the Abstract Expressive Power of Description Logics with Concrete Domains
Abstract
Concrete domains have been introduced in Description Logic (DL) to enable reference to concrete objects (such as numbers) and predefined predicates on these objects (such as numerical comparisons) when defining concepts. The main emphasis of research in this context was on finding restrictions on the concrete domain such that its integration into certain DLs preserves decidability. In particular, it was shown that ω-admissible concrete domains can be integrated into the DL ALC without causing undecidability.
In this paper, we concentrate on investigating the expressive power of DLs with concrete domains. Basically, their semantics is defined using first-order interpretations as abstract domains extended with partial functions from the abstract domain into the concrete domain. The abstract expressive power of a given classical logic (first-order logic or DL) extended with a concrete domain is determined by which classes of first-order interpretations (i.e., abstract domains where we forget the partial functions and their values) can be expressed.
To show that such a class is not first-order definable, one can try to use a compactness argument, i.e., prove that first-order definability would lead to a contradiction to compactness of first-order logic (FO). In the first part of the paper, we will show that extensions of FO or ALC with a homomorphism ω-compact concrete domain share many formal properties with FO, such as the compactness and the downward Löwenheim-Skolem property. Nevertheless, their abstract expressive power need not be contained in that of FO. Note that any ω-admissible concrete domain is homomorphism ω-compact.
In the second part of the paper, we investigate whether finitely-bounded homogeneous structures, which preserve decidability if employed as concrete domains, can be used to express certain universal first-order sentences, which then could be added to knowledge bases without destroying decidability. We will see that this requires rather strong conditions on the universal first-order sentences or an extended scheme for integrating the concrete domain.