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
2024
Abstract BibTeX Entry DOI
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 article, we complement these investigations by studying the abstract expressive power of both first-order and description logics extended with concrete domains, i.e., we analyze which classes of first-order interpretations can be expressed using these logics, compared to what their counterparts without concrete domains can express. We demonstrate that, under natural conditions on the concrete domain D (which also play a role for decidability), extensions of first-order logic (FOL) or the well-known DL ALC with D share important formal characteristics with FOL, such as the compactness and the Löwenheim-Skolem properties. Nevertheless, these conditions do not ensure that the abstract expressive power of the extensions we consider is contained in that of FOL, though in some cases it is. To be more precise, we show, on the one hand, that unary concrete domains leave the abstract expressive power within FOL if we are allowed to introduce auxiliary predicates. As a by-product, we obtain (semi-)decidability results for some fragments of FOL extended with the concrete domains considered in this article. On the other hand, we show that the ability to express equality between elements of D, another condition employed in the context of showing decidability of ALC(D), is sufficient to push the abstract expressive power of most first-order fragments with concrete domains beyond that of FOL. While for such concrete domains D decidability is retained for ALC(D), we show that the availability of equality in D causes undecidability of the two-variable fragment of FOL(D), although the two-variable fragment of FOL is decidable.
@article{ BaBo-ACR-24, address = {New York, NY, USA}, author = {Franz {Baader} and Filippo {De Bortoli}}, doi = {https://doi.org/10.1145/3699839.3699840}, journal = {SIGAPP Appl. Comput. Rev.}, month = {October}, number = {3}, pages = {5--17}, publisher = {Association for Computing Machinery}, title = {Logics with Concrete Domains: First-Order Properties, Abstract Expressive Power, and (Un)Decidability}, volume = {24}, year = {2024}, }
Abstract BibTeX Entry PDF File DOI
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 both first-order and description logics extended with concrete domains, i.e., we analyze which classes of first-order interpretations can be expressed using these logics, compared to what first-order logic without concrete domains can express. We demonstrate that, under natural conditions on the concrete domain D (which also play a role for decidability), extensions of first-order logic (FOL) or the well-known DL ALC with D share important formal characteristics with FOL, such as the compactness and the Löwenheim-Skolem properties. Nevertheless, their abstract expressive power need not be contained in that of FOL, though in some cases it is. To be more precise, we show, on the one hand, that unary concrete domains leave the abstract expressive power within FOL if we are allowed to introduce auxiliary predicates. On the other hand, we exhibit a class of concrete domains that push the abstract expressive power beyond that of FOL. As a by-product of these investigations, we obtain (semi-)decidability results for some of the logics with concrete domains considered in this paper.
@inproceedings{ BaBo-SAC-24, address = {New York, NY, USA}, author = {Franz {Baader} and Filippo {De Bortoli}}, booktitle = {Proceedings of the 39th {ACM/SIGAPP} Symposium on Applied Computing}, doi = {https://doi.org/10.1145/3605098.3635984}, pages = {754--761}, publisher = {{ACM}}, series = {SAC '24}, title = {{The Abstract Expressive Power of First-Order and Description Logics with Concrete Domains}}, year = {2024}, }
Abstract BibTeX Entry Online Version Extended Version
Concrete domains have been introduced in the context of Description Logics to allow references to qualitative and quantitative values. In particular, the class of \(\omega\)-admissible concrete domains, which includes Allen's interval algebra, the region connection calculus (RCC8), and the rational numbers with ordering and equality, has been shown to yield extensions of \(\mathcal{ALC}\) for which concept satisfiability w.r.t. a general TBox is decidable. In this paper, we present an algorithm based on type elimination and use it to show that deciding the consistency of an \(\mathcal{ALC}(\mathfrak{D})\) ontology is ExpTime-complete if the concrete domain \(\mathfrak{D}\) is \(\omega\)-admissible and its constraint satisfaction problem is decidable in exponential time. While this allows us to reason with concept and role assertions, we also investigate feature assertions \(f(a,c)\) that can specify a constant \(c\) as the value of a feature \(f\) for an individual \(a\). We show that, under conditions satisfied by all known \(\omega\)-admissible domains, we can add feature assertions without affecting the complexity.
@inproceedings{ BaBoKo-DL-24, address = {Bergen, Norway}, author = {Stefan {Borgwardt} and Filippo {De Bortoli} and Patrick {Koopmann}}, booktitle = {Proceedings of the 37th International Workshop on Description Logics (DL'24)}, editor = {Laura {Giordano} and Jean Christoph {Jung} and Ana {Ozaki}}, publisher = {CEUR-WS}, series = {{CEUR} Workshop Proceedings}, title = {{The Precise Complexity of Reasoning in $\mathcal{ALC}$ with $\omega$-Admissible Concrete Domains}}, volume = {3739}, year = {2024}, }
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 10 October 2024, 15:33:22.
Technische Berichte
2023
Abstract BibTeX Entry PDF File DOI
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}}, doi = {https://doi.org/10.25368/2024.240}, 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 10 October 2024, 15:33:34.
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 10 October 2024, 15:33:32.
Talks
- The Expressive Power of Quantitative Extensions of Description Logics - talk given at the m O e X Seminar on April 5, 2024
- Description Logics that Count, and What They Can and Cannot Count - talk given at the 33rd International Workshop on Description Logics (YouTube)
- How to Design Logic-Based Decision Assistants - talk recorded for the ScaDS.AI Living Lab Lecture Series (YouTube)