Concrete Domains Meet Expressive Cardinality Restrictions in Description Logics
Publikation: Beitrag in Buch/Konferenzbericht/Sammelband/Gutachten › Beitrag in Konferenzband › Beigetragen › Begutachtung
Beitragende
Abstract
Standard Description Logics (DLs) can encode quantitative aspects of an application domain through either number restrictions, which constrain the number of individuals that are in a certain relationship with an individual, or concrete domains, which can be used to assign concrete values to individuals using so-called features. These two mechanisms have been extended towards very expressive DLs, for which reasoning nevertheless remains decidable. Number restrictions have been generalized to more powerful comparisons of sets of role successors in ALCSCC, while the comparison of feature values of different individuals in ALC(D) has been studied in the context of ω-admissible concrete domains D. In this paper, we combine both formalisms and investigate the complexity of reasoning in the thus obtained DL ALCOSCC(D), which additionally includes the ability to refer to specific individuals by name. We show that, in spite of its high expressivity, the consistency problem for this DL is ExpTime-complete, assuming that the constraint satisfaction problem of D is also decidable in exponential time. It is thus not higher than the complexity of the basic DL ALC. At the same time, we show that many natural extensions to this DL, including a tighter integration of the concrete domain and number restrictions, lead to undecidability.
Details
| Originalsprache | Englisch |
|---|---|
| Titel | Automated Deduction - CADE 30 - 30th International Conference on Automated Deduction, 2025, Proceedings |
| Redakteure/-innen | Clark Barrett, Uwe Waldmann |
| Herausgeber (Verlag) | Springer |
| Seiten | 676-695 |
| Seitenumfang | 20 |
| ISBN (elektronisch) | 978-3-031-99984-0 |
| ISBN (Print) | 978-3-031-99983-3 |
| Publikationsstatus | Veröffentlicht - 2025 |
| Peer-Review-Status | Ja |
Publikationsreihe
| Reihe | Lecture Notes in Artificial Intelligence (LNAI) |
|---|---|
| Band | 15943 |
| ISSN | 0302-9743 |
Externe IDs
| Scopus | 105013459854 |
|---|---|
| ORCID | /0000-0002-4049-221X/work/191036344 |
Schlagworte
ASJC Scopus Sachgebiete
Schlagwörter
- Description Logics, Automated Deduction, Cardinality Constraints, Concrete Domains