{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T06:39:52Z","timestamp":1725518392826},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540710691"},{"type":"electronic","value":"9783540710707"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-71070-7_16","type":"book-chapter","created":{"date-parts":[[2008,8,29]],"date-time":"2008-08-29T05:56:30Z","timestamp":1219989390000},"page":"179-193","source":"Crossref","is-referenced-by-count":46,"title":["The Complexity of Conjunctive Query Answering in Expressive Description Logics"],"prefix":"10.1007","author":[{"given":"Carsten","family":"Lutz","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"16_CR1","volume-title":"The Description Logic Handbook","author":"F. Baader","year":"2003","unstructured":"Baader, F., McGuiness, D.L., Nardi, D., Patel-Schneider, P.: The Description Logic Handbook. Cambridge University Press, Cambridge (2003)"},{"key":"16_CR2","doi-asserted-by":"crossref","unstructured":"Calvanese, D., De Giacomo, G., Lenzerini, M.: On the decidability of query containment under constraints. In: Proc. of PODS 1998, pp. 149\u2013158 (1998)","DOI":"10.1145\/275487.275504"},{"key":"16_CR3","first-page":"260","volume-title":"Proc. of KR 2006","author":"D. Calvanese","year":"2006","unstructured":"Calvanese, D., Giacomo, G.D., Lembo, D., Lenzerini, M., Rosati, R.: Data complexity of query answering in description logics. In: Proc. of KR 2006, pp. 260\u2013270. AAAI Press, Menlo Park (2006)"},{"key":"16_CR4","volume-title":"Proc. of AAAI 2007","author":"D. Calvanese","year":"2007","unstructured":"Calvanese, D., Eiter, T., Ortiz, M.: Answering regular path queries in expressive description logics: an automata-theoretic approach. In: Proc. of AAAI 2007. AAAI Press, Menlo Park (2007)"},{"issue":"1","key":"16_CR5","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1145\/322234.322243","volume":"28","author":"A.K. Chandra","year":"1981","unstructured":"Chandra, A.K., Kozen, D.C., Stockmeyer, L.J.: Alternation. Journal of the ACM\u00a028(1), 114\u2013133 (1981)","journal-title":"Journal of the ACM"},{"key":"16_CR6","unstructured":"Glimm, B., Horrocks, I., Sattler, U.: Conjunctive query entailment for \n                      \n                        \n                      \n                      $\\mathcal{SHOQ}$\n                    . In: Proc. of DL 2007. CEUR-WS, vol. 250 (2007)"},{"key":"16_CR7","doi-asserted-by":"crossref","first-page":"150","DOI":"10.1613\/jair.2372","volume":"31","author":"B. Glimm","year":"2008","unstructured":"Glimm, B., Lutz, C., Horrocks, I., Sattler, U.: Answering conjunctive queries in the \n                      \n                        \n                      \n                      $\\mathcal{SHIQ}$\n                     description logic. JAIR\u00a031, 150\u2013197 (2008)","journal-title":"JAIR"},{"key":"16_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1007\/3-540-48242-3_11","volume-title":"Logic Programming and Automated Reasoning","author":"I. Horrocks","year":"1999","unstructured":"Horrocks, I., Sattler, U., Tobies, S.: Practical reasoning for expressive description logics. In: Ganzinger, H., McAllester, D., Voronkov, A. (eds.) LPAR 1999. LNCS, vol.\u00a01705, pp. 161\u2013180. Springer, Heidelberg (1999)"},{"key":"16_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"482","DOI":"10.1007\/10721959_39","volume-title":"Automated Deduction - CADE-17","author":"I. Horrocks","year":"2000","unstructured":"Horrocks, I., Sattler, U., Tobies, S.: Reasoning with individuals for the description logic SHIQ. In: McAllester, D. (ed.) CADE 2000. LNCS, vol.\u00a01831, pp. 482\u2013496. Springer, Heidelberg (2000)"},{"key":"16_CR10","volume-title":"Proc. of AAAI 2000","author":"I. Horrocks","year":"2000","unstructured":"Horrocks, I., Tessaris, S.: A conjunctive query language for description logic ABoxes. In: Proc. of AAAI 2000. AAAI Press, Menlo Park (2000)"},{"key":"16_CR11","unstructured":"Hustadt, U., Motik, B., Sattler, U.: Data complexity of reasoning in very expressive description logics. In: Proc. of IJCAI 2005, pp. 466\u2013471. Professional Book Center (2005)"},{"key":"16_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"310","DOI":"10.1007\/978-3-540-76298-0_23","volume-title":"The Semantic Web","author":"M. Kr\u00f6tzsch","year":"2007","unstructured":"Kr\u00f6tzsch, M., Rudolph, S., Hitzler, P.: Conjunctive queries for a tractable fragment of OWL 1.1. In: Aberer, K., Choi, K.-S., Noy, N., Allemang, D., Lee, K.-I., Nixon, L., Golbeck, J., Mika, P., Maynard, D., Mizoguchi, R., Schreiber, G., Cudr\u00e9-Mauroux, P. (eds.) ISWC 2007. LNCS, vol.\u00a04825, pp. 310\u2013323. Springer, Heidelberg (2007)"},{"key":"16_CR13","unstructured":"Lutz, C.: The Complexity of Reasoning with Concrete Domains. PhD thesis, LuFG Theoretical Computer Science, RWTH Aachen, Germany (2002)"},{"key":"16_CR14","doi-asserted-by":"crossref","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. Journal of Artificial Intelligence Research (JAIR)\u00a023, 667\u2013726 (2005)","journal-title":"Journal of Artificial Intelligence Research (JAIR)"},{"key":"16_CR15","unstructured":"Lutz, C.: Inverse roles make conjunctive queries hard. In: Proc. of DL 2007, CEUR-WS vol. 250 (2007), \n                      \n                        http:\/\/lat.inf.tu-dresden.de\/~clu\/papers\/"},{"key":"16_CR16","unstructured":"Lutz, C.: Two upper bounds for conjunctive query answering in \n                      \n                        \n                      \n                      $\\mathcal{SHIQ}$\n                    . In: Proc. of DL 2008, CEUR-WS (2008), \n                      \n                         http:\/\/lat.inf.tu-dresden.de\/~clu\/papers\/"},{"key":"16_CR17","volume-title":"Proc. of AAAI 2006","author":"M. Ortiz","year":"2006","unstructured":"Ortiz, M., Calvanese, D., Eiter, T.: Characterizing data complexity for conjunctive query answering in expressive description logics. In: Proc. of AAAI 2006. AAAI Press, Menlo Park (2006)"},{"key":"16_CR18","volume-title":"Proc. of AAAI 2008","author":"M. Ortiz","year":"2008","unstructured":"Ortiz, M., \u0160imkus, M., Eiter, T.: Worst-case optimal conjunctive query answering for an expressive description logic without inverses. In: Proc. of AAAI 2008. AAAI Press, Menlo Park (2008)"},{"key":"16_CR19","unstructured":"Ortiz, M., \u0160imkus, M., Eiter, T.: Conjunctive query answering in \n                      \n                        \n                      \n                      $\\mathcal{SH}$\n                     using knots. In: Proc. of DL 2008. CEUR WS (2008)"},{"key":"16_CR20","first-page":"265","volume":"2","author":"A. Schaerf","year":"1993","unstructured":"Schaerf, A.: On the complexity of the instance checking problem in concept languages with existential quantification. JIIS\u00a02, 265\u2013278 (1993)","journal-title":"JIIS"},{"key":"16_CR21","unstructured":"Rosati, R.: On conjunctive query answering in \n                      \n                        \n                      \n                      $\\mathcal{EL}$\n                    . In: Proc. of DL 2007. CEUR-WS, vol.\u00a0250 (2007)"},{"key":"16_CR22","unstructured":"Tobies, S.: Complexity Results and Practical Algorithms for Logics in Knowledge Representation. PhD thesis, RWTH Aachen (2001)"}],"container-title":["Lecture Notes in Computer Science","Automated Reasoning"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-71070-7_16.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,3]],"date-time":"2021-05-03T00:36:28Z","timestamp":1620002188000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-71070-7_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540710691","9783540710707"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-71070-7_16","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[]}}