Filippo De Bortoli

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},
}

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},
}

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},
}

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},
}

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},
}

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},
}

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},
}

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},
}

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},
}

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},
}