We summarize our recent work on extending Description Logics with numeric constraints presented in [1]. We add numeric features to the expressive DL ℒℋℐ with closed predicates, and study reasoning problems that go beyond satisfiability, such as finding models that optimize user-defined objectives. Description Logics (DLs) have proven to be excellent formalisms for describing diferent domains and reasoning about them, but their very limited support for numeric constraints and quantitative reasoning is a significant weakness. In many applications, one would like to be able to refer to integers or real numbers and basic comparisons between them. In expressive DLs like ℒℋℐ, we can describe complex requirements in the form of concept inclusions, such as Project ⊓ ¬{proj1} ⊑ ≥ 3 assignedTo− .Employee, but we cannot reason, e.g., about the number of hours that employees work for a project, or verify that the sum of the monthly salaries of all employees assigned to a project does not exceed the corresponding budget. Standard DLs cannot express this type of quantitative constraints, and adding them is far from easy, and even simple numeric reasoning easily becomes computationally costly, or even undecidable. Overcoming this limitation is a long-standing challenge that has received significant attention since the early days of DL research. The most prominent line of work here is concrete domains [2]. In addition to concepts and roles, we use concrete features such as age, salary, size, etc., to relate objects to values from a domain, like the reals or the integers, for example. A fixed set of predicates over these domains, such as addition and comparisons, can then be used to incorporate numeric constraints into concept descriptions. DLs with concrete domains are very powerful, but this comes at a high computational cost. Strong restrictions must be imposed on the concrete domains to preserve decidability (see [3, 4] and their references). Most works require the so-called -admissibility, which, in a nutshell, guarantees that the infinite systems of constraints that may arise when reasoning about infinite models can be efectively decided. Tight complexity bounds for standard reasoning tasks like concept satisfiability and instance checking have been obtained for expressive DLs with -admissible concrete domains [3, 4]-and even a few isolated results for non--admissible ones [5, 6]-but those works focus on worst-case bounds and generic restrictions that preserve decidability in many domains, rather than on practical usability. In contrast, eforts to support powerful and useful domains by restricting the interaction with the logics, and practicable algorithms for them, have been limited [7, 8]. When DLs are extended with numeric features, many novel and natural reasoning problems arise. For example, if a feature corresponds to a cost, it is natural to minimize it: a company may not only be interested in staying within a given budget when fulfilling certain requirements, but may naturally want to minimize their cost. Given the open domains of DLs, the cost associated with a specific feature may not always be finite, so it is natural to ask whether the KB can be satisfied while guaranteeing that certain cost remains bounded, or below a certain value. Popular reasoning problems such as concept
satisfiability, instance checking, and query answering can all be defined in terms of optimal models. Additionally, one can ask what values certain features might take when other features are optimized. Despite their evident potential, to our knowledge, this kind of numeric reasoning service has not yet been developed for DLs.
This extended abstract summarizes our recent work [
We refer to [10] for standard preliminaries on DLs. We extend DLs with closed predicates [11] by allowing to assign numeric values to concept names and control how some values for the objects compare to aggregated values of its neighbors. For example, assuming an ontology describing a company setting, we want to be able to assign possible salaries to employees within described ranges, and ensure that the sum of yearly salaries of the employees does not exceed a given yearly budget. We introduce features, which assign numeric values to elements, and a new form of concept expressions that locally restricts feature values. Let be a countably infinite set of feature, disjoint from the sets of concept names , role names and individual names . Let + = ∪ {⊤, ⊥} ∪ {{}| ∈ } be the set of basic + concepts. Given a KB , we denote with () and () the sets of features and basic concepts (resp.) occurring in .
Definition 1. Let ℒ be a DL with closed predicates. A feature annotation is a partial function from + × to finite discrete subsets of the non-negative rationals Q+ ∪ {0}. We call the set = (, ) the domain of feature for . A neighborhood restriction takes the form 0 + 1 ∑︁ 1[1.1] + · · · + ∑︁ [.] ∘ , (* ) where ∘ ∈ { <, ≤ , ≥ , >}, 1, . . . , are roles, 1, . . . , are concepts, , 1, . . . , are features, and , 1, . . . , are non-negative rational numbers. Concepts in ℒNF are defined as for ℒ, but also allowing neighborhood restrictions. A KB is defined as a 4-tuple = ( , Σ , , ), where ( , Σ , ) is an ℒNF KB with closed predicates and is a feature annotation function.
The feature annotation function determines the set of values that objects participating in a basic concept can take as the value of feature . For instance, (ExecEmpl, salary ) = [3.5, 5.5, +0.1] indicates that executive employees can have their salary -value between 3.5k and 5.5k, with increases of 100€. In our case, we restrict our attention to sets that consist of finitely many, non-negative rational values. Note that is a partial function, as for instance we may not want to prescribe values for (Office, salary ), since ofices have no salary.
To define the semantics of our formalism, we extended standard interpretation functions to features by requiring that an interpretation function · ℐ assigns to every feature ∈ a partial function ℐ from ∆ ℐ to non-negative rational values. The semantics of a neighborhood restriction (* ) is now straightforward: at a domain element, we compare the feature value of multiplied by the weight with the weighted sum of the feature values of the relevant neighbors, i.e.
(0 + 1 ∑︁ 1[1.1] + · · ·
+ ∑︁ [.] ∘ )ℐ = { ∈ ∆ ℐ : (︀ 0 +
ℐ (′))︀ ∘ ℐ ()} ∑︁ (,′)∈ℐ,′∈ℐ, ℐ(′) def.,1≤ ≤ Satisfaction of axioms in ℐ involving the new concept constructor is defined as usual. Definition 2. Given a KB = ( , Σ , , ), an interpretation ℐ is -suitable, if for each ∈ ∆ ℐ , each feature ∈ (), and each basic concept ∈ + () with ∈ ℐ and (, ) defined, we have that ℐ () ∈ (, ). We say that ℐ satisfies , and call ℐ a model of , if (i) ℐ is -suitable and (ii) ℐ satisfies ( , Σ , ).
Standard reasoning tasks can be easily defined in our setting. By adapting the well-known mosaic technique [12, 13] for ℒℋℐ with closed predicates [9], we provide tight complexity results. Roughly speaking, the core idea of the mosaic technique is to succinctly represent small fragments of models that serve as variables of a system of inequalities. A solution to the system consists of a set of fragments that can be successfully plugged together into a model. Given a KB, to accommodate our numeric features and constraints, we extend the model fragments of [9] with vectors called feature types, where the -th position corresponds to the value of the feature or is undefined. Via the feature types, we ensure that when constructing the model, we respect the feature annotations of and satisfy the axioms with neighborhood constraints.
Theorem 1. Satisfiability of ℒℋℐNF KBs with closed predicates is NExpTime-complete.
Our formalism supports other novel reasoning problems that arise naturally by restricting the models of KBs to those that are optimal w.r.t. some given objective. Given a KB , a cost function for is an expression of the form = 0 + ∑︀
=1 · [], where 0, ∈ Q+ are weights, ∈ (), and ∈ + (), for all 1 ≤ ≤ . Given a concrete interpretation ℐ and a cost function , the value of ℐ w.r.t. , denoted v (ℐ) is defined as
(ℐ) = 0 + ∑︁ ∑︁
ℐ ().
=1 ∈ℐ s.t. ℐ() def.
Definition 3. Given = ( , Σ , , ) and a cost function , an interpretation ℐ is an optimal model of w.r.t. if: (i) ℐ |= , (ii) (ℐ) is finite, and (iii) there exists no such that |= and ( ) ≤ (ℐ).
Standard reasoning tasks such as KB satisfiability, concept satisfiability, and instance checking can be easily transferred to the setting of optimal models. Furthermore, we can define ad hoc reasoning tasks in which we check if a specific requirement over feature values is fulfilled. We call cost query an expression of the form ∘ , where is a cost function, is a non-negative rational, and ∘ ∈ { <, ≤ , =, ≥ , >}. We say that a cost query is true in an interpretation ℐ, in symbols ℐ |= , if (ℐ) ∘ is true. The reasoning tasks of brave and cautious query answering can be easily defined for cost queries. Given a cost query and a KB , we say that is bravely entailed by if there exists a model ℐ of such that ℐ |= . While, we say that is cautiously entailed by if ℐ |= , for all models ℐ of . Theorem 2. In ℒℋℐNF, KB satisfiability w.r.t. optimal models is NExpTime-complete. Concept satisfiability, instance checking, cautious and brave cost query answering w.r.t. optimal models are ExpTimeNP-complete.
We can analogously define optimal models as those that maximize the value of .
Our logic has a form of concrete domains [
This work was partially supported by the Austrian Science Fund (FWF) projects PIN8884924, P30873 and 10.55776/COE12.
The authors have not employed any Generative AI tools. [9] S. Lukumbuzya, M. Ortiz, M. Šimkus, Datalog Rewritability and Data Complexity of ℒℋℐ with Closed Predicates, Artif. Intell. 330 (2024) 104099. doi:10.1016/J.ARTINT.2024.104099. [10] F. Baader, I. Horrocks, C. Lutz, U. Sattler, An Introduction to Description Logic, Cambridge
University Press, 2017. [11] C. Lutz, I. Seylan, F. Wolter, Ontology-Based Data Access with Closed Predicates is Inherently Intractable(Sometimes), in: Proceedings of the 23rd International Joint Conference on Artificial Intelligence (IJCAI), IJCAI/AAAI, 2013, pp. 1024–1030. [12] I. Pratt-Hartmann, Complexity of the Two-Variable Fragment with Counting Quantifiers, Journal of Logic, Language and Information 14 (2005) 369–395. doi:10.1007/s10849-005-5791-1. [13] C. Lutz, U. Sattler, L. Tendera, The Complexity of Finite Model Reasoning in Description Logics,
Inf. Comput. 199 (2005) 132–171. doi:10.1016/j.ic.2004.11.002. [14] C. Lutz, M. Milicic, A Tableau Algorithm for Description Logics with Concrete Domains and
General TBoxes, J. Autom. Reason. 38 (2007) 227–259. doi:10.1007/S10817-006-9049-7. [15] F. Baader, F. De Bortoli, Description logics that count, and what they can and cannot count (extended abstract), in: S. Borgwardt, T. Meyer (Eds.), Proceedings of the 33rd International Workshop on Description Logics (DL), co-located with the 17th International Conference on Principles of Knowledge Representation and Reasoning (KR), volume 2663 of CEUR Workshop Proceedings, CEUR-WS.org, 2020. URL: https://ceur-ws.org/Vol-2663/abstract-2.pdf. [16] B. Bednarczyk, O. Fiuk, Presburger Büchi Tree Automata with Applications to Logics with Expressive Counting, in: A. Ciabattoni, E. Pimentel, R. J. G. B. de Queiroz (Eds.), Proceedings of the 28th International Workshop on Logic, Language, Information, and Computation (WoLLIC), volume 13468 of Lecture Notes in Computer Science, Springer, 2022, pp. 295–308. doi:10.1007/ 978-3-031-15298-6\_19. [17] P. A. Bonatti, C. Lutz, F. Wolter, The Complexity of Circumscription in DLs, J. Artif. Intell. Res. 35 (2009) 717–773. URL: https://doi.org/10.1613/jair.2763. doi:10.1613/JAIR.2763. [18] M. Bienvenu, C. Bourgaux, R. Jean, Cost-Based Semantics for Querying Inconsistent Weighted Knowledge Bases, in: P. Marquis, M. Ortiz, M. Pagnucco (Eds.), Proceedings of the 21st International Conference on Principles of Knowledge Representation and Reasoning, KR, 2024. doi:10.24963/ KR.2024/16.