Congratulations! Filippo De Bortoli won the Best Student Paper Award for the paper “The Expressive Power of Description Logics with Numerical Constraints over Restricted Classes of Models”. The award was presented to him at the 15th International Symposium on Frontiers of Combining Systems (FroCoS 2025). The conference took place from September 29 – October 1, 2025 in Reykjavík, Iceland. The paper was co-authored by ScaDS.AI Dresden/Leipzig PI Prof. Franz Baader.

Abstract

For Description Logics (DLs), different approaches for extending the expressive power using numerical constraints have been introduced. Here, the authors 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, the authors are interested in characterizing their expressive power. They improve on their previous work in this direction in several respects.

For ALCSCC, they 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), they consider a notion of expressive power that takes the concrete values assigned to individuals into account, rather than the abstract expressive power investigated in their 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.

Find the paper here.

FroCoS

The International Symposium on Frontiers of Combining Systems (FroCoS) is the main international event for research on the development of techniques and methods for the combination and integration of formal systems, their modularization and analysis. It was hosted at Reykjavik University by the Icelandic Centre of Excellence in Theoretical Computer Science. It was sponsored by Inria and the Artificial Intelligence Journal.