The Expressive Power of Description Logics with Numerical Constraints over Restricted Classes of Models (Extended Version)

Franz BaaderFranz Baader, Filippo De BortoliFilippo De Bortoli

Franz Baader, Filippo De Bortoli
The Expressive Power of Description Logics with Numerical Constraints over Restricted Classes of Models (Extended Version)
Technical Report, Chair of Automata Theory, Institute of Theoretical Computer Science, Technische Universität Dresden, volume LTCS-25-03, 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.
Weitere Informationen unter:Further Information: Link
Projekt:Project: CPEC, ScaDS.AI
Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory

@techreport{ BaBo-LTCS-25-03,
      address = {Dresden, Germany},
      author = {Franz {Baader} and Filippo {De Bortoli}},
      doi = {https://doi.org/10.25368/2025.126},
      institution = {Chair of Automata Theory, Institute of Theoretical Computer Science, Technische Universit{\"a}t Dresden},
      note = {\url{https://tu-dresden.de/inf/lat/reports#BaBo-LTCS-25-03}},
      number = {25-03},
      title = {{The Expressive Power of Description Logics with Numerical Constraints over Restricted Classes of Models (Extended Version)}},
      type = {LTCS-Report},
      year = {2025},
    }

,

     number = {25-03},
     title = { {The Expressive Power of Description Logics with Numerical Constraints over Restricted Classes of Models (Extended Version)} },
     type = {LTCS-Report},
     year = {2025},
   }

}}