{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,28]],"date-time":"2026-07-28T07:26:23Z","timestamp":1785223583468,"version":"3.55.0"},"publisher-location":"Cham","reference-count":31,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783031999833","type":"print"},{"value":"9783031999840","type":"electronic"}],"license":[{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T00:00:00Z","timestamp":1753833600000},"content-version":"vor","delay-in-days":210,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2025]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    Standard Description Logics (DLs) can encode quantitative aspects of an application domain through either\n                    <jats:italic>number restrictions<\/jats:italic>\n                    , which constrain the number of individuals that are\u00a0in a certain relationship with an individual, or\n                    <jats:italic>concrete domains<\/jats:italic>\n                    , which can be used to assign concrete values to individuals using so-called features. These two mechanisms have been extended towards very expressive DLs, for which reasoning nevertheless remains decidable. Number restrictions have been generalized to\u00a0more powerful comparisons of sets of role successors in\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$\\mathcal {ALCSCC}$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mi>ALCSCC<\/mml:mi>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    ,\u00a0while the comparison of feature values of different individuals in\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$\\mathcal {ALC} (\\mathfrak {D})$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mi>ALC<\/mml:mi>\n                            <mml:mo>(<\/mml:mo>\n                            <mml:mi>D<\/mml:mi>\n                            <mml:mo>)<\/mml:mo>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    has been studied in the context of\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$\\omega $$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mi>\u03c9<\/mml:mi>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    -admissible concrete domains\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$\\mathfrak {D}$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mi>D<\/mml:mi>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    . In this paper, we combine both formalisms\u00a0and investigate the complexity of reasoning in the thus obtained\u00a0DL\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$\\mathcal {ALCOSCC}(\\mathfrak {D})$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mi>ALCOSCC<\/mml:mi>\n                            <mml:mo>(<\/mml:mo>\n                            <mml:mi>D<\/mml:mi>\n                            <mml:mo>)<\/mml:mo>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    , which additionally includes the ability to refer\u00a0to specific individuals by name. We show that, in spite of its\u00a0high expressivity, the consistency problem for this DL\u00a0is\n                    <jats:sc>ExpTime<\/jats:sc>\n                    -complete, assuming that the constraint satisfaction problem of\u00a0\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$\\mathfrak {D}$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mi>D<\/mml:mi>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    is also decidable in exponential time. It is thus\u00a0not higher than the complexity of the basic DL\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$\\mathcal {ALC}$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mi>ALC<\/mml:mi>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    . At the same time, we show that many natural extensions to this DL, including a tighter integration of the concrete domain and number restrictions, lead\u00a0to undecidability.\n                  <\/jats:p>","DOI":"10.1007\/978-3-031-99984-0_35","type":"book-chapter","created":{"date-parts":[[2025,7,29]],"date-time":"2025-07-29T11:48:00Z","timestamp":1753789680000},"page":"676-695","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Concrete Domains Meet Expressive Cardinality Restrictions in\u00a0Description Logics"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4049-221X","authenticated-orcid":false,"given":"Franz","family":"Baader","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0924-8478","authenticated-orcid":false,"given":"Stefan","family":"Borgwardt","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8623-6465","authenticated-orcid":false,"given":"Filippo","family":"De Bortoli","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5999-2583","authenticated-orcid":false,"given":"Patrick","family":"Koopmann","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2025,7,30]]},"reference":[{"issue":"11","key":"35_CR1","doi-asserted-by":"publisher","first-page":"832","DOI":"10.1145\/182.358434","volume":"26","author":"JF Allen","year":"1983","unstructured":"Allen, J.F.: Maintaining knowledge about temporal intervals. Commun. ACM 26(11), 832\u2013843 (1983). https:\/\/doi.org\/10.1145\/182.358434","journal-title":"Commun. ACM"},{"key":"35_CR2","doi-asserted-by":"publisher","unstructured":"Alrabbaa, C., Baader, F., Borgwardt, S., Koopmann, P., Kovtunova, A.: Combining proofs for description logic and concrete domain reasoning. In: Fensel, A., Ozaki, A., Roman, D., Soylu, A. (eds.) Rules and Reasoning - 7th International Joint Conference, RuleML+RR 2023, Proceedings. LNCS, vol. 14244, pp. 54\u201369. Springer (2023). https:\/\/doi.org\/10.1007\/978-3-031-45072-3_4","DOI":"10.1007\/978-3-031-45072-3_4"},{"key":"35_CR3","doi-asserted-by":"publisher","unstructured":"Baader, F.: A new description logic with set constraints and cardinality constraints on role successors. In: Dixon, C., Finger, M. (eds.) Proceedings of the 11th International Symposium on Frontiers of Combining Systems (FroCoS\u201917). LNCS, vol. 10483, pp. 43\u201359. Springer-Verlag, Bras\u00edlia, Brazil (2017). https:\/\/doi.org\/10.1007\/978-3-319-66167-4_3","DOI":"10.1007\/978-3-319-66167-4_3"},{"key":"35_CR4","doi-asserted-by":"publisher","unstructured":"Baader, F., Bednarczyk, B., Rudolph, S.: Satisfiability and query answering in description logics with global and local cardinality constraints. In: ECAI 2020, pp. 616\u2013623. IOS Press (2020). https:\/\/doi.org\/10.3233\/FAIA200146","DOI":"10.3233\/FAIA200146"},{"key":"35_CR5","doi-asserted-by":"publisher","unstructured":"Baader, F., Borgwardt, S., De Bortoli, F., Koopmann, P.: Concrete domains meet expressive cardinality restrictions in description logics (extended version) (2025). https:\/\/doi.org\/10.48550\/arXiv.2505.21103","DOI":"10.48550\/arXiv.2505.21103"},{"key":"35_CR6","doi-asserted-by":"publisher","unstructured":"Baader, F., Calvanese, D., McGuinness, D.L., Nardi, D., Patel-Schneider, P.F. (eds.): The Description Logic Handbook: Theory, Implementation, and Applications. Cambridge University Press (2003). https:\/\/doi.org\/10.1017\/CBO9780511711787","DOI":"10.1017\/CBO9780511711787"},{"key":"35_CR7","doi-asserted-by":"publisher","unstructured":"Baader, F., De Bortoli, F.: On the expressive power of description logics with cardinality constraints on finite and infinite sets. In: Herzig, A., Popescu, A. (eds.) FroCoS 2019. LNCS (LNAI), vol. 11715, pp. 203\u2013219. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-29007-8_12","DOI":"10.1007\/978-3-030-29007-8_12"},{"key":"35_CR8","unstructured":"Baader, F., Hanschke, P.: A scheme for integrating concrete domains into concept languages. In: Mylopoulos, J., Reiter, R. (eds.) Proceedings of the 12th International Joint Conference on Artificial Intelligence, IJCAI 1991, pp. 452\u2013457. Morgan Kaufmann (1991). http:\/\/ijcai.org\/Proceedings\/91-1\/Papers\/070.pdf"},{"key":"35_CR9","doi-asserted-by":"publisher","unstructured":"Baader, F., Horrocks, I., Lutz, C., Sattler, U.: An Introduction to Description Logic. Cambridge University Press (2017). https:\/\/doi.org\/10.1017\/9781139025355","DOI":"10.1017\/9781139025355"},{"key":"35_CR10","doi-asserted-by":"publisher","unstructured":"Baader, F., Rydval, J.: Description logics with concrete domains and general concept inclusions revisited. In: Peltier, N., Sofronie-Stokkermans, V. (eds.) IJCAR 2020. LNCS (LNAI), vol. 12166, pp. 413\u2013431. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-51074-9_24","DOI":"10.1007\/978-3-030-51074-9_24"},{"issue":"3","key":"35_CR11","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1007\/s10817-022-09626-2","volume":"66","author":"F Baader","year":"2022","unstructured":"Baader, F., Rydval, J.: Using model theory to find decidable and tractable description logics with concrete domains. J. Autom. Reason. 66(3), 357\u2013407 (2022). https:\/\/doi.org\/10.1007\/s10817-022-09626-2","journal-title":"J. Autom. Reason."},{"key":"35_CR12","doi-asserted-by":"crossref","unstructured":"Berger, R.: The undecidability of the domino problem. Mem. Am. Math. Soc. 66, 72 (1966). https:\/\/mathscinet.ams.org\/mathscinet-getitem?mr=216954","DOI":"10.1090\/memo\/0066"},{"key":"35_CR13","unstructured":"Borgwardt, S., De Bortoli, F., Koopmann, P.: The precise complexity of reasoning in $$\\cal{ALC}$$ with $$\\omega $$-admissible concrete domains. In: Giordano, L., Jung, J.C., Ozaki, A. (eds.) Proceedings of the 37th International Workshop on Description Logics (DL 2024). CEUR Workshop Proceedings, vol.\u00a03739. CEUR-WS.org (2024). https:\/\/ceur-ws.org\/Vol-3739\/paper-1.pdf"},{"key":"35_CR14","doi-asserted-by":"publisher","unstructured":"Carapelle, C., Turhan, A.: Description logics reasoning w.r.t. general TBoxes is decidable for concrete domains with the EHD-property. In: Kaminka, G.A., et al. (eds.) ECAI 2016 \u2013 22nd European Conference on Artificial Intelligence. Frontiers in Artificial Intelligence and Applications, vol.\u00a0285, pp. 1440\u20131448. IOS Press (2016). https:\/\/doi.org\/10.3233\/978-1-61499-672-9-1440","DOI":"10.3233\/978-1-61499-672-9-1440"},{"key":"35_CR15","doi-asserted-by":"publisher","unstructured":"Demri, S., Quaas, K.: First steps towards taming description logics with strings. In: Gaggl, S.A., Martinez, M.V., Ortiz, M. (eds.) Logics in Artificial Intelligence \u2013 18th European Conference, JELIA 2023, Proceedings. LNCS, vol. 14281, pp. 322\u2013337. Springer (2023). https:\/\/doi.org\/10.1007\/978-3-031-43619-2_23","DOI":"10.1007\/978-3-031-43619-2_23"},{"key":"35_CR16","doi-asserted-by":"publisher","unstructured":"Guti\u00e9rrez-Basulto, V., Ib\u00e1\u00f1ez-Garc\u00eda, Y.A., Jung, J.C.: Number restrictions on transitive roles in description logics with nominals. In: Singh, S., Markovitch, S. (eds.) Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, pp. 1121\u20131127. AAAI Press (2017). https:\/\/doi.org\/10.1609\/AAAI.V31I1.10678","DOI":"10.1609\/AAAI.V31I1.10678"},{"key":"35_CR17","unstructured":"Hollunder, B., Baader, F.: Qualifying number restrictions in concept languages. In: Allen, J.F., Fikes, R., Sandewall, E. (eds.) Proceedings of the 2nd International Conference on Principles of Knowledge Representation and Reasoning (KR\u201991), pp. 335\u2013346. Morgan Kaufmann (1991)"},{"key":"35_CR18","unstructured":"Hollunder, B., Nutt, W., Schmidt-Schau\u00df, M.: Subsumption algorithms for concept description languages. In: 9th European Conference on Artificial Intelligence, ECAI 1990, pp. 348\u2013353 (1990)"},{"key":"35_CR19","unstructured":"Horrocks, I., Sattler, U.: Ontology reasoning in the $$\\cal{SHOQ}(\\rm D)$$ description logic. In: Nebel, B. (ed.) Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence, IJCAI 2001, pp. 199\u2013204. Morgan Kaufmann (2001)"},{"issue":"3","key":"35_CR20","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1093\/JIGPAL\/8.3.239","volume":"8","author":"I Horrocks","year":"2000","unstructured":"Horrocks, I., Sattler, U., Tobies, S.: Practical reasoning for very expressive description logics. Log. J. IGPL 8(3), 239\u2013263 (2000). https:\/\/doi.org\/10.1093\/JIGPAL\/8.3.239","journal-title":"Log. J. IGPL"},{"key":"35_CR21","doi-asserted-by":"publisher","unstructured":"Jonsson, P.: Constants and finite unary relations in qualitative constraint reasoning. Artif. Intell. 257, 1\u201323 (2018). https:\/\/doi.org\/10.1016\/j.artint.2017.12.003","DOI":"10.1016\/j.artint.2017.12.003"},{"key":"35_CR22","doi-asserted-by":"publisher","unstructured":"Kuncak, V., Rinard, M.: Towards efficient satisfiability checking for boolean algebra with presburger arithmetic. In: Pfenning, F. (ed.) CADE 2007. LNCS (LNAI), vol. 4603, pp. 215\u2013230. Springer, Heidelberg (2007). https:\/\/doi.org\/10.1007\/978-3-540-73595-3_15","DOI":"10.1007\/978-3-540-73595-3_15"},{"key":"35_CR23","doi-asserted-by":"publisher","unstructured":"Labai, N., Ortiz, M., Simkus, M.: An ExpTime upper bound for $$\\cal{ALC}$$ with integers. In: Calvanese, D., Erdem, E., Thielscher, M. (eds.) Proceedings of the 17th International Conference on Principles of Knowledge Representation and Reasoning, KR 2020, pp. 614\u2013623 (2020). https:\/\/doi.org\/10.24963\/KR.2020\/61","DOI":"10.24963\/KR.2020\/61"},{"key":"35_CR24","doi-asserted-by":"publisher","unstructured":"Li, S., Liu, W., Wang, S.: Qualitative constraint satisfaction problems: an extended framework with landmarks. Artif. Intell. 201, 32\u201358 (2013). https:\/\/doi.org\/10.1016\/j.artint.2013.05.006","DOI":"10.1016\/j.artint.2013.05.006"},{"key":"35_CR25","unstructured":"Lutz, C.: The complexity of description logics with concrete domains. Ph.D. thesis, RWTH Aachen University, Germany (2002). http:\/\/sylvester.bth.rwth-aachen.de\/dissertationen\/2002\/042\/index.htm"},{"issue":"4","key":"35_CR26","doi-asserted-by":"publisher","first-page":"669","DOI":"10.1145\/1024922.1024925","volume":"5","author":"C Lutz","year":"2004","unstructured":"Lutz, C.: NExpTime-complete description logics with concrete domains. ACM Trans. Comput. Logic (TOCL) 5(4), 669\u2013705 (2004). https:\/\/doi.org\/10.1145\/1024922.1024925","journal-title":"ACM Trans. Comput. Logic (TOCL)"},{"issue":"1","key":"35_CR27","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1007\/s10817-006-9049-7","volume":"38","author":"C Lutz","year":"2007","unstructured":"Lutz, C., Mili\u010di\u0107, M.: A tableau algorithm for description logics with concrete domains and general TBoxes. J. Autom. Reason. 38(1), 227\u2013259 (2007). https:\/\/doi.org\/10.1007\/s10817-006-9049-7","journal-title":"J. Autom. Reason."},{"key":"35_CR28","unstructured":"Matiyasevich, Y.V.: Hilbert\u2019s tenth problem. With a foreword by Martin Davis. MIT Press, Cambridge, MA (1993)"},{"key":"35_CR29","unstructured":"Randell, D.A., Cui, Z., Cohn, A.G.: A spatial logic based on regions and connection. In: Nebel, B., Rich, C., Swartout, W.R. (eds.) Proceedings of the 3rd International Conference on Principles of Knowledge Representation and Reasoning (KR\u201992), pp. 165\u2013176. Morgan Kaufmann (1992)"},{"key":"35_CR30","doi-asserted-by":"publisher","unstructured":"Tobies, S.: The complexity of reasoning with cardinality restrictions and nominals in expressive description logics. J. Artif. Intell. Res. 12, 199\u2013217 (2000). https:\/\/doi.org\/10.1613\/JAIR.705","DOI":"10.1613\/JAIR.705"},{"issue":"1","key":"35_CR31","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1093\/LOGCOM\/11.1.85","volume":"11","author":"S Tobies","year":"2001","unstructured":"Tobies, S.: PSPACE reasoning for graded modal logics. J. Log. Comput. 11(1), 85\u2013106 (2001). https:\/\/doi.org\/10.1093\/LOGCOM\/11.1.85","journal-title":"J. Log. Comput."}],"container-title":["Lecture Notes in Computer Science","Automated Deduction \u2013 CADE 30"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-99984-0_35","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,19]],"date-time":"2026-06-19T15:25:47Z","timestamp":1781882747000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-99984-0_35"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025]]},"ISBN":["9783031999833","9783031999840"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-99984-0_35","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025]]},"assertion":[{"value":"30 July 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"The authors have no competing interests to declare that\u00a0are relevant to the content of this article.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Disclosure of Interests"}},{"value":"CADE","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Automated Deduction","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Stuttgart","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Germany","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2025","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"28 July 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"31 July 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"30","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"cade2025","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/www.dhbw-stuttgart.de\/cade-30\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}