- Titel
- The Expressive Power of Description Logics with Numerical Constraints over Restricted Classes of Models
- Untertitel
- (Extended Version)
- Zitierfähige Url:
- https://nbn-resolving.org/urn:nbn:de:bsz:14-qucosa2-978151
- Schriftenreihe
- LTCS-Report
- Bandnummer
- 25-03
- Erstveröffentlichung
- 2025
- DOI
- https://doi.org/10.25368/2025.126
- Abstract (EN)
- This is an extended version of an article accepted at the 15th International Symposium on Frontiers of Combining Systems (Fro-CoS 2025).
- For Description Logics (DLs), different approaches for extending the expressive power using numerical constraints have been introduced. Here, we consider the logic ALCSCC, which can state powerful numerical constraints on the number of role successors satisfying certain properties, and logics of the form ALC(D), in which individuals can be assigned numerical or other concrete values, which can be compared using predefined predicates of D. Instead of investigating the complexity of reasoning in these logics, we are interested in characterizing their expressive power. We improve on our previous work in this direction in several respects. For ALCSCC, we develop a method that can deal with the finitely branching interpretations considered in the original paper on this logic, rather than moving to the variant ALCSCC^∞, where arbitrary interpretations are allowed. The main idea is to employ, in the proof of the characterization, locality properties of first-order logic over certain restricted classes of models (such as finite and finitely branching models) rather than compactness, which does not hold in the finitely branching case. For logics of the form ALC(D), we consider a notion of expressive power that takes the concrete values assigned to individuals into account, rather than the abstract expressive power investigated in our previous work. The characterization of the expressive power of ALC(D) obtained this way works not only for arbitrary interpretations, but also for finite and finitely branching ones.
- Freie Schlagwörter (EN)
- Description Logics, Concrete Domains, Cardinality constraints, Expressive power, Bisimulation, Locality
- Klassifikation (DDC)
- 004
- Klassifikation (RVK)
- ST 136
- Publizierende Institution
- Technische Universität Dresden, Fakultät Informatik, Institut für Theoretische Informatik, Professur für Automatentheorie
- URN Qucosa
- urn:nbn:de:bsz:14-qucosa2-978151
- Veröffentlichungsdatum Qucosa
- 07.07.2025
- Dokumenttyp
- Bericht
- Sprache des Dokumentes
- Englisch
- Lizenz / Rechtehinweis
CC BY 4.0