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

Franz BaaderFranz Baader, Filippo De BortoliFilippo De Bortoli

ISBN: 978-3-032-04167-8
ISSN: 0302-9743
DOI Link

Franz Baader, Filippo De Bortoli
The Expressive Power of Description Logics with Numerical Constraints over Restricted Classes of Models
In René Thiemann, Christoph Weidenbach, eds., Frontiers of Combining Systems: 15th International Symposium, FroCoS 2025, Reykjavik, Iceland, September 29 – October 1, 2025, Proceedings, volume 15979 of Lecture Notes in Artificial Intelligence, 22-39, September 2025. Springer

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.
Projekt:Project: CPEC, ScaDS.AI
Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory

The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-032-04167-8_2.

@inproceedings{BB2025,
  author    = {Franz Baader and Filippo De Bortoli},
  title     = {The Expressive Power of Description Logics with Numerical
               Constraints over Restricted Classes of Models},
  editor    = {Ren{\'{e}} Thiemann and Christoph Weidenbach},
  booktitle = {Frontiers of Combining Systems: 15th International Symposium,
               {FroCoS} 2025, Reykjavik, Iceland, September 29 {\textendash}
               October 1, 2025, Proceedings},
  series    = {Lecture Notes in Artificial Intelligence},
  volume    = {15979},
  publisher = {Springer},
  year      = {2025},
  month     = {September},
  pages     = {22-39},
  doi       = {10.1007/978-3-032-04167-8_2}
}