The Expressive Power of Description Logics with Numerical Constraints over Restricted Classes of Models

Filippo De BortoliFilippo De Bortoli

Filippo De Bortoli
The Expressive Power of Description Logics with Numerical Constraints over Restricted Classes of Models
Talk, September 2025

Details
Bibtex

KurzfassungAbstract
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.
Bemerkung: Note: Talk given at the 15th International Symposium on Frontiers of Combining Systems (FroCoS 2025).
Weitere Informationen unter:Further Information: Link
Projekt:Project: CPEC, ScaDS.AI
Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory

@misc{B2025,
  author = {Filippo De Bortoli},
  title  = {The Expressive Power of Description Logics with Numerical
            Constraints over Restricted Classes of Models},
  year   = {2025},
  month  = {September}
}