This extended abstract reports on work that was published in the proceedings of FLAIRS-38. In previous work it was shown that the logic ℒME, which extends the description logic (DL) ℒ with probabilistic conditionals, has domain-lifted inference. In the FLAIRS-38 paper, we extend this result from the base logic ℒ to two logics that can count, the two-variable fragment C2 of first-order logic (FOL) with counting quantifiers, and the DL ℒ, which can formulate expressive counting constraints on role successors and is not a fragment of FOL. As an auxiliary result, we prove that model counting in ℒ can be realized in a domain-liftable way.
only two that are not rich, whereas cardinality restrictions on concepts [16, 17] can constrain the overall number of elements of a concept, e.g., expressing that there are more than 500,000 rich people living in Florida. Description logics ofering such counting features are contained in C2, the two-variable fragment of FOL with counting quantifiers, and are thus decidable [ 18, 19]. In [20, 21] it was recently shown that (extended versions of) model counting in C2 can be realized in a domain-liftable way. We use this result in [13] to prove that C2ME allows for domain-lifted inference. The DL ℒ [22] ofers more expressive counting constraints on role successors, which in general cannot be expressed in C2 or even full FOL [23]. For example, in ℒ we can describe persons that have more rich than non-rich children without specifying how many children of each type the person actually has, and in ℒME we can say that, with a high probability (say .8), rich persons have more rich than non-rich children. We show in [13] that (an extended version of) model counting in ℒ can be realized in a domain-liftable way, and use this result to prove that ℒME allows for domain-lifted inference.
In the following, we briefly sketch the main results obtained in [ 13]. More details can be found in the full paper [13].
Model counting usually asks how many models over a given finite domain Δ a given sentence has. In [13], we consider a slightly extended version of this task, called concept-constrained model counting, where the underlying logic is either C2 or ℒ. Concepts of ℒ and their extensions as well as ℒ TBoxes and their models are defined in [ 22]. For the two-variable fragment C2 of FOL with counting quantifiers, concepts are formulas with one free variable , and their extension consists of those elements of that make the formula true when substituted for . A C2 TBox is a sentence (i.e., formula without free variables) of C2.
Let be a TBox, 1, . . . , concepts, 1, . . . , ℓ non-negative integers, and Δ a finite set. Then ccmc( , 1, . . . , ℓ, 1, . . . , ℓ, Δ) is defined to be the number of models of with domain Δ that satisfy | | = (1 ≤ ≤ ℓ). We say that concept-constrained model counting is domain-liftable if this number can be computed in polynomial time in the size of the input Δ (i.e., where the other inputs of the function ccmc are assumed to be of constant size).
Theorem 1 ([13]). Concept-constrained model counting in C2 and in ℒ is domain-liftable.
For C2, this is an easy consequence of the results on model counting in C2 in [20] (Proposition 4
together with Theorem 4). For ℒ, this is explicitly proved in [13], and constitutes one of the
main results of this paper.
3. The Logics ℒ ME and C2ME
In the following, let ℒ be either ℒ or C2. In the logic ℒME, we consider probabilistic conditionals
(PCs) of the form ( | )[], where , are ℒ concepts and is a rational number. An ℒ knowledge
base = ( , ) consists of an ℒ TBox together with a finite set of PCs. To define the semantics
of such a knowledge base , we follow [
ME is shown to be also domain-liftable in [13].
This semantics for PCs is called aggregating semantics [10]. A knowledge base with at least one model is consistent. Using the fact that concept-constrained model counting for ℒ is domain-liftable Theorem 2 ([13]). Consistency of an ℒ
ME knowledge base for a finite domain Δ can be checked in
Instead of reasoning w.r.t. all models of a consistent knowledge base, we use the maximum entropy
distribution as preferred model. In fact, as pointed out in [
∈ℐΔ ∀ ∈ ℐΔ : () ≥ 0 and () = 0 if ̸|= , has exactly one solution ME [10].
∑︀∈ℐΔ,|= normalization constant.
Instead of solving this optimization problem directly, one usually considers the dual optimization problem, whose solutions represent ME in a compact way. Assume that = {( | )[] | = 1, . . . , } and define the functions (1 ≤ ≤ ) as () := | ∩ | − | |. An application of the Lagrange multiplier method to the above optimization problem then yields ME() = 0 if ̸|= and ME() = 0 11()
· · · () if |= , where the values > 0 are solutions to the equations () 1 1() · · · () = 0, = 1, . . . , , and 0 = ︁( ∑︀∈ℐΔ,|= 1 1() · · · ())︁ − 1 is a on ℐ ity distribution
Δ is defined in [
Since the numbers are solutions of a non-linear optimization problem, they can in general only
be approximated (e.g., using Newton’s method). Following [
∈ Q> 0 of the exact solution () =
0 {︃ 0 1 1() · · · () if |= , else, where the normalization constant 0 is defined analogously to 0.
It is shown in [13] that domain-lifted inference w.r.t. this result is the following theorem. is possible. The main step towards achieving ( √1 1, . . . , √ ) satisfies
|= ( | )[].
Theorem 3. Let , be ℒ concepts, = ( , ) with = {( | )[] | 1 ≤ ≤ } a consistent ℒ knowledge base where = / for natural numbers , , and let the maximum entropy distribution, as defined above. Then we can compute (in time polynomial in |Δ|) a polynomial (1, . . . , ) in indeterminates and with rational coeficients such that := be an approximation of
Employing results from the theory of algebraic field extensions [ 24, 25], this theorem is used in [13] to show the following domain-liftability result.
|= ⊑ can be decided in time polynomial in |Δ|.
base, and a rational approximation of the maximum entropy distribution. Then
Corollary 1. Let , be ℒ concepts, ∈ [
As pointed out in [13], it would also be interesting to know, for a given rational number , whether is larger or smaller than the probability for which were able to show domain-liftability also for this problem. the final version of [ 13], we were able to show that this problem is decidable (see [26]), but it was not clear to us whether deciding the problem can be done in time polynomial in |Δ|. More recently, we |= ( | )[] holds. At the point of submitting
This work was supported by the German Federal Ministry of Education and Research (BMBF, SCADS22B) and the Saxon State Ministry for Science, Culture and Tourism (SMWK) by funding the competence center for Big Data and AI “ScaDS.AI Dresden/Leipzig”.
The author(s) have not employed any Generative AI tools. scription logic ℒ
ME under the principle of maximum entropy, in: F. Calimeri, N. Leone, M. Manna (Eds.), Logics in Artificial Intelligence – 16th European Conference, JELIA 2019, Proceedings, volume 11468 of Lecture Notes in Computer Science, Springer, 2019, pp. 434–449. [4] F. Baader, A. Ecke, G. Kern-Isberner, M. Wilhelm, The complexity of the consistency problem in the probabilistic description logic ℒ
ME, in: A. Herzig, A. Popescu (Eds.), Frontiers of Combining logic ℒ Systems – 12th International Symposium, FroCoS 2019, Proceedings, volume 11715 of Lecture Notes in Computer Science, Springer, 2019, pp. 167–184. doi:10.1007/978-3-030-29007-8\_10. [5] M. Wilhelm, G. Kern-Isberner, Maximum entropy calculations for the probabilistic description
ME, in: C. Lutz, U. Sattler, C. Tinelli, A. Turhan, F. Wolter (Eds.), Description Logic, Theory Combination, and All That – Essays Dedicated to Franz Baader on the Occasion of His 60th Birthday, volume 11560 of Lecture Notes in Computer Science, Springer, 2019, pp. 588–609. [6] T. Lukasiewicz, Expressive probabilistic description logics, Artif. Intell. 172 (2008) 852–883. [7] R. Peñaloza, N. Potyka, Towards statistical reasoning in description logics over finite domains, in: Proceedings of the 11th International Conference on Scalable Uncertainty Management (SUM), volume 10564 of Lecture Notes in Computer Science, Springer, 2017, pp. 280–294. [8] V. Gutiérrez-Basulto, J. C. Jung, C. Lutz, L. Schröder, Probabilistic description logics for subjective uncertainty, J. Artif. Intell. Res. 58 (2017) 1–66. doi:10.1613/JAIR.5222.
[9] J. B. Paris, Common sense and maximum entropy, Synthese 117 (1999) 75–93. [10] G. Kern-Isberner, M. Thimm, Novel semantical approaches to relational probabilistic conditionals, in: F. Lin, U. Sattler, M. Truszczynski (Eds.), Principles of Knowledge Representation and Reasoning: Proceedings of the Twelfth International Conference, KR 2010, AAAI Press, 2010. [11] C. Beierle, M. Finthammer, G. Kern-Isberner, Relational probabilistic conditionals and their instantiations under maximum entropy semantics for first-order knowledge bases, Entropy 17 [12] G. Van den Broeck, N. Taghipour, W. Meert, J. Davis, L. D. Raedt, Lifted probabilistic inference by first-order knowledge compilation, in: T. Walsh (Ed.), IJCAI 2011, Proceedings of the 22nd International Joint Conference on Artificial Intelligence, IJCAI/AAAI, 2011, pp. 2178–2185. doi: 10. 5591/978-1-57735-516-8/IJCAI11-363. [13] F. Baader, A. Claußnitzer, Maximum entropy reasoning via model counting in (description) logics that count, in: The International FLAIRS Conference, Proceedings, 38(1), 2025. doi:https: //doi.org/10.32473/flairs.38.1.138854, an extended version of this paper is available as a technical report [26]. [14] B. Hollunder, W. Nutt, M. Schmidt-Schauß, Subsumption algorithms for concept description languages, in: 9th European Conference on Artificial Intelligence, ECAI 1990, 1990, pp. 348–353. [15] B. Hollunder, F. Baader, Qualifying number restrictions in concept languages, in: J. F. Allen, R. Fikes, E. Sandewall (Eds.), Proceedings of the 2nd International Conference on Principles of Knowledge Representation and Reasoning (KR’91), Morgan Kaufmann, 1991, pp. 335–346. [16] F. Baader, M. Buchheit, B. Hollunder, Cardinality restrictions on concepts, Artif. Intell. 88 (1996) 195–213. doi:10.1016/S0004-3702(96)00010-0. [17] S. Tobies, The complexity of reasoning with cardinality restrictions and nominals in expressive description logics, J. Artif. Intell. Res. 12 (2000) 199–217. doi:10.1613/JAIR.705. [18] E. Grädel, M. Otto, E. Rosen, Two-variable logic with counting is decidable, in: Proceedings, 12th Annual IEEE Symposium on Logic in Computer Science, IEEE Computer Society, 1997, pp. 306–317. doi:10.1109/LICS.1997.614957. [19] L. Pacholski, W. Szwast, L. Tendera, Complexity of two-variable logic with counting, in: Proceedings, 12th Annual IEEE Symposium on Logic in Computer Science, IEEE Computer Society, 1997, pp. 318–327. doi:10.1109/LICS.1997.614958. [20] O. Kuželka, Weighted first-order model counting in the two-variable fragment with counting quantifiers, J. Artif. Intell. Res. 70 (2021) 1281–1307. doi: 10.1613/JAIR.1.12320. [21] J. Tóth, O. Kuželka, Complexity of weighted first-order model counting in the two-variable fragment with counting quantifiers: A bound to beat, in: P. Marquis, M. Ortiz, M. Pagnucco (Eds.), Proceedings of the 21st International Conference on Principles of Knowledge Representation and Reasoning, KR 2024, 2024. doi:10.24963/KR.2024/64. [22] F. Baader, A new description logic with set constraints and cardinality constraints on role successors, in: C. Dixon, M. Finger (Eds.), Frontiers of Combining Systems – 11th International Symposium, FroCoS 2017, Proceedings, volume 10483 of Lecture Notes in Computer Science, Springer, 2017, pp. 43–59. doi:10.1007/978-3-319-66167-4\_3. [23] F. Baader, F. D. Bortoli, On the expressive power of description logics with cardinality constraints on finite and infinite sets, in: A. Herzig, A. Popescu (Eds.), Frontiers of Combining Systems – 12th International Symposium, FroCoS 2019, Proceedings, volume 11715 of Lecture Notes in Computer Science, Springer, 2019, pp. 203–219. doi:10.1007/978-3-030-29007-8\_12. [24] N. Jacobson, Basic Algebra I, W. H. Freeman and Company, 1974. [25] H. Cohen, A Course in Computational Algebraic Number Theory, volume 138 of Graduate Texts in
Mathematics, Springer, 1993. URL: https://www.worldcat.org/oclc/27810276. [26] F. Baader, A. Claußnitzer, Maximum Entropy Reasoning via Model Counting in (Description) Logics that Count (Extended Version), LTCS-Report 25-01, Chair of Automata Theory, Institute of Theoretical Computer Science, Technische Universität Dresden, 2025. URL: https: //lat.inf.tu-dresden.de/research/reports.html. doi:10.25368/2025.015.