{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,2]],"date-time":"2025-11-02T02:18:55Z","timestamp":1762049935739,"version":"build-2065373602"},"reference-count":72,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2022,5,4]],"date-time":"2022-05-04T00:00:00Z","timestamp":1651622400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,5,4]],"date-time":"2022-05-04T00:00:00Z","timestamp":1651622400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100002957","name":"Technische Universit\u00e4t Dresden","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100002957","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Autom Reasoning"],"published-print":{"date-parts":[[2022,8]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Concrete domains have been introduced in the area of Description Logic to enable reference to concrete objects (such as numbers) and predefined predicates on these objects (such as numerical comparisons) when defining concepts. Unfortunately, in the presence of general concept inclusions (GCIs), which are supported by all modern DL systems, adding concrete domains may easily lead to undecidability. To regain decidability of the DL<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mathcal {ALC}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>ALC<\/mml:mi><\/mml:math><\/jats:alternatives><\/jats:inline-formula>in the presence of GCIs, quite strong restrictions, in sum called<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\omega $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>\u03c9<\/mml:mi><\/mml:math><\/jats:alternatives><\/jats:inline-formula>-admissibility, were imposed on the concrete domain. On the one hand, we generalize the notion of<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\omega $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>\u03c9<\/mml:mi><\/mml:math><\/jats:alternatives><\/jats:inline-formula>-admissibility from concrete domains with only binary predicates to concrete domains with predicates of arbitrary arity. On the other hand, we relate<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\omega $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>\u03c9<\/mml:mi><\/mml:math><\/jats:alternatives><\/jats:inline-formula>-admissibility to well-known notions from model theory. In particular, we show that finitely bounded homogeneous structures yield<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\omega $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>\u03c9<\/mml:mi><\/mml:math><\/jats:alternatives><\/jats:inline-formula>-admissible concrete domains. This allows us to show<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\omega $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>\u03c9<\/mml:mi><\/mml:math><\/jats:alternatives><\/jats:inline-formula>-admissibility of concrete domains using existing results from model theory. When integrating concrete domains into lightweight DLs of the<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mathcal {EL}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>EL<\/mml:mi><\/mml:math><\/jats:alternatives><\/jats:inline-formula>family, achieving decidability is not enough. One wants reasoning in the resulting DL to be tractable. This can be achieved by using so-called p-admissible concrete domains and restricting the interaction between the DL and the concrete domain. We investigate p-admissibility from an algebraic point of view. Again, this yields strong algebraic tools for demonstrating p-admissibility. In particular, we obtain an expressive numerical p-admissible concrete domain based on the rational numbers. Although<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\omega $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>\u03c9<\/mml:mi><\/mml:math><\/jats:alternatives><\/jats:inline-formula>-admissibility and p-admissibility are orthogonal conditions that are almost exclusive, our algebraic characterizations of these two properties allow us to locate an infinite class of p-admissible concrete domains whose integration into<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mathcal {ALC}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>ALC<\/mml:mi><\/mml:math><\/jats:alternatives><\/jats:inline-formula>yields decidable DLs.<\/jats:p>","DOI":"10.1007\/s10817-022-09626-2","type":"journal-article","created":{"date-parts":[[2022,5,4]],"date-time":"2022-05-04T06:03:24Z","timestamp":1651644204000},"page":"357-407","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["Using Model Theory to Find Decidable and Tractable Description Logics with Concrete Domains"],"prefix":"10.1007","volume":"66","author":[{"given":"Franz","family":"Baader","sequence":"first","affiliation":[]},{"given":"Jakub","family":"Rydval","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,5,4]]},"reference":[{"issue":"11","key":"9626_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)","journal-title":"Commun. ACM"},{"key":"9626_CR2","unstructured":"Baader, F., Hanschke, P.: A scheme for integrating concrete domains into concept languages. In: Proceedings of the 12th International Joint Conference on Artificial Intelligence (IJCAI\u201991), pp. 452\u2013457 (1991). Long version available as [6]"},{"key":"9626_CR3","unstructured":"Baader, F., Hanschke, P.: A scheme for integrating concrete domains into concept languages. Tech. Rep. RR-91-10, Deutsches Forschungszentrum f\u00fcr K\u00fcnstliche Intelligenz (DFKI) (1991). https:\/\/lat.inf.tu-dresden.de\/research\/reports\/1991\/DFKI-RR-91-10.pdf"},{"key":"9626_CR4","doi-asserted-by":"crossref","unstructured":"Baader, F., Hanschke, P.: Extensions of concept languages for a mechanical engineering application. In: Proceedings of the 16th German Workshop on Artificial Intelligence (GWAI\u201992), Lecture Notes in Computer Science, vol. 671, pp. 132\u2013143. Springer, Berlin (1992)","DOI":"10.1007\/BFb0018999"},{"key":"9626_CR5","doi-asserted-by":"crossref","unstructured":"Baader, F., Rydval, J.: An algebraic view on p-admissible concrete domains for lightweight description logics (extended version). LTCS-Report 20-10, Chair of Automata Theory, Institute of Theoretical Computer Science, Technische Universit\u00e4t Dresden, Dresden, Germany (2020). https:\/\/tu-dresden.de\/inf\/lat\/reports#BaRy-LTCS-20-10","DOI":"10.25368\/2022.265"},{"key":"9626_CR6","doi-asserted-by":"crossref","unstructured":"Baader, F., Rydval, J.: Description logics with concrete domains and general concept inclusions revisited. In: Stokkermans, V.S., Peltier, N. (eds.) Proceedings of the International Joint Conference on Automated Reasoning (IJCAR 2020), Lecture Notes in Computer Science, vol. 12166, pp. 413\u2013431. Springer, New York (2020)","DOI":"10.1007\/978-3-030-51074-9_24"},{"key":"9626_CR7","doi-asserted-by":"crossref","unstructured":"Baader, F., Rydval, J.: Using model-theory to find $$\\omega $$-admissible concrete domains. LTCS-Report 20-01, Chair of Automata Theory, Institute of Theoretical Computer Science, Technische Universit\u00e4t Dresden, Dresden, Germany (2020). https:\/\/tu-dresden.de\/inf\/lat\/reports#BaRy-LTCS-20-01","DOI":"10.25368\/2022.259"},{"key":"9626_CR8","doi-asserted-by":"crossref","unstructured":"Baader, F., Rydval, J.: An algebraic view on p-admissible concrete domains for lightweight description logics. In: Faber, W., Friedrich, D., Gebser, M. (eds.) 17th European Conference on Logics in Artificial Intelligence (JELIA 2021), Lecture Notes in Artificial Intelligence, vol. 12678, pp. 194\u2013209. Springer, New York (2021)","DOI":"10.1007\/978-3-030-75775-5_14"},{"key":"9626_CR9","doi-asserted-by":"crossref","unstructured":"Baader, F., B\u00fcrckert, H.J., Hollunder, B., Nutt, W., Siekmann, J.H.: Concept logics. In: Lloyd, J.W. (ed.) Computational Logics, Symposium Proceedings, pp. 177\u2013201. Springer, Berlin (1990)","DOI":"10.1007\/978-3-642-76274-1_10"},{"key":"9626_CR10","unstructured":"Baader, F., Calvanese, D., McGuinness, D., Nardi, D., Patel-Schneider, P.F. (eds.): The Description Logic Handbook: Theory, Implementation, and Applications. Cambridge University Press, Cambridge (2003)"},{"key":"9626_CR11","unstructured":"Baader, F., Brandt, S., Lutz, C.: Pushing the $$\\cal{EL}$$ envelope. In: Kaelbling, L.P., Saffiotti, A. (eds.) Proceedings of the 19th International Joint Conference on Artificial Intelligence (IJCAI\u00a02005), pp. 364\u2013369. Morgan Kaufmann, Los Altos, Edinburgh (UK) (2005)"},{"key":"9626_CR12","doi-asserted-by":"publisher","DOI":"10.1017\/9781139025355","volume-title":"An Introduction to Description Logic","author":"F Baader","year":"2017","unstructured":"Baader, F., Horrocks, I., Lutz, C., Sattler, U.: An Introduction to Description Logic. Cambridge University Press, Cambridge (2017)"},{"key":"9626_CR13","doi-asserted-by":"crossref","unstructured":"Barto, L., Kompatscher, M., Ol\u0161\u00e1k, M., Van\u00a0Pham, T., Pinsker, M.: Equations in oligomorphic clones and the Constraint Satisfaction Problem for $$\\omega $$-categorical structures. J. Math. Logic 19(2) (2019)","DOI":"10.1142\/S0219061319500107"},{"issue":"1\u20132","key":"9626_CR14","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/j.tcs.2007.10.025","volume":"391","author":"P Bell","year":"2008","unstructured":"Bell, P., Potapov, I.: On undecidability bounds for matrix decision problems. Theor. Comput. Sci. 391(1\u20132), 3\u201313 (2008)","journal-title":"Theor. Comput. Sci."},{"key":"9626_CR15","doi-asserted-by":"crossref","unstructured":"Bodirsky, M.: The core of a countably categorical structure. In: Diekert, V., Durand, B. (eds.) Proceedings of the 22nd Annual Symposium on Theoretical Aspects of Computer Science (STACS 2005), Lecture Notes in Computer Science, vol. 3404, pp. 110\u2013120. Springer, Berlin (2005)","DOI":"10.1007\/978-3-540-31856-9_9"},{"key":"9626_CR16","unstructured":"Bodirsky, M.: Complexity classification in infinite-domain constraint satisfaction (2012). M\u00e9moire d\u2019Habilitation \u00e0 Diriger des Recherches, Universit\u00e9 Diderot\u2014Paris 7. https:\/\/arxiv.org\/pdf\/1201.0856.pdf"},{"issue":"1","key":"9626_CR17","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1016\/j.jcss.2012.05.012","volume":"79","author":"M Bodirsky","year":"2013","unstructured":"Bodirsky, M., Dalmau, V.: Datalog and constraint satisfaction with infinite templates. J. Comput. Syst. Sci. 79(1), 79\u2013100 (2013)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"9626_CR18","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1667053.1667058","volume":"57","author":"M Bodirsky","year":"2010","unstructured":"Bodirsky, M., K\u00e1ra, J.: The complexity of temporal constraint satisfaction problems. J. ACM (JACM) 57(2), 1\u201341 (2010)","journal-title":"J. ACM (JACM)"},{"key":"9626_CR19","doi-asserted-by":"crossref","unstructured":"Bodirsky, M., Mottet, A.: Reducts of finitely bounded homogeneous structures, and lifting tractability from finite-domain constraint satisfaction. In: Proceedings of the 31st Annual ACM\/IEEE Symposium on Logic in Computer Science (LICS 2016), pp. 623\u2013632. ACM\/IEEE (2016). https:\/\/arxiv.org\/pdf\/1601.04520v1.pdf","DOI":"10.1145\/2933575.2934515"},{"issue":"3","key":"9626_CR20","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1093\/logcom\/exi083","volume":"16","author":"M Bodirsky","year":"2006","unstructured":"Bodirsky, M., Ne\u0161et\u0159il, J.: Constraint satisfaction with countable homogeneous templates. J. Log. Comput. 16(3), 359\u2013373 (2006)","journal-title":"J. Log. Comput."},{"key":"9626_CR21","unstructured":"Bodirsky, M., W\u00f6lfl, S.: RCC8 is polynomial on networks of bounded treewidth. In: Walsh, T. (ed.) Proceedings of the 22nd International Joint Conference on Artificial Intelligence (IJCAI 2011), pp. 756\u2013761. IJCAI\/AAAI (2011)"},{"issue":"18","key":"9626_CR22","doi-asserted-by":"publisher","first-page":"1684","DOI":"10.1016\/j.tcs.2008.12.050","volume":"410","author":"M Bodirsky","year":"2009","unstructured":"Bodirsky, M., Chen, H., K\u00e1ra, J., von Oertzen, T.: Maximal infinite-valued constraint languages. Theor. Comput. Sci. 410(18), 1684\u20131693 (2009)","journal-title":"Theor. Comput. Sci."},{"key":"9626_CR23","doi-asserted-by":"crossref","unstructured":"Bodirsky, M., Hils, M., Martin, B.: On the scope of the universal-algebraic approach to constraint satisfaction. In: Proceedings of the 25th Annual IEEE Symposium on Logic in Computer Science (LICS 2010), pp. 90\u201399. IEEE (2010)","DOI":"10.1109\/LICS.2010.13"},{"issue":"1","key":"9626_CR24","doi-asserted-by":"publisher","first-page":"404","DOI":"10.1137\/090778493","volume":"26","author":"M Bodirsky","year":"2012","unstructured":"Bodirsky, M., Chen, H., Feder, T.: On the complexity of MMSNP. SIAM J. Discret. Math. 26(1), 404\u2013414 (2012)","journal-title":"SIAM J. Discret. Math."},{"issue":"3","key":"9626_CR25","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3105907","volume":"18","author":"M Bodirsky","year":"2017","unstructured":"Bodirsky, M., Jonsson, P., Pham, T.V.: The complexity of phylogeny constraint satisfaction problems. ACM Trans. Comput. Logic (TOCL) 18(3), 1\u201342 (2017)","journal-title":"ACM Trans. Comput. Logic (TOCL)"},{"key":"9626_CR26","doi-asserted-by":"crossref","unstructured":"Bodirsky, M., Madelaine, F., Mottet, A.: A universal-algebraic proof of the complexity dichotomy for monotone monadic SNP. In: Proceedings of the 33rd Annual ACM\/IEEE Symposium on Logic in Computer Science (LICS 2018), pp. 105\u2013114 (2018)","DOI":"10.1145\/3209108.3209156"},{"issue":"2","key":"9626_CR27","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3154832","volume":"65","author":"M Bodirsky","year":"2018","unstructured":"Bodirsky, M., Martin, B., Mottet, A.: Discrete temporal constraint satisfaction problems. J. ACM (JACM) 65(2), 1\u201341 (2018)","journal-title":"J. ACM (JACM)"},{"issue":"4","key":"9626_CR28","doi-asserted-by":"publisher","first-page":"1224","DOI":"10.1137\/16M1082974","volume":"48","author":"M Bodirsky","year":"2019","unstructured":"Bodirsky, M., Martin, B., Pinsker, M., Pongr\u00e1cz, A.: Constraint satisfaction problems for reducts of homogeneous graphs. SIAM J. Comput. 48(4), 1224\u20131264 (2019)","journal-title":"SIAM J. Comput."},{"key":"9626_CR29","doi-asserted-by":"crossref","unstructured":"Bodirsky, M., Kn\u00e4uer, S., Starke, F.: ASNP: A tame fragment of existential second-order logic. In: Anselmo, M., Vedova, G.D., Manea, F., Pauly, A. (eds.) Beyond the Horizon of Computability\u2014Proceedings of the 16th Conference on Computability in Europe (CiE 2020), Lecture Notes in Computer Science, vol. 12098, pp. 149\u2013162. Springer (2020)","DOI":"10.1007\/978-3-030-51466-2_13"},{"key":"9626_CR30","doi-asserted-by":"crossref","unstructured":"Bodirsky, M., Rydval, J., Schrottenloher, A.: Universal Horn sentences and the joint embedding property (2021). https:\/\/arxiv.org\/pdf\/2104.11123.pdf","DOI":"10.46298\/dmtcs.7435"},{"key":"9626_CR31","doi-asserted-by":"crossref","unstructured":"Boja\u0144czyk, M., Segoufin, L., Toru\u0144czyk, S.: Verification of database-driven systems via amalgamation. In: Proceedings of the 32nd ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, pp. 63\u201374 (2013)","DOI":"10.1145\/2463664.2465228"},{"key":"9626_CR32","unstructured":"Brandt, S.: Polynomial time reasoning in a description logic with existential restrictions, GCI axioms, and\u2014what else? In: de\u00a0M\u00e1ntaras, R.L., Saitta, L. (eds.) Proceedings of the 16th European Conference on Artificial Intelligence (ECAI\u00a02004), pp. 298\u2013302 (2004)"},{"key":"9626_CR33","unstructured":"Braunfeld, S.: The undecidability of joint embedding and joint homomorphism for hereditary graph classes. Discret. Math. Theor. Comput. Sci. 21(2) (2019)"},{"key":"9626_CR34","doi-asserted-by":"crossref","unstructured":"Bulatov, A.A.: A dichotomy theorem for nonuniform CSPs. In: Umans, C. (ed.) 58th IEEE Annual Symposium on Foundations of Computer Science (FOCS 2017), pp. 319\u2013330. IEEE Computer Society (2017)","DOI":"10.1109\/FOCS.2017.37"},{"key":"9626_CR35","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., Fox, M., Bouquet, P., H\u00fcllermeier, E., Dignum, V., Dignum, F., van Harmelen, F. (eds.) Proceedings of the 22nd European Conference on Artificial Intelligence (ECAI 2016), Frontiers in Artificial Intelligence and Applications, vol. 285, pp. 1440\u20131448. IOS Press (2016)"},{"issue":"2","key":"9626_CR36","doi-asserted-by":"publisher","first-page":"689","DOI":"10.1007\/s00224-016-9724-y","volume":"61","author":"C Carapelle","year":"2017","unstructured":"Carapelle, C., Feng, S., Kartzow, A., Lohrey, M.: Satisfiability of ECTL$$^{*}$$ with local tree constraints. Theory Comput. Syst. 61(2), 689\u2013720 (2017)","journal-title":"Theory Comput. Syst."},{"key":"9626_CR37","doi-asserted-by":"crossref","unstructured":"Chandra, A.K., Merlin, P.M.: Optimal implementation of conjunctive queries in relational data bases. In: Hopcroft, J.E., Friedman, E.P., Harrison, M.A. (eds.) Proceedings of the 9th Annual ACM Symposium on Theory of Computing (STOC 1977), pp. 77\u201390. ACM (1977)","DOI":"10.1145\/800105.803397"},{"issue":"4","key":"9626_CR38","doi-asserted-by":"publisher","first-page":"454","DOI":"10.1006\/aama.1998.0641","volume":"22","author":"G Cherlin","year":"1999","unstructured":"Cherlin, G., Shelah, S., Shi, N.: Universal graphs with forbidden subgraphs and algebraic closure. Adv. Appl. Math. 22(4), 454\u2013491 (1999)","journal-title":"Adv. Appl. Math."},{"key":"9626_CR39","doi-asserted-by":"crossref","unstructured":"Dabrowski, K.K., Jonsson, P., Ordyniak, S., Osipov, G.: Solving infinite-domain CSPs using the patchwork property. In: Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI-21). AAAI Press\/The MIT Press (2021)","DOI":"10.1609\/aaai.v35i5.16488"},{"issue":"3","key":"9626_CR40","doi-asserted-by":"publisher","first-page":"380","DOI":"10.1016\/j.ic.2006.09.006","volume":"205","author":"S Demri","year":"2007","unstructured":"Demri, S., D\u2019Souza, D.: An automata-theoretic approach to constraint LTL. Inf. Comput. 205(3), 380\u2013415 (2007)","journal-title":"Inf. Comput."},{"issue":"3","key":"9626_CR41","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1016\/0743-1066(84)90014-1","volume":"1","author":"WF Dowling","year":"1984","unstructured":"Dowling, W.F., Gallier, J.H.: Linear-time algorithms for testing the satisfiability of propositional horn formulae. J. Log. Program. 1(3), 267\u2013284 (1984)","journal-title":"J. Log. Program."},{"key":"9626_CR42","unstructured":"Fagin, R.: Generalized first-order spectra and polynomial-time recognizable sets. In: Karp, R. (ed.) SIAM-AMS Proceedings on Complexity of Computation, vol.\u00a07, pp. 43\u201373 (1974)"},{"key":"9626_CR43","doi-asserted-by":"crossref","unstructured":"Feder, T., Vardi, M.Y.: Homomorphism closed vs. existential positive. In: Proceedings of the 18th Annual IEEE Symposium of Logic in Computer Science (LICS 2003), pp. 311\u2013320. IEEE (2003)","DOI":"10.1109\/LICS.2003.1210071"},{"key":"9626_CR44","unstructured":"Gillibert, P., Jonu\u0161as, J., Kompatscher, M., Mottet, A., Pinsker, M.: Hrushovski\u2019s encoding and $$\\omega $$-categorical CSP monsters. In: 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik (2020)"},{"key":"9626_CR45","doi-asserted-by":"crossref","unstructured":"Haarslev, V., M\u00f6ller, R., Wessel, M.: The description logic $$\\cal{ALCNH}_{{R}+}$$ extended with concrete domains: a practically motivated approach. In: Proceedings of the International Joint Conference on Automated Reasoning (IJCAR\u00a02001), Lecture Notes in Artificial Intelligence, vol. 2083, pp. 29\u201344. Springer, Berlin (2001)","DOI":"10.1007\/3-540-45744-5_4"},{"issue":"1","key":"9626_CR46","doi-asserted-by":"publisher","first-page":"69","DOI":"10.2140\/pjm.1971.38.69","volume":"38","author":"CW Henson","year":"1971","unstructured":"Henson, C.W.: A family of countable homogeneous graphs. Pac. J. Math. 38(1), 69\u201383 (1971)","journal-title":"Pac. J. Math."},{"issue":"3","key":"9626_CR47","doi-asserted-by":"publisher","first-page":"494","DOI":"10.2307\/2272734","volume":"37","author":"CW Henson","year":"1972","unstructured":"Henson, C.W.: Countable homogeneous relational structures and $$\\aleph _{0}$$-categorical theories. J. Symbol. Logic 37(3), 494\u2013500 (1972)","journal-title":"J. Symbol. Logic"},{"issue":"2","key":"9626_CR48","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1016\/0004-3702(95)00042-9","volume":"83","author":"R Hirsch","year":"1996","unstructured":"Hirsch, R.: Relation algebras of intervals. Artif. Intell. 83(2), 267\u2013295 (1996)","journal-title":"Artif. Intell."},{"key":"9626_CR49","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511551574","volume-title":"Model Theory","author":"W Hodges","year":"1993","unstructured":"Hodges, W.: Model Theory. Cambridge University Press, Cambridge (1993)"},{"key":"9626_CR50","volume-title":"A Shorter Model Theory","author":"W Hodges","year":"1997","unstructured":"Hodges, W.: A Shorter Model Theory. Cambridge University Press, Cambridge (1997)"},{"issue":"6","key":"9626_CR51","doi-asserted-by":"publisher","first-page":"1069","DOI":"10.1093\/bib\/bbv011","volume":"16","author":"R Hoehndorf","year":"2015","unstructured":"Hoehndorf, R., Schofield, P.N., Gkoutos, G.V.: The role of ontologies in biological and biomedical research: a functional perspective. Brief. Bioinform. 16(6), 1069\u20131080 (2015)","journal-title":"Brief. Bioinform."},{"issue":"1","key":"9626_CR52","doi-asserted-by":"publisher","first-page":"7","DOI":"10.1016\/j.websem.2003.07.001","volume":"1","author":"I Horrocks","year":"2003","unstructured":"Horrocks, I., Patel-Schneider, P.F., van Harmelen, F.: From SHIQ and RDF to OWL: the making of a web ontology language. J. Web Semant. 1(1), 7\u201326 (2003)","journal-title":"J. Web Semant."},{"key":"9626_CR53","first-page":"229","volume":"27","author":"J Hubi\u010dka","year":"2016","unstructured":"Hubi\u010dka, J., Ne\u0161et\u0159il, J.: Homomorphism and embedding universal structures for restricted classes. J. Multiple-Valued Logic Soft Comput. 27, 229\u2013253 (2016)","journal-title":"J. Multiple-Valued Logic Soft Comput."},{"key":"9626_CR54","series-title":"Graduate Texts in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0539-5","volume-title":"Descriptive Complexity","author":"N Immerman","year":"1999","unstructured":"Immerman, N.: Descriptive Complexity. Graduate Texts in Computer Science, Springer, Berlin (1999)"},{"key":"9626_CR55","volume-title":"Locally Finite Groups","author":"OH Kegel","year":"2000","unstructured":"Kegel, O.H., Wehrfritz, B.A.: Locally Finite Groups. Elsevier, New York (2000)"},{"key":"9626_CR56","unstructured":"Klin, B., Lasota, S., Ochremiak, J., Torunczyk, S.: Homomorphism problems for first-order definable structures. In: 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2016)"},{"key":"9626_CR57","doi-asserted-by":"crossref","unstructured":"Knight, J., Lachlan, A.: Shrinking, stretching and codes for homogeneous structures. In: Classification Theory (Chicago, IL, 1985), Lecture Notes in Mathematics, 1292, pp. 192\u2013228. Springer, Berlin (1987)","DOI":"10.1007\/BFb0082239"},{"key":"9626_CR58","unstructured":"Kompatscher, M., Van\u00a0Pham, T.: A complexity dichotomy for poset constraint satisfaction. In: Vollmer, H., Vall\u00e9e, B. (eds.) 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017), vol.\u00a066, pp. 47:1\u201347:12. Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany (2017)"},{"key":"9626_CR59","unstructured":"Kopczy\u0144ski, E., Toru\u0144czyk, S.: LOIS: an application of SMT solvers. In: King, T., Piskac, R. (eds.) Proc. of the 14th International Workshop on Satisfiability Modulo Theories (SMT 2016), CEUR Workshop Procveedings, vol. 1617, pp. 51\u201360. ceur-ws.org (2016)"},{"key":"9626_CR60","doi-asserted-by":"publisher","unstructured":"Labai, N.: Automata-based reasoning for decidable logics with data values. Dissertation, Technische Universit\u00e4t Wien (2021). https:\/\/doi.org\/10.34726\/hss.2021.94060","DOI":"10.34726\/hss.2021.94060"},{"key":"9626_CR61","doi-asserted-by":"crossref","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)","DOI":"10.24963\/kr.2020\/61"},{"key":"9626_CR62","unstructured":"Lutz, C.: Interval-based temporal reasoning with general TBoxes. In: Proceedings of the 17th International Joint Conference on Artificial Intelligence (IJCAI\u00a02001), pp. 89\u201394 (2001)"},{"key":"9626_CR63","doi-asserted-by":"crossref","unstructured":"Lutz, C.: NExpTime-complete description logics with concrete domains. In: Gor\u00e9, R., Leitsch, , A., Nipkow, T. (eds.) Proceedings of the International Joint Conference on Automated Reasoning (IJCAR\u00a02001), no. 2083 in Lecture Notes in Artificial Intelligence, pp. 45\u201360. Springer, Siena (2001)","DOI":"10.1007\/3-540-45744-5_5"},{"key":"9626_CR64","unstructured":"Lutz, C.: Adding numbers to the $$\\cal{SHIQ}$$ description logic\u2014First results. In: Proceedings of the 8th International Conference on Principles of Knowledge Representation and Reasoning (KR\u00a02002), pp. 191\u2013202. Morgan Kaufmann, Los Altos (2002)"},{"issue":"1\u20133","key":"9626_CR65","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. Automated Reason. 38(1\u20133), 227\u2013259 (2007)","journal-title":"J. Automated Reason."},{"issue":"15","key":"9626_CR66","doi-asserted-by":"publisher","first-page":"1599","DOI":"10.1016\/j.disc.2011.01.024","volume":"311","author":"D Macpherson","year":"2011","unstructured":"Macpherson, D.: A survey of homogeneous structures. Discret. Math. 311(15), 1599\u20131634 (2011)","journal-title":"Discret. Math."},{"key":"9626_CR67","unstructured":"Mottet, A., Bodirsky, M.: A dichotomy for first-order reducts of unary structures. Logical Methods in Computer Science 14 (2018)"},{"key":"9626_CR68","doi-asserted-by":"publisher","first-page":"94","DOI":"10.1016\/j.aim.2014.08.008","volume":"267","author":"PP Pach","year":"2014","unstructured":"Pach, P.P., Pinsker, M., Pluh\u00e1r, G., Pongr\u00e1cz, A., Szab\u00f3, C.: Reducts of the random partial order. Adv. Math. 267, 94\u2013120 (2014)","journal-title":"Adv. Math."},{"key":"9626_CR69","unstructured":"Pan, J.Z., Horrocks, I.: Reasoning in the $$\\cal{SHOQ} (D_n)$$ description logic. In: Horrocks, I., Tessaris, S. (eds.) Proceedings of the 2002 Description Logic Workshop (DL\u00a02002), CEUR Workshop Proceedings, vol.\u00a053. CEUR-WS.org (2002)"},{"key":"9626_CR70","unstructured":"Randell, D.A., Cui, Z., Cohn, A.G.: A spatial logic based on regions and connection. In: Proceedings of the 3rd International Conference on the Principles of Knowledge Representation and Reasoning (KR\u201992), pp. 165\u2013176. Morgan Kaufmann, Los Altos (1992)"},{"key":"9626_CR71","unstructured":"Schild, K.: A correspondence theory for terminological logics: preliminary report. In: Proceedings of the 12th International Joint Conference on Artificial Intelligence (IJCAI\u201991), pp. 466\u2013471 (1991)"},{"key":"9626_CR72","doi-asserted-by":"crossref","unstructured":"Zhuk, D.: A proof of CSP dichotomy conjecture. In: C.\u00a0Umans (ed.) 58th IEEE Annual Symposium on Foundations of Computer Science (FOCS 2017), pp. 331\u2013342. IEEE Computer Society (2017)","DOI":"10.1109\/FOCS.2017.38"}],"container-title":["Journal of Automated Reasoning"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10817-022-09626-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10817-022-09626-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10817-022-09626-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,23]],"date-time":"2024-09-23T18:41:31Z","timestamp":1727116891000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10817-022-09626-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,5,4]]},"references-count":72,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2022,8]]}},"alternative-id":["9626"],"URL":"https:\/\/doi.org\/10.1007\/s10817-022-09626-2","relation":{},"ISSN":["0168-7433","1573-0670"],"issn-type":[{"type":"print","value":"0168-7433"},{"type":"electronic","value":"1573-0670"}],"subject":[],"published":{"date-parts":[[2022,5,4]]},"assertion":[{"value":"28 April 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 February 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 May 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}