{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T17:20:04Z","timestamp":1740158404490,"version":"3.37.3"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2020,3,14]],"date-time":"2020-03-14T00:00:00Z","timestamp":1584144000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,3,14]],"date-time":"2020-03-14T00:00:00Z","timestamp":1584144000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["389792660"],"award-info":[{"award-number":["389792660"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["K\u00fcnstl Intell"],"published-print":{"date-parts":[[2020,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We investigate the impact that general concept inclusions and role-value maps have on the complexity and decidability of reasoning in the description logic<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mathcal{FL}_0$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:msub><mml:mi>FL<\/mml:mi><mml:mn>0<\/mml:mn><\/mml:msub><\/mml:math><\/jats:alternatives><\/jats:inline-formula>. On the one hand, we give a more direct proof for ExpTime-hardness of subsumption w.r.t. general concept inclusions in<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mathcal{FL}_0$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:msub><mml:mi>FL<\/mml:mi><mml:mn>0<\/mml:mn><\/mml:msub><\/mml:math><\/jats:alternatives><\/jats:inline-formula>. On the other hand, we determine restrictions on role-value maps that ensure decidability of subsumption, but we also show undecidability for the cases where these restrictions are not satisfied.<\/jats:p>","DOI":"10.1007\/s13218-020-00651-0","type":"journal-article","created":{"date-parts":[[2020,3,14]],"date-time":"2020-03-14T14:02:21Z","timestamp":1584194541000},"page":"291-301","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Role-Value Maps and General Concept Inclusions in the Minimal Description Logic with Value Restrictions or Revisiting Old Skeletons in the DL Cupboard"],"prefix":"10.1007","volume":"34","author":[{"given":"Franz","family":"Baader","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Cl\u00e9ment","family":"Th\u00e9ron","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,3,14]]},"reference":[{"key":"651_CR1","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1007\/BF02127747","volume":"18","author":"F Baader","year":"1996","unstructured":"Baader F (1996) Using automata theory for characterizing the semantics of terminological cycles. Ann Math Artif Intell 18:175\u2013219","journal-title":"Ann Math Artif Intell"},{"key":"651_CR2","unstructured":"Baader F (2003) Description logic terminology. In: [6], pp. 485\u2013495"},{"key":"651_CR3","doi-asserted-by":"crossref","unstructured":"Baader F (2003) Restricted role-value-maps in a description logic with existential restrictions and terminological cycles. In: Calvanese D, De Giacomo G, Franconi E (eds) Proceedings of the 2003 description logic workshop (DL\u00a02003), CEUR Workshop Proceedings, vol 81. CEUR-WS.org","DOI":"10.25368\/2022.125"},{"key":"651_CR4","unstructured":"Baader F, Brandt S, Lutz C (2005) Pushing the $${\\cal{EL}}$$ envelope. In: Kaelbling LP, Saffiotti A (eds) Proceedings of the 19th international joint conference on artificial intelligence (IJCAI\u00a02005). Morgan Kaufmann, Los Altos, pp 364\u2013369"},{"key":"651_CR5","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF01051766","volume":"2","author":"F Baader","year":"1993","unstructured":"Baader F, B\u00fcrckert HJ, Nebel B, Nutt W, Smolka G (1993) On the expressivity of feature logics with negation, functional uncertainty, and sort equations. J Logic Lang Inf 2:1\u201318","journal-title":"J Logic Lang Inf"},{"volume-title":"The description logic handbook: theory, implementation, and applications","year":"2003","key":"651_CR6","unstructured":"Baader F, Calvanese D, McGuinness D, Nardi D, Patel-Schneider PF (eds) (2003) The description logic handbook: theory, implementation, and applications. Cambridge University Press, Cambridge"},{"key":"651_CR7","unstructured":"Baader F, Gil OF, Pensel M (2018) Standard and non-standard inferences in the description logic $$\\cal{FL}_0$$ using tree automata. In: Lee D, Steen A, Walsh T (eds) Proceedings of the 4th global conference on artificial intelligence (GCAI-2018), EPiC Series in Computing, vol 55. EasyChair, pp 1\u201314"},{"key":"651_CR8","doi-asserted-by":"crossref","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 (2017) An introduction to description logic. Cambridge University Press, Cambridge"},{"issue":"4","key":"651_CR9","first-page":"57","volume":"16","author":"F Baader","year":"2002","unstructured":"Baader F, Horrocks I, Sattler U (2002) Description logics for the semantic web. KI 16(4):57\u201359","journal-title":"KI"},{"issue":"1","key":"651_CR10","first-page":"25","volume":"24","author":"F Baader","year":"2010","unstructured":"Baader F, Lutz C, Turhan AY (2010) Small is again beautiful in description logics. KI 24(1):25\u201333","journal-title":"KI"},{"issue":"3","key":"651_CR11","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1006\/jsco.2000.0426","volume":"31","author":"F Baader","year":"2001","unstructured":"Baader F, Narendran P (2001) Unification of concept terms in description logics. J Symb Comput 31(3):277\u2013305","journal-title":"J Symb Comput"},{"key":"651_CR12","unstructured":"Baader F, Th\u00e9ron C (2019) Role-value maps and general concept inclusions in the description logic $${\\cal{FL}}_0$$. LTCS-Report 19-08, Chair of Automata Theory, Institute of Theoretical Computer Science, Technische Universit\u00e4t Dresden, Dresden, Germany. https:\/\/tu-dresden.de\/inf\/lat\/reports#BaTh-LTCS-19-08"},{"key":"651_CR13","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4613-9771-7","volume-title":"String-rewriting systems","author":"RV Book","year":"1993","unstructured":"Book RV, Otto F (1993) String-rewriting systems. Springer, New York"},{"key":"651_CR14","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1613\/jair.56","volume":"1","author":"A Borgida","year":"1994","unstructured":"Borgida A, Patel-Schneider PF (1994) A semantics and complete algorithm for subsumption in the CLASSIC description logic. J Artif Intell Res 1:277\u2013308","journal-title":"J Artif Intell Res"},{"key":"651_CR15","unstructured":"Brachman RJ, Levesque, HJ (1984) The tractability of subsumption in frame-based description languages. In: Proceedings of the 4th national conference on artificial intelligence (AAAI\u201984), pp 34\u201337"},{"volume-title":"Readings in knowledge representation","year":"1985","key":"651_CR16","unstructured":"Brachman RJ, Levesque HJ (eds) (1985) Readings in knowledge representation. Morgan Kaufmann, Los Altos"},{"issue":"2","key":"651_CR17","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1207\/s15516709cog0902_1","volume":"9","author":"RJ Brachman","year":"1985","unstructured":"Brachman RJ, Schmolze JG (1985) An overview of the KL-ONE knowledge representation system. Cogn Sci 9(2):171\u2013216","journal-title":"Cogn Sci"},{"key":"651_CR18","unstructured":"Donini FM, Lenzerini M, Nardi D, Nutt W (1991) The complexity of concept languages. In: Allen J, Fikes R, Sandewall E (eds) Proceedings of the 2nd international conference on the principles of knowledge representation and reasoning (KR\u201991). Morgan Kaufmann, Los Altos, pp 151\u2013162"},{"issue":"2","key":"651_CR19","first-page":"117","volume":"30","author":"B Glimm","year":"2016","unstructured":"Glimm B, Stuckenschmidt H (2016) 15 years of semantic web: an incomplete survey. KI 30(2):117\u2013130","journal-title":"KI"},{"issue":"6","key":"651_CR20","doi-asserted-by":"crossref","first-page":"1069","DOI":"10.1093\/bib\/bbv011","volume":"16","author":"R Hoehndorf","year":"2015","unstructured":"Hoehndorf R, Schofield PN, Gkoutos GV (2015) The role of ontologies in biological and biomedical research: a functional perspective. Brief Bioinform 16(6):1069\u20131080","journal-title":"Brief Bioinform"},{"key":"651_CR21","doi-asserted-by":"crossref","unstructured":"Hofmann M (2005) Proof-theoretic approach to description-logic. In: Panangaden P (ed) Proceedings of the 20th IEEE symposium on logic in computer science (LICS\u00a02005). IEEE Computer Society Press, pp 229\u2013237","DOI":"10.1109\/LICS.2005.38"},{"key":"651_CR22","unstructured":"Horrocks I, Kutz O, Sattler U (2006) The even more irresistible $${\\cal{SROIQ}}$$. In: Doherty P, Mylopoulos J, Welty CA (eds.) Proceedings of the 10th international conference on principles of knowledge representation and reasoning (KR\u00a02006). AAAI Press\/The MIT Press, Lake District, UK, pp 57\u201367"},{"key":"651_CR23","first-page":"3","volume":"4","author":"M Jurdzinski","year":"2008","unstructured":"Jurdzinski M, Sproston J, Laroussinie F (2008) Model checking probabilistic timed automata with one or two clocks. Logic Methods Comput Sci 4:3","journal-title":"Logic Methods Comput Sci"},{"key":"651_CR24","unstructured":"Kazakov Y (2008) $${\\cal{RIQ}}$$ and $${\\cal{SROIQ}}$$ are harder than $${\\cal{SHOIQ}}$$. In: Brewka G, Lang J (eds) Proceedings of the 11th international conference on principles of knowledge representation and reasoning (KR\u00a02008). AAAI Press, pp 274\u2013284"},{"key":"651_CR25","unstructured":"Kazakov Y, de\u00a0Nivelle H (2003) Subsumption of concepts in $${\\cal{FL}}_0$$ for (cyclic) terminologies with respect to descriptive semantics is PSPACE-complete. In: Proceedings of the 2003 description logic workshop (DL\u00a02003). CEUR electronic workshop proceedings. http:\/\/CEUR-WS.org\/Vol-81\/"},{"key":"#cr-split#-651_CR26.1","unstructured":"Minsky M (1975) A framework for representing knowledge. In: Haugeland J"},{"key":"#cr-split#-651_CR26.2","unstructured":"(ed) Mind design. The MIT Press (1981). A longer version appeared in the psychology of computer vision. Republished in [16]"},{"key":"651_CR27","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1016\/0004-3702(90)90087-G","volume":"43","author":"B Nebel","year":"1990","unstructured":"Nebel B (1990) Terminological reasoning is inherently intractable. Artif Intell 43:235\u2013249","journal-title":"Artif Intell"},{"key":"651_CR28","doi-asserted-by":"crossref","first-page":"410","DOI":"10.1002\/bs.3830120511","volume":"12","author":"MR Quillian","year":"1967","unstructured":"Quillian MR (1967) Word concepts: a theory and simulation of some basic capabilities. Behav Sci 12:410\u2013430 (Republished in [16])","journal-title":"Behav Sci"},{"key":"651_CR29","first-page":"216","volume-title":"Semantic information processing","author":"MR Quillian","year":"1968","unstructured":"Quillian MR (1968) Semantic memory. In: Minsky M (ed) Semantic information processing. The MIT Press, London, pp 216\u2013270"},{"key":"651_CR30","unstructured":"Schmidt-Schau\u00df M (1989) Subsumption in KL-ONE is undecidable. In: Brachman RJ, Levesque HJ, Reiter R (eds) Proceedings of the 1st international conference on the principles of knowledge representation and reasoning (KR\u201989). Morgan Kaufmann, Los Altos, pp 421\u2013431"},{"issue":"2","key":"651_CR31","doi-asserted-by":"crossref","first-page":"234","DOI":"10.1006\/inco.2000.2894","volume":"164","author":"I Walukiewicz","year":"2001","unstructured":"Walukiewicz I (2001) Pushdown processes: games and model-checking. Inf Comput 164(2):234\u2013263","journal-title":"Inf Comput"}],"container-title":["KI - K\u00fcnstliche Intelligenz"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s13218-020-00651-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s13218-020-00651-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s13218-020-00651-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,18]],"date-time":"2022-10-18T21:01:30Z","timestamp":1666126890000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s13218-020-00651-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,3,14]]},"references-count":32,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2020,9]]}},"alternative-id":["651"],"URL":"https:\/\/doi.org\/10.1007\/s13218-020-00651-0","relation":{},"ISSN":["0933-1875","1610-1987"],"issn-type":[{"type":"print","value":"0933-1875"},{"type":"electronic","value":"1610-1987"}],"subject":[],"published":{"date-parts":[[2020,3,14]]},"assertion":[{"value":"31 October 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 March 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 March 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}