Filippo De Bortoli
Wissenschaftlicher Mitarbeiter
NameHerr Filippo De Bortoli M.Sc.
Eine verschlüsselte E-Mail über das SecureMail-Portal versenden (nur für TUD-externe Personen).
Besuchsadresse:
Andreas-Pfitzmann-Bau, Raum 3030 Nöthnitzer Straße 46
01187 Dresden
I am a doctoral student at the Chair of Automata Theory of TU Dresden and a team member of the Center for Scalable Data Analysis and Artificial Intelligence (ScaDS.AI) of TU Dresden and Uni Leipzig. My current research project, mainly supervised by Franz Baader, focuses on the characterization of the expressive power of Description Logics extended with Presburger-like cardinality constraints and concrete domain constructors. I have been a member of the Quantitative Logics and Automata (QuantLA) research training group from May 2019 to June 2022.
Links
- ORCiD
- Scopus
- dblp
- Google Scholar
- ResearchGate
- Semantic Scholar
- MathSciNet
- zbMATH
- International Center for Computational Logic TU Dresden
- Forschungsinformationssystem (FIS) TU Dresden
Veröffentlichungen
2023
Abstract BibTeX Entry PDF File Online version
Concrete domains have been introduced in Description Logic (DL) to enable reference to concrete objects (such as numbers) and predefined predicates on these objects (such as numerical comparisons) when defining concepts. The primary research goal in this context was to find restrictions on the concrete domain such that its integration into certain DLs preserves decidability or tractability. In this paper, we investigate the abstract expressive power of logics extended with concrete domains, namely which classes of first-order interpretations can be expressed using these logics. In the first part of the paper, we show that, under natural conditions on the concrete domain \(\mathfrak{D}\) (which also play a role for decidability), extensions of first-order logic (\(\texttt{FOL}\)) or \(\mathcal{ALC}\) with \(\mathfrak{D}\) share important formal properties with \(\texttt{FOL}\), such as the compactness and the Löwenheim-Skolem property. Nevertheless, their abstract expressive power need not be contained in that of \(\texttt{FOL}\). In the second part of the paper, we investigate whether finitely bounded homogeneous structures, which preserve decidability if employed as concrete domains, can be used to express certain universal first-order sentences, which then could be added to DL knowledge bases without destroying decidability. We show that this requires rather strong conditions on said sentences or an extended scheme for integrating the concrete domain that leads to undecidability.
@inproceedings{ BaBo-DL-23, address = {Rhodes, Greece}, author = {Franz {Baader} and Filippo {De Bortoli}}, booktitle = {Proceedings of the 36th International Workshop on Description Logics (DL'23)}, editor = {Oliver {Kutz} and Ana {Ozaki}}, publisher = {CEUR-WS}, series = {CEUR Workshop Proceedings}, title = {{On the Abstract Expressive Power of Description Logics with Concrete Domains}}, volume = {3515}, year = {2023}, }
2020
Abstract BibTeX Entry DOI
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.
@inproceedings{ BaBo-ANDREI60-20, author = {Franz {Baader} and Filippo {De Bortoli}}, booktitle = {ANDREI-60. Automated New-era Deductive Reasoning Event in Iberia}, doi = {https://doi.org/10.29007/ltzn}, editor = {Laura {Kovacs} and Konstantin {Korovin} and Giles {Reger}}, pages = {1--25}, publisher = {EasyChair}, series = {EPiC Series in Computing}, title = {Description Logics That Count, and What They Can and Cannot Count}, volume = {68}, year = {2020}, }
Abstract BibTeX Entry PDF File
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.
@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}, }
2019
Abstract BibTeX Entry PDF File DOI (The final publication is available at link.springer.com) ©Springer Nature Switzerland AG 2019
In recent work we have extended the description logic (DL) by means of more expressive number restrictions using numerical and set constraints stated in the quantifier-free fragment of Boolean Algebra with Presburger Arithmetic (QFBAPA). It has been shown that reasoning in the resulting DL, called \(\mathcal{ALCSCC}\), is PSpace-complete without a TBox and ExpTime-complete w.r.t. a general TBox. The semantics of \(\mathcal{ALCSCC}\) is defined in terms of finitely branching interpretations, that is, interpretations where every element has only finitely many role successors. This condition was needed since QFBAPA considers only finite sets. In this paper, we first introduce a variant of \(\mathcal{ALCSCC}\), called \(\mathcal{ALCSCC}^\infty\), in which we lift this requirement (inexpressible in first-order logic) and show that the complexity results for \(\mathcal{ALCSCC}\) mentioned above are preserved. Nevertheless, like \(\mathcal{ALCSCC}\), \(\mathcal{ALCSCC}^\infty\) is not a fragment of first-order logic. The main contribution of this paper is to give a characterization of the first-order fragment of \(\mathcal{ALCSCC}^\infty\). The most important tool used in the proof of this result is a notion of bisimulation that characterizes this fragment.
@inproceedings{ BaDeBo-FroCoS19, author = {Franz {Baader} and Filippo {De Bortoli}}, booktitle = {Proc. of the 12th International Symposium on Frontiers of Combining Systems ({FroCoS} 2019)}, doi = {https://doi.org/10.1007/978-3-030-29007-8_12}, editor = {Andreas {Herzig} and Andrei {Popescu}}, pages = {203--219}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, title = {On the Expressive Power of Description Logics with Cardinality Constraints on Finite and Infinite Sets}, volume = {11715}, year = {2019}, }
Generated 28 March 2024, 13:25:06.
Technische Berichte
2023
Abstract BibTeX Entry PDF File
Concrete domains have been introduced in Description Logic (DL) to enable reference to concrete objects (such as numbers) and predefined predicates on these objects (such as numerical comparisons) when defining concepts. The primary research goal in this context was to find restrictions on the concrete domain such that its integration into certain DLs preserves decidability or tractability. In this paper, we investigate the abstract expressive power of logics extended with concrete domains, namely which classes of first-order interpretations can be expressed using these logics. In the first part of the paper, we show that, under natural conditions on the concrete domain \(\mathfrak{D}\) (which also play a role for decidability), extensions of first-order logic (\(\texttt{FOL}\)) or \(\mathcal{ALC}\) with \(\mathfrak{D}\) share important formal properties with \(\texttt{FOL}\), such as the compactness and the Löwenheim-Skolem property. Nevertheless, their abstract expressive power need not be contained in that of \(\texttt{FOL}\). In the second part of the paper, we investigate whether finitely bounded homogeneous structures, which preserve decidability if employed as concrete domains, can be used to express certain universal first-order sentences, which then could be added to DL knowledge bases without destroying decidability. We show that this requires rather strong conditions on said sentences or an extended scheme for integrating the concrete domain that leads to undecidability.
@techreport{ BaBo-LTCS-23-02, 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-23-02}}, number = {23-02}, title = {{On the Abstract Expressive Power of Description Logics with Concrete Domains (Extended Version)}}, type = {LTCS-Report}, year = {2023}, }
2019
Abstract BibTeX Entry PDF File DOI
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.
@techreport{ BaBo-LTCS-19-09, address = {Dresden, Germany}, author = {Franz {Baader} and Filippo {De Bortoli}}, doi = {https://doi.org/10.25368/2022.258}, 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}, }
Generated 28 March 2024, 13:25:16.
Abschlussarbeiten
2019
Abstract BibTeX Entry PDF File Publication
Recent research in the field of Description Logic (DL) investigated the complexity of the satisfiability problem for description logics that are obtained by enriching the well-known DL ALCQ with more complex set and cardinality constraints over role successors. The algorithms that have been proposed so far, despite providing worst-case optimal decision procedures for the concept satisfiability problem (both without and with a terminology) lack the efficiency needed to obtain usable implementations. In particular, the algorithm for the case without terminology is non-deterministic and the one for the case with a terminology is also best-case exponential. The goal of this thesis is to use well-established techniques from the field of numerical optimization, such as column generation, in order to obtain more practical algorithms. As a starting point, efficient approaches for dealing with counting quantifiers over unary predicates based on SAT-based column generation should be considered.
@thesis{ DeBo-Mas-19, address = {Dresden, Germany}, author = {Filippo {De Bortoli}}, school = {Technische Universit\"{a}t Dresden}, title = {Integrating Reasoning Services for Description Logics with Cardinality Constraints with Numerical Optimization Techniques}, type = {Master's Thesis}, year = {2019}, }
Generated 28 March 2024, 13:25:19.