Concrete domains have been introduced in the area of 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. Unfortunately, in the presence of general concept inclusions (GCIs), which are supported by all modern DL systems, adding concrete domains may easily lead to undecidability.
To regain decidability of the DL ALC in the presence of GCIs, quite strong restrictions, called ω-admissibility, were imposed on the concrete domain. On the one hand, we generalize the notion of ω-admissibility from concrete domains with only binary predicates to concrete domains with predicates of arbitrary arity. On the other hand, we relate ω-admissibility to well-known notions from model theory. In particular, we show that finitely bounded homogeneous structures yield ω-admissible concrete domains. This allows us to show ω-admissibility of concrete domains using existing results from model theory.
When integrating concrete domains into lightweight DLs of the EL family, achieving decidability of reasoning is not enough. One wants the resulting DL to be tractable. This can be achieved by using so-called p-admissible concrete domains and restricting the interaction between the DL and the concrete domain. We investigate p-admissibility from an algebraic point of view. Again, this yields strong algebraic tools for demonstrating p-admissibility. In particular, we obtain an expressive numerical p-admissible concrete domain based on the rational numbers. Although ω-admissibility and p-admissibility are orthogonal conditions that are almost exclusive, our algebraic characterizations of these two properties allow us to locate an infinite class of p-admissible concrete domains whose integration into ALC yields
decidable DLs.
DL systems that can handle concrete domains allow their users to employ a fixed set of predicates of one or more fixed concrete domains when modelling concepts.
They do not provide their users with means for defining new predicates, let alone new concrete domains. The good news is that finitely bounded homogeneous structures offer precisely that. We show that integrating concrete domains based on finitely bounded homogeneous structures into ALC yields decidable DLs even if we allow predicates specified by first-order formulas. This class of structures also provides effective means for defining new ω-admissible concrete domains with at most binary predicates. The bad news is that defining ω-admissible concrete domains with predicates of higher arities is computationally hard. We obtain two new lower bounds for this meta-problem, but leave its decidability open. In contrast, we prove that there is no algorithm that would facilitate defining p-admissible concrete domains already for binary signatures.:1. Introduction . . . 1
2. Preliminaries . . . 5
3. Description Logics with Concrete Domains . . . 9
3.1. Basic definitions and undecidability results . . . 9
3.2. Decidable and tractable DLs with concrete domains . . . 16
4. A Model-Theoretic Analysis of ω-Admissibility . . . 23
4.1. Homomorphism ω-compactness via ω-categoricity . . . 23
4.2. Patchworks via homogeneity . . . 24
4.3. JDJEPD via decomposition into orbits . . . 27
4.4. Upper bounds via finite boundedness . . . 28
4.5. ω-admissible finitely bounded homogeneous structures . . . 32
4.6. ω-admissible homogeneous cores with a decidable CSP . . . 34
4.7. Coverage of the developed sufficient conditions . . . 36
4.8. Closure properties: homogeneity & finite boundedness . . . 39
5. A Model-Theoretic Analysis of p-Admissibility . . . 47
5.1. Convexity via square embeddings . . . 47
5.2. Convex ω-categorical structures . . . 50
5.3. Convex numerical structures . . . 52
5.4. Ages defined by forbidden substructures . . . 54
5.5. Ages defined by forbidden homomorphic images . . . 56
5.6. (Non-)closure properties of convexity . . . 59
6. Towards user-definable concrete domains . . . 61
6.1. A proof-theoretic perspective . . . 65
6.2. Universal Horn sentences and the JEP . . . 66
6.3. Universal sentences and the AP: the Horn case . . . 77
6.4. Universal sentences and the AP: the general case . . . 90
7. Conclusion . . . 99
7.1. Contributions and future outlook . . . 99
A. Concrete Domains without Equality . . . 103
Bibliography . . . 107
List of figures . . . 115
Alphabetical Index . . . 117
| Identifer | oai:union.ndltd.org:DRESDEN/oai:qucosa:de:qucosa:79907 |
| Date | 12 July 2022 |
| Creators | Rydval, Jakub |
| Contributors | Baader, Franz, Lutz, Carsten, Technische Universität Dresden |
| Source Sets | Hochschulschriftenserver (HSSS) der SLUB Dresden |
| Language | English |
| Detected Language | English |
| Type | info:eu-repo/semantics/publishedVersion, doc-type:doctoralThesis, info:eu-repo/semantics/doctoralThesis, doc-type:Text |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0025 seconds