{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,16]],"date-time":"2025-09-16T20:15:46Z","timestamp":1758053746666,"version":"3.44.0"},"publisher-location":"Cham","reference-count":65,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783032041661","type":"print"},{"value":"9783032041678","type":"electronic"}],"license":[{"start":{"date-parts":[[2025,9,15]],"date-time":"2025-09-15T00:00:00Z","timestamp":1757894400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,9,15]],"date-time":"2025-09-15T00:00:00Z","timestamp":1757894400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2026]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>The <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$\\mathcal{E}\\mathcal{L}$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>E<\/mml:mi>\n                    <mml:mi>L<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> family of description logics facilitates efficient polynomial-time reasoning and has been standardized as the profile OWL\u00a02\u00a0EL of the Web Ontology Language. <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$\\mathcal{E}\\mathcal{L}$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>E<\/mml:mi>\n                    <mml:mi>L<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> can represent and reason not only with symbolic knowledge but also with concrete knowledge expressed by numbers, strings, and other concrete datatypes. Such concrete domains must be convex to avoid introducing disjunctions \u201cthrough the backdoor.\u201d However, existing concrete domains provide only limited utility. In order to overcome this issue, we introduce a novel form of concrete domains based on semi-lattices. They are convex by design and can thus be integrated into Horn-DLs such as <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$\\mathcal{E}\\mathcal{L}$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>E<\/mml:mi>\n                    <mml:mi>L<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>. Moreover, they allow for FBoxes to express dependencies between concrete features. We describe four instantiations concerned with real intervals, 2D-polygons, regular languages, and graphs.<\/jats:p>","DOI":"10.1007\/978-3-032-04167-8_3","type":"book-chapter","created":{"date-parts":[[2025,9,14]],"date-time":"2025-09-14T22:03:53Z","timestamp":1757887433000},"page":"40-60","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Reasoning in\u00a0OWL 2 EL with\u00a0Hierarchical Concrete Domains"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0219-0330","authenticated-orcid":false,"given":"Francesco","family":"Kriegel","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,9,15]]},"reference":[{"key":"3_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1007\/978-3-031-45072-3_4","volume-title":"Rules and Reasoning","author":"C Alrabbaa","year":"2023","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.) RuleML+RR 2023. LNCS, vol. 14244, pp. 54\u201369. Springer, Cham (2023). https:\/\/doi.org\/10.1007\/978-3-031-45072-3_4"},{"key":"3_CR2","doi-asserted-by":"publisher","unstructured":"Baader, F., Borgwardt, S., Lippmann, M.: Query rewriting for DL-lite with $$n$$-ary concrete domains. In: Proceedings of the 26th International Joint Conference on Artificial Intelligence (IJCAI), pp. 786\u2013792 (2017). https:\/\/doi.org\/10.24963\/IJCAI.2017\/109","DOI":"10.24963\/IJCAI.2017\/109"},{"key":"3_CR3","doi-asserted-by":"publisher","unstructured":"Baader, F., Bortoli, F.D.: The abstract expressive power of first-order and description logics with concrete domains. In: Proceedings of the 39th ACM\/SIGAPP Symposium on Applied Computing (SAC), pp. 754\u2013761 (2024). https:\/\/doi.org\/10.1145\/3605098.3635984","DOI":"10.1145\/3605098.3635984"},{"key":"3_CR4","unstructured":"Baader, F., Brandt, S., Lutz, C.: Pushing the $$\\cal{EL}$$ envelope. In: Proceedings of the 19th International Joint Conference on Artificial Intelligence (IJCAI), pp. 364\u2013369 (2005). http:\/\/ijcai.org\/Proceedings\/05\/Papers\/0372.pdf"},{"key":"3_CR5","unstructured":"Baader, F., Brandt, S., Lutz, C.: Pushing the $$\\cal{EL}$$ envelope further. In: Proceedings of the 4th OWLED Workshop on OWL: Experiences and Directions. CEUR Workshop Proceedings (2008). https:\/\/ceur-ws.org\/Vol-496\/owled2008dc%5C_paper%5C_3.pdf"},{"issue":"3","key":"3_CR6","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1145\/3699839.3699840","volume":"24","author":"F Baader","year":"2024","unstructured":"Baader, F., De Bortoli, F.: Logics with concrete domains: first-order properties, abstract expressive power, and (un)decidability. SIGAPP Appl. Comput. Rev. 24(3), 5\u201317 (2024). https:\/\/doi.org\/10.1145\/3699839.3699840","journal-title":"SIGAPP Appl. Comput. Rev."},{"key":"3_CR7","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), pp. 452\u2013457 (1991). http:\/\/ijcai.org\/Proceedings\/91-1\/Papers\/070.pdf"},{"key":"3_CR8","series-title":"Lecture Notes in Computer Science (Lecture Notes in Artificial Intelligence)","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1007\/978-3-030-79876-5_18","volume-title":"Automated Deduction \u2013 CADE 28","author":"F Baader","year":"2021","unstructured":"Baader, F., Koopmann, P., Kriegel, F., Nuradiansyah, A.: Computing optimal repairs of quantified\u00a0ABoxes w.r.t. static $$\\cal{EL}$$ TBoxes. In: Platzer, A., Sutcliffe, G. (eds.) CADE 2021. LNCS (LNAI), vol. 12699, pp. 309\u2013326. Springer, Cham (2021). https:\/\/doi.org\/10.1007\/978-3-030-79876-5_18"},{"key":"3_CR9","doi-asserted-by":"publisher","unstructured":"Baader, F., Kriegel, F.: Pushing optimal ABox repair from $$\\cal{EL}$$ towards more expressive Horn-DLs. In: Proceedings of the 19th International Conference on Principles of Knowledge Representation and Reasoning (KR), pp. 22\u201332 (2022). https:\/\/doi.org\/10.24963\/kr.2022\/3","DOI":"10.24963\/kr.2022\/3"},{"key":"3_CR10","series-title":"Lecture Notes in Computer Science (Lecture Notes in Artificial Intelligence)","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1007\/3-540-45653-8_15","volume-title":"Logic for Programming, Artificial Intelligence, and Reasoning","author":"F Baader","year":"2001","unstructured":"Baader, F., K\u00fcsters, R.: Unification in a description logic with transitive closure of roles. In: Nieuwenhuis, R., Voronkov, A. (eds.) LPAR 2001. LNCS (LNAI), vol. 2250, pp. 217\u2013232. Springer, Heidelberg (2001). https:\/\/doi.org\/10.1007\/3-540-45653-8_15"},{"key":"3_CR11","series-title":"Lecture Notes in Computer Science (Lecture Notes in Artificial Intelligence)","doi-asserted-by":"publisher","first-page":"194","DOI":"10.1007\/978-3-030-75775-5_14","volume-title":"Logics in Artificial Intelligence","author":"F Baader","year":"2021","unstructured":"Baader, F., Rydval, J.: An algebraic view on p-admissible concrete domains for lightweight description logics. In: Faber, W., Friedrich, G., Gebser, M., Morak, M. (eds.) JELIA 2021. LNCS (LNAI), vol. 12678, pp. 194\u2013209. Springer, Cham (2021). https:\/\/doi.org\/10.1007\/978-3-030-75775-5_14"},{"key":"3_CR12","series-title":"Lecture Notes in Computer Science (Lecture Notes in Artificial Intelligence)","doi-asserted-by":"publisher","first-page":"413","DOI":"10.1007\/978-3-030-51074-9_24","volume-title":"Automated Reasoning","author":"F Baader","year":"2020","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"},{"issue":"3","key":"3_CR13","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."},{"issue":"8","key":"3_CR14","doi-asserted-by":"publisher","first-page":"979","DOI":"10.1016\/S0306-4379(03)00003-6","volume":"28","author":"F Baader","year":"2003","unstructured":"Baader, F., Sattler, U.: Description logics with aggregates and concrete domains. Inf. Syst. 28(8), 979\u20131004 (2003). https:\/\/doi.org\/10.1016\/S0306-4379(03)00003-6","journal-title":"Inf. Syst."},{"key":"3_CR15","unstructured":"Baget, J., Lecl\u00e8re, M., Mugnier, M., Salvat, E.: Extending decidable cases for rules with existential variables. In: Proceedings of the 21st International Joint Conference on Artificial Intelligence (IJCAI), pp. 677\u2013682 (2009). http:\/\/ijcai.org\/Proceedings\/09\/Papers\/118.pdf"},{"key":"3_CR16","doi-asserted-by":"publisher","unstructured":"Bonchi, F., Pous, D.: Checking NFA equivalence with bisimulations up to congruence. In: Proceedings of the 40th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL), pp. 457\u2013468 (2013). See also [29] and [17]. https:\/\/doi.org\/10.1145\/2429069.2429124","DOI":"10.1145\/2429069.2429124"},{"issue":"2","key":"3_CR17","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1145\/2713167","volume":"58","author":"F Bonchi","year":"2015","unstructured":"Bonchi, F., Pous, D.: Hacking nondeterminism with induction and coinduction. Commun. ACM 58(2), 87\u201395 (2015). https:\/\/doi.org\/10.1145\/2713167","journal-title":"Commun. ACM"},{"key":"3_CR18","unstructured":"Borgwardt, S., Bortoli, F.D., Koopmann, P.: The precise complexity of reasoning in $$\\cal{ALC}$$ with $$\\omega $$-admissible concrete domains. In: Proceedings of the 37th International Workshop on Description Logics (DL). CEUR Workshop Proceedings (2024). https:\/\/ceur-ws.org\/Vol-3739\/paper-1.pdf"},{"issue":"2","key":"3_CR19","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1006\/INCO.1997.2688","volume":"140","author":"A Br\u00fcggemann-Klein","year":"1998","unstructured":"Br\u00fcggemann-Klein, A., Wood, D.: One-unambiguous regular languages. Inf. Comput. 140(2), 229\u2013253 (1998). https:\/\/doi.org\/10.1006\/INCO.1997.2688","journal-title":"Inf. Comput."},{"key":"3_CR20","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: Proceedings of the 22nd European Conference on Artificial Intelligence (ECAI). Frontiers in Artificial Intelligence and Applications, pp. 1440\u20131448 (2016). https:\/\/doi.org\/10.3233\/978-1-61499-672-9-1440","DOI":"10.3233\/978-1-61499-672-9-1440"},{"key":"3_CR21","doi-asserted-by":"publisher","unstructured":"Chandra, A.K., Merlin, P.M.: Optimal implementation of conjunctive queries in relational data bases. In: Proceedings of the 9th Annual ACM Symposium on Theory of Computing (STOC), pp. 77\u201390 (1977). https:\/\/doi.org\/10.1145\/800105.803397","DOI":"10.1145\/800105.803397"},{"key":"3_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"56","DOI":"10.1007\/3-540-62222-5_36","volume-title":"Database Theory \u2014 ICDT \u201997","author":"C Chekuri","year":"1997","unstructured":"Chekuri, C., Rajaraman, A.: Conjunctive query containment revisited. In: Afrati, F., Kolaitis, P. (eds.) ICDT 1997. LNCS, vol. 1186, pp. 56\u201370. Springer, Heidelberg (1997). https:\/\/doi.org\/10.1007\/3-540-62222-5_36"},{"key":"3_CR23","unstructured":"Cocke, J.: Programming languages and their compilers: preliminary notes, USA (1969)"},{"issue":"2","key":"3_CR24","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1145\/274363.274364","volume":"17","author":"G Greiner","year":"1998","unstructured":"Greiner, G., Hormann, K.: Efficient clipping of arbitrary polygons. ACM Trans. Graph. 17(2), 71\u201383 (1998). https:\/\/doi.org\/10.1145\/274363.274364","journal-title":"ACM Trans. Graph."},{"key":"3_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1007\/978-3-540-70583-3_4","volume-title":"Automata, Languages and Programming","author":"H Gruber","year":"2008","unstructured":"Gruber, H., Holzer, M.: Finite automata, digraph connectivity, and regular expression size. In: Aceto, L., Damg\u00e5rd, I., Goldberg, L.A., Halld\u00f3rsson, M.M., Ing\u00f3lfsd\u00f3ttir, A., Walukiewicz, I. (eds.) ICALP 2008. LNCS, vol. 5126, pp. 39\u201350. Springer, Heidelberg (2008). https:\/\/doi.org\/10.1007\/978-3-540-70583-3_4"},{"issue":"3","key":"3_CR26","doi-asserted-by":"publisher","first-page":"351","DOI":"10.1093\/LOGCOM\/9.3.351","volume":"9","author":"V Haarslev","year":"1999","unstructured":"Haarslev, V., Lutz, C., M\u00f6ller, R.: A description logic with concrete domains and a role-forming predicate operator. J. Log. Comput. 9(3), 351\u2013384 (1999). https:\/\/doi.org\/10.1093\/LOGCOM\/9.3.351","journal-title":"J. Log. Comput."},{"key":"3_CR27","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1007\/3-540-45744-5_4","volume-title":"IJCAR 2001","author":"V Haarslev","year":"2001","unstructured":"Haarslev, V., M\u00f6ller, R., Wessel, M.: The description logic $$\\cal{ALCNH}_{R+}$$ extended with concrete domains: a practically motivated approach. In: Gor\u00e9, R., Leitsch, A., Nipkow, T. (eds.) IJCAR 2001. LNCS, vol. 2083, pp. 29\u201344. Springer, Heidelberg (2001). https:\/\/doi.org\/10.1007\/3-540-45744-5_4"},{"key":"3_CR28","doi-asserted-by":"crossref","unstructured":"Hales, T.C.: The Jordan curve theorem, formally and informally. Am. Math. Mon. 114(10), 882\u2013894 (2007). http:\/\/www.jstor.org\/stable\/27642361","DOI":"10.1080\/00029890.2007.11920481"},{"issue":"2","key":"3_CR29","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1145\/2701001","volume":"58","author":"TA Henzinger","year":"2015","unstructured":"Henzinger, T.A., Raskin, J.: The equivalence problem for finite automata: technical perspective. Commun. ACM 58(2), 86 (2015). https:\/\/doi.org\/10.1145\/2701001","journal-title":"Commun. ACM"},{"key":"3_CR30","doi-asserted-by":"publisher","unstructured":"Hickey, T.J., Ju, Q., van Emden, M.H.: Interval arithmetic: from principles to implementation. 48(5), 1038\u20131068 (2001). https:\/\/doi.org\/10.1145\/502102.502106","DOI":"10.1145\/502102.502106"},{"key":"3_CR31","unstructured":"Hopcroft, J.E., Karp, R.M.: A linear algorithm for testing equivalence of finite automata. Technical report, TR71-114, Cornell University (1971). https:\/\/hdl.handle.net\/1813\/5958"},{"issue":"6","key":"3_CR32","doi-asserted-by":"publisher","first-page":"1795","DOI":"10.1016\/J.JCSS.2011.12.003","volume":"78","author":"D Hovland","year":"2012","unstructured":"Hovland, D.: The inclusion problem for regular expressions. J. Comput. Syst. Sci. 78(6), 1795\u20131813 (2012). https:\/\/doi.org\/10.1016\/J.JCSS.2011.12.003","journal-title":"J. Comput. Syst. Sci."},{"key":"3_CR33","doi-asserted-by":"publisher","unstructured":"Jiang, S., Song, Z., Weinstein, O., Zhang, H.: A faster algorithm for solving general LPs. In: Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC), pp. 823\u2013832 (2021). https:\/\/doi.org\/10.1145\/3406325.3451058","DOI":"10.1145\/3406325.3451058"},{"key":"3_CR34","doi-asserted-by":"publisher","unstructured":"Jones, N.D.: Space-bounded reducibility among combinatorial problems. J. Comput. Syst. Sci. 11(1), 68\u201385 (1975). See also [34]. https:\/\/doi.org\/10.1016\/S0022-0000(77)80009-3","DOI":"10.1016\/S0022-0000(77)80009-3"},{"key":"3_CR35","doi-asserted-by":"crossref","unstructured":"Jones, N.D.: Space-Bounded Reducibility among Combinatorial Problems. J. Comput. Syst. Sci. 11(1), 68\u201385 (1975). See also [34]. https:\/\/doi.org\/10.1016\/S0022-0000(75)80050-X","DOI":"10.1016\/S0022-0000(75)80050-X"},{"key":"3_CR36","doi-asserted-by":"publisher","unstructured":"Jordan, C.: Cours d\u2019analyse de l\u2019\u00c9cole Polytechnique\u2014Volume 3: Calcul int\u00e9gral, \u00e9quations diff\u00e9rentielles, Paris (1887). https:\/\/doi.org\/10.1017\/CBO9781107300064","DOI":"10.1017\/CBO9781107300064"},{"issue":"1\u20133","key":"3_CR37","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1016\/S0304-3975(02)00830-7","volume":"302","author":"G Karakostas","year":"2003","unstructured":"Karakostas, G., Lipton, R.J., Viglas, A.: On the complexity of intersecting finite state automata and NL versus NP. Theoret. Comput. Sci. 302(1\u20133), 257\u2013274 (2003). https:\/\/doi.org\/10.1016\/S0304-3975(02)00830-7","journal-title":"Theoret. Comput. Sci."},{"key":"3_CR38","series-title":"The IBM Research Symposia Series","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of Computer Computations","author":"RM Karp","year":"1972","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W., Bohlinger, J.D. (eds.) Complexity of Computer Computations. The IBM Research Symposia Series, pp. 85\u2013103. Springer, Boston (1972). https:\/\/doi.org\/10.1007\/978-1-4684-2001-2_9"},{"key":"3_CR39","doi-asserted-by":"crossref","unstructured":"Kasami, T.: An Efficient Recognition and Syntax-Analysis Algorithm for Context-Free Languages. Report R-257, Coordinated Science Laboratory, University of Illinois, Urbana, Illinois (1966). https:\/\/doi.org\/10.1007\/978-1-4684-2001-2_9","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"3_CR40","unstructured":"Kazakov, Y., Klinov, P.: Advancing ELK: not only performance matters. In: Proceedings of the 28th International Workshop on Description Logics (DL). CEUR Workshop Proceedings (2015). http:\/\/hdl.handle.net\/2142\/74304"},{"key":"3_CR41","unstructured":"Kazakov, Y., Kr\u00f6tzsch, M., Siman\u010d\u00edk, F.: Practical reasoning with nominals in the $$\\cal{EL}$$ family of description logics. In: Proceedings of the 13th International Conference on Principles of Knowledge Representation and Reasoning (KR) (2012). https:\/\/ceur-ws.org\/Vol-1350\/paper-27.pdf"},{"issue":"1","key":"3_CR42","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/S10817-013-9296-3","volume":"53","author":"Y Kazakov","year":"2014","unstructured":"Kazakov, Y., Kr\u00f6tzsch, M., Siman\u010d\u00edk, F.: The incredible ELK - from polynomial procedures to efficient reasoning with $$\\cal{EL} $$ ontologies. J. Autom. Reason. 53(1), 1\u201361 (2014). https:\/\/doi.org\/10.1007\/S10817-013-9296-3","journal-title":"J. Autom. Reason."},{"key":"3_CR43","doi-asserted-by":"publisher","unstructured":"Kozen, D.: Lower bounds for natural proof systems. In: Proceedings of the 18th Annual Symposium on Foundations of Computer Science (FOCS), pp. 254\u2013266 (1977). https:\/\/doi.org\/10.1109\/SFCS.1977.16","DOI":"10.1109\/SFCS.1977.16"},{"key":"3_CR44","doi-asserted-by":"publisher","unstructured":"Kriegel, F.: Beyond optimal: interactive identification of better-than-optimal repairs. In: Proceedings of the 40th ACM\/SIGAPP Symposium on Applied Computing (SAC), pp. 1019\u20131026 (2025). https:\/\/doi.org\/10.1145\/3672608.3707750","DOI":"10.1145\/3672608.3707750"},{"key":"3_CR45","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1007\/978-3-031-15791-2_11","volume-title":"KI 2022","author":"F Kriegel","year":"2022","unstructured":"Kriegel, F.: Optimal fixed-premise repairs of $$\\cal{EL} $$ TBoxes. In: Bergmann, R., Malburg, L., Rodermund, S.C., Timm, I.J. (eds.) KI 2022. LNCS, vol. 13404, pp. 115\u2013130. Springer, Cham (2022). https:\/\/doi.org\/10.1007\/978-3-031-15791-2_11"},{"key":"3_CR46","doi-asserted-by":"publisher","unstructured":"Kriegel, F.: Reasoning in OWL 2 EL with Hierarchical Concrete Domains (Extended Version). LTCS-Report 25-04, Chair of Automata Theory, Institute of Theoretical Computer Science, Technische Universit\u00e4t Dresden (2025). https:\/\/doi.org\/10.25368\/2025.127","DOI":"10.25368\/2025.127"},{"key":"3_CR47","doi-asserted-by":"publisher","unstructured":"Kr\u00f6tzsch, M., Rudolph, S., Hitzler, P.: Complexities of Horn description logics. ACM Trans. Comput. Logic 14(1), 2:1\u20132:36 (2013). https:\/\/doi.org\/10.1145\/2422085.2422087","DOI":"10.1145\/2422085.2422087"},{"key":"3_CR48","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1016\/J.TCS.2016.02.027","volume":"627","author":"K Losemann","year":"2016","unstructured":"Losemann, K., Martens, W., Niewerth, M.: Closure properties and descriptional complexity of deterministic regular expressions. Theoret. Comput. Sci. 627, 54\u201370 (2016). https:\/\/doi.org\/10.1016\/J.TCS.2016.02.027","journal-title":"Theoret. Comput. Sci."},{"issue":"4","key":"3_CR49","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. Log. 5(4), 669\u2013705 (2004). https:\/\/doi.org\/10.1145\/1024922.1024925","journal-title":"ACM Trans. Comput. Log."},{"key":"3_CR50","doi-asserted-by":"crossref","unstructured":"Lutz, C.: The complexity of description logics with concrete domains. Doctoral thesis, RWTH Aachen University, Germany (2002). https:\/\/doi.org\/10.1145\/1024922.1024925","DOI":"10.1145\/1024922.1024925"},{"key":"3_CR51","doi-asserted-by":"publisher","first-page":"667","DOI":"10.1613\/JAIR.1542","volume":"23","author":"C Lutz","year":"2005","unstructured":"Lutz, C., Areces, C., Horrocks, I., Sattler, U.: Keys, nominals, and concrete domains. J. Artif. Intell. Res. 23, 667\u2013726 (2005). https:\/\/doi.org\/10.1613\/JAIR.1542","journal-title":"J. Artif. Intell. Res."},{"issue":"1\u20133","key":"3_CR52","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\u20133), 227\u2013259 (2007). https:\/\/doi.org\/10.1007\/S10817-006-9049-7","journal-title":"J. Autom. Reason."},{"issue":"4","key":"3_CR53","doi-asserted-by":"publisher","first-page":"427","DOI":"10.1007\/S10817-011-9235-0","volume":"47","author":"D Magka","year":"2011","unstructured":"Magka, D., Kazakov, Y., Horrocks, I.: Tractable extensions of the description logic $$\\cal{EL} $$ with numerical datatypes. J. Autom. Reason. 47(4), 427\u2013450 (2011). https:\/\/doi.org\/10.1007\/S10817-011-9235-0","journal-title":"J. Autom. Reason."},{"key":"3_CR54","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1016\/J.ADVENGSOFT.2013.04.004","volume":"64","author":"F Mart\u0131nez","year":"2013","unstructured":"Mart\u0131nez, F., Og\u00e1yar, C.J., Jim\u00e9nez, J., Ruiz, A.J.R.: A simple algorithm for Boolean operations on polygons. Adv. Eng. Softw. 64, 11\u201319 (2013). https:\/\/doi.org\/10.1016\/J.ADVENGSOFT.2013.04.004","journal-title":"Adv. Eng. Softw."},{"issue":"2","key":"3_CR55","doi-asserted-by":"publisher","first-page":"221","DOI":"10.2307\/2272123","volume":"42","author":"GF McNulty","year":"1977","unstructured":"McNulty, G.F.: Fragments of first order logic, I: universal Horn logic. J. Symb. Log. 42(2), 221\u2013237 (1977). https:\/\/doi.org\/10.2307\/2272123","journal-title":"J. Symb. Log."},{"issue":"4","key":"3_CR56","doi-asserted-by":"publisher","first-page":"384","DOI":"10.1016\/0146-664X(82)90023-5","volume":"19","author":"J O\u2019Rourke","year":"1982","unstructured":"O\u2019Rourke, J., Chien, C., Olson, T., Naddor, D.: A new linear algorithm for intersecting convex polygons. Comput. Graph. Image Process. 19(4), 384\u2013391 (1982). https:\/\/doi.org\/10.1016\/0146-664X(82)90023-5","journal-title":"Comput. Graph. Image Process."},{"key":"3_CR57","unstructured":"Ortiz, M., Rudolph, S., \u0160imkus, M.: Worst-case optimal reasoning for the Horn-DL fragments of OWL 1 and 2. In: Proceedings of the 12th International Conference on Principles of Knowledge Representation and Reasoning (KR) (2010). http:\/\/aaai.org\/ocs\/index.php\/KR\/KR2010\/paper\/view\/1296"},{"key":"3_CR58","unstructured":"Pan, J.Z., Horrocks, I.: Reasoning in the $$\\cal{SHOQ}(\\textbf{D}_{\\textbf{n}})$$ description logic. In: Proceedings of the 15th International Workshop on Description Logics (DL). CEUR Workshop Proceedings (2002). https:\/\/ceur-ws.org\/Vol-53\/Pan-Horrocks-shoqdn-2002.ps"},{"key":"3_CR59","unstructured":"Rydval, J.: Using model theory to find decidable and tractable description logics with concrete domains. Doctoral thesis, Dresden University of Technology, Germany (2022). https:\/\/nbn-resolving.org\/urn:nbn:de:bsz:14-qucosa2-799074"},{"key":"3_CR60","unstructured":"Shamos, M.I.: Computational geometry. Ph.D. thesis, Yale University, United States (1978). http:\/\/euro.ecom.cmu.edu\/people\/faculty\/mshamos\/1978ShamosThesis.pdf"},{"key":"3_CR61","doi-asserted-by":"publisher","unstructured":"Stockmeyer, L.J., Meyer, A.R.: Word problems requiring exponential time: preliminary report. In: Proceedings of the 5th Annual ACM Symposium on Theory of Computing (STOC), pp. 1\u20139 (1973). https:\/\/doi.org\/10.1145\/800125.804029","DOI":"10.1145\/800125.804029"},{"issue":"2","key":"3_CR62","doi-asserted-by":"publisher","first-page":"118","DOI":"10.1007\/BF01898355","volume":"1","author":"GT Toussaint","year":"1985","unstructured":"Toussaint, G.T.: A simple linear algorithm for intersecting convex polygons. Vis. Comput. 1(2), 118\u2013123 (1985). https:\/\/doi.org\/10.1007\/BF01898355","journal-title":"Vis. Comput."},{"issue":"7","key":"3_CR63","doi-asserted-by":"publisher","first-page":"56","DOI":"10.1145\/129902.129906","volume":"35","author":"BR Vatti","year":"1992","unstructured":"Vatti, B.R.: A generic solution to polygon clipping. Commun. ACM 35(7), 56\u201363 (1992). https:\/\/doi.org\/10.1145\/129902.129906","journal-title":"Commun. ACM"},{"issue":"2","key":"3_CR64","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/S0019-9958(67)80007-X","volume":"10","author":"DH Younger","year":"1967","unstructured":"Younger, D.H.: Recognition and parsing of context-free languages in time $$n^3$$. Inf. Control 10(2), 189\u2013208 (1967). https:\/\/doi.org\/10.1016\/S0019-9958(67)80007-X","journal-title":"Inf. Control"},{"issue":"2","key":"3_CR65","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1016\/0304-3975(92)00011-F","volume":"125","author":"S Yu","year":"1994","unstructured":"Yu, S., Zhuang, Q., Salomaa, K.: The state complexities of some basic operations on regular languages. Theoret. Comput. Sci. 125(2), 315\u2013328 (1994). https:\/\/doi.org\/10.1016\/0304-3975(92)00011-F","journal-title":"Theoret. Comput. Sci."}],"container-title":["Lecture Notes in Computer Science","Frontiers of Combining Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-032-04167-8_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,14]],"date-time":"2025-09-14T22:03:56Z","timestamp":1757887436000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-04167-8_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,9,15]]},"ISBN":["9783032041661","9783032041678"],"references-count":65,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-04167-8_3","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,9,15]]},"assertion":[{"value":"15 September 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"FroCoS","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Symposium on Frontiers of Combining Systems","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Reykjavik","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Iceland","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":"27 September 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"3 October 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"15","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"frocos2025","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/icetcs.github.io\/frocos-itp-tableaux25\/frocos\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}