Datei:BaBoBoKo-CADE-25.pdf

2026-02-14T10:26:39Z

Filippo De Bortoli:

Phdthesis3024

2026-02-13T16:45:01Z

Filippo De Bortoli:

{{Publikation Erster Autor
|ErsterAutorVorname=Filippo
|ErsterAutorNachname=De Bortoli
}}
{{Phdthesis
|Title=Complexity and Expressive Power of Description Logics with Numerical Constraints
|Instructor=Prof. Dr.-Ing. Franz Baader
|Date=2025-08-11
|School=Technische Universität Dresden
}}
{{Publikation Details
|Abstract=Standard Description Logics (DLs) can encode numerical aspects of domain-specific knowledge using number restrictions and concrete domains. The former are used to compare the number of role successors of an individual described by a given concept with a fixed natural number. The latter are used to assign concrete values (e.g. numbers) to an individual, which can be referenced using features and constrained using predefined predicates (e.g. numerical comparisons). Recently, number restrictions were extended using the quantifier-free fragment of Boolean Algebra with Presburger Arithmetic (QFBAPA). In the resulting DL, called ALCSCC, reasoning is as complex as with number restrictions, in spite of the increase in expressive power. In this thesis, we develop a method to study the expressive power of ALCSCC, which has a semantics based on finitely branching interpretations, using the locality properties satisfied by first-order logic (FOL) over certain restricted classes of models (such as finite and finitely branching models) rather than compactness, which fails in the finitely branching case. We thus generalize our earlier work, in which we introduced a variant ALCSCC∞ defined over arbitrary interpretations and analyzed its expressive power using a bisimulation-based characterization. Early research in DL considered cardinality restrictions (CRs) that compare the number of individuals described by a concept with a fixed natural number. Similarly to number restrictions, CRs have been generalized using QFBAPA, obtaining extended CRs defined over finite interpretations, increasing the expressive power without increasing the complexity of reasoning. We prove that the complexity of reasoning with extended CRs over arbitrary interpretations is the same w.r.t. the finite variant, and lift the notion of bisimulation used for ALCSCC∞ to study their expressive power, with additional results based on 0–1 laws and model-theoretic properties used to differentiate the expressive power of different logics. We characterize the subsets of these logics that are FOL-definable and prove that neither of the logics is fully FOL-definable. It is known that 𝜔-admissible concrete domains 𝔇, such as Allen’s interval algebra, the region connection calculus RCC8, and the rational numbers with ordering and equality, yield decidable extensions ALC(𝔇) of ALC. If the constraint satisfaction problem (CSP) of 𝔇 is decidable in exponential time, we show that reasoning in ALC(𝔇) is ExpTime-complete. We then look at two notions of expressive power for logics with concrete domains. One enables the comparison of logics with (possibly different) concrete domains, and we analyze it by using a bisimulation that accounts for the presence of feature values and using a locality-based method as in the case of ALCSCC. The other, called abstract expressive power, looks at the classes of first-order interpretations that can be expressed using extensions of FOL and DLs with concrete domains, compared to what their counterparts without concrete domains can express. If 𝔇 only has unary predicates, the abstract expressive power remains within FOL if we are allowed to introduce auxiliary symbols, and we obtain decidability results for some fragments of FOL extended with 𝔇 as a by-product. If we can state equality between elements of 𝔇, on the other hand, the abstract expressive power of most first-order fragments extended by 𝔇 is beyond that of FOL, and the two-variable fragment with concrete domains becomes undecidable. We find sufficient conditions on 𝔇 such that these extensions satisfy first-order properties such as compactness. Finally, we study ALCOSCC(𝔇), a combination of ALCSCC and concrete domains where we can additionally refer to specific individuals by name and use so-called feature roles. We show that the consistency problem for this DL is ExpTime-complete, assuming that the CSP of 𝔇 is decidable in exponential time. We show that many natural extensions to this DL, including a tighter integration of the concrete domain and number restrictions, lead to undecidability.
|Download=De Bortoli-Dissertation.pdf
|Link=https://nbn-resolving.org/urn:nbn:de:bsz:14-qucosa2-989517
|Projekt=QuantLA, ScaDS.AI
|Forschungsgruppe=Automatentheorie
|BibTex=@thesis{DeBortoli-Diss-2025,
address = {Dresden, Germany},
author = {Filippo {De Bortoli} },
school = {Technische Universit\"{a}t Dresden},
title = {Complexity and Expressive Power of Description Logics with Numerical Constraints},
type = {Doctoral Thesis},
year = {2025},
}
}}
{{Forschungsgebiet Auswahl
|Forschungsgebiet=Beschreibungslogiken
}}

2026-02-13T16:40:32Z

Filippo De Bortoli:

Datei:BaBo-FroCoS-25.pdf

2026-02-13T16:38:36Z

Filippo De Bortoli:

Inproceedings3457

2026-01-22T13:46:52Z

Filippo De Bortoli: Die Seite wurde neu angelegt: „{{Publikation Erster Autor |ErsterAutorVorname=Franz |ErsterAutorNachname=Baader |FurtherAuthors=Stefan Borgwardt; Filippo De Bortoli; Patrick Koopmann }} {{Inproceedings |Referiert=1 |Title=Concrete Domains Meet Expressive Cardinality Restrictions in Description Logics (Extended Abstract) |To appear=0 |Year=2025 |Month=September |Booktitle=Proceedings of the 38th International Workshop on Description Logics (DL'25) |Pages=5 |Publisher=CEUR-WS.org |Editor…“

2024-10-10T13:48:44Z

Filippo De Bortoli:

{{Publikation Erster Autor
|ErsterAutorVorname=Franz
|ErsterAutorNachname=Baader
|FurtherAuthors=Filippo De Bortoli
}}
{{Techreport
|Title=On the Complexity and Expressiveness of Description Logics with Counting
|Year=2019
|Month=Dezember
|Institution=Chair of Automata Theory, Institute of Theoretical Computer Science, Technische Universität Dresden
|Archivierungsnummer=LTCS-Report 19-09
}}
{{Publikation Details
|Abstract=Simple counting quantifiers that can be used to compare the number of role successors of an individual or the cardinality of a concept with a fixed natural number have been employed in Description Logics (DLs) for more than two decades under the respective names of number restrictions and cardinality restrictions on concepts. Recently, we have considerably extended the expressivity of such quantifiers by allowing to impose set and cardinality constraints formulated in the quantifier-free fragment of Boolean Algebra with Presburger Arithmetic (QFBAPA) on sets of role successors and concepts, respectively. We were able to prove that this extension does not increase the complexity of reasoning. In the present paper, we investigate the expressive power of the DLs obtained this way, using appropriate bisimulation characterizations and 0–1 laws as tools for distinguishing the expressiveness of different logics. In particular, we show that, in contrast to most classical DLs, these logics are no longer expressible in first-order predicate logic (FOL), and we characterize their first-order fragments. In most of our previous work on DLs with QFBAPA-based set and cardinality constraints we have employed finiteness restrictions on interpretations to ensure that the obtained sets are finite. Here we dispense with these restrictions to make the comparison with classical DLs, where one usually considers arbitrary models rather than finite ones, easier. It turns out that doing so does not change the complexity of reasoning.
|Link=https://tu-dresden.de/inf/lat/reports#BaBo-LTCS-19-09
|Projekt=QuantLA
|Forschungsgruppe=Automatentheorie
|BibTex=@techreport{ BaBo-LTCS-19-09,
address = {Dresden, Germany},
author = {Franz {Baader} and Filippo {De Bortoli} },
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-19-09} },
number = {19-09},
title = { {On the Complexity and Expressiveness of Description Logics with Counting} },
type = {LTCS-Report},
year = {2019},
}
}}

Inproceedings3317

2024-10-10T13:48:14Z

Filippo De Bortoli:

{{Publikation Erster Autor
|ErsterAutorVorname=Franz
|ErsterAutorNachname=Baader
|FurtherAuthors=Filippo De Bortoli
}}
{{Inproceedings
|Referiert=1
|Title=Description Logics that Count, and What They Can and Cannot Count (Extended Abstract)
|To appear=0
|Year=2020
|Booktitle=Proceedings of the 33rd International Workshop on Description Logics (DL'20)
|Publisher=CEUR-WS
|Editor=Stefan Borgwardt, Thomas Meyer
|Series=CEUR Workshop Proceedings
|Volume=2663
}}
{{Publikation Details
|Abstract=Simple counting quantifiers that can be used to compare the number of role successors of an individual or the cardinality of a concept with a fixed natural number have been employed in Description Logics (DLs) for more than two decades under the respective names of number restrictions and cardinality restriction on concepts. Recently, we have considerably extended the expressivity of such quantifiers by allowing to impose set and cardinality constraints formulated in the quantifier-free fragment of Boolean Algebra with Presburger Arithmetic (QFBAPA) on sets of role successors and concepts, respectively. We were able to prove that this extension does not increase the complexity of reasoning. In the present paper, we investigate the expressive power of the DLs obtained this way, using appropriate bisimulation characterizations and 0-1 laws as tools for distinguishing the expressiveness of different logics. In particular, we show that, in contrast to most classical DLs, these logics are no longer expressible in first-order predicate logic (FOL), and we characterize their first-order fragments. In most of our previous work on DLs with QFBAPA-based set and cardinality constraints we have employed finiteness restrictions on interpretations to ensure that the obtained sets are finite. Here we dispense with these restrictions to make the comparison with classical DLs, where one usually considers arbitrary models rather than finite ones, easier. It turns out that doing so does not change the complexity of reasoning.
|Link=https://lat.inf.tu-dresden.de/research/papers/2020/BaDeBo-DL-20.pdf
|Projekt=QuantLA
|Forschungsgruppe=Automatentheorie
|BibTex=@inproceedings{ BaDeBo-DL-20,
address = {Online},
author = {Franz {Baader} and Filippo {De Bortoli} },
booktitle = {Proceedings of the 33rd International Workshop on Description Logics (DL'20)},
editor = {Stefan {Borgwardt} and Thomas {Meyer} },
publisher = {CEUR-WS},
series = {CEUR Workshop Proceedings},
title = {Description Logics that Count, and What They Can and Cannot Count (Extended Abstract)},
volume = {2663},
year = {2020},
}
}}