Complexity and Expressive Power of Description Logics with Numerical Constraints

Filippo De BortoliFilippo De Bortoli

Filippo De Bortoli
Complexity and Expressive Power of Description Logics with Numerical Constraints
Phd thesis, Technische Universität Dresden, 2025-08-11

Details
Bibtex

KurzfassungAbstract
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.
Weitere Informationen unter:Further Information: Link
Projekt:Project: QuantLA, ScaDS.AI
Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory

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