{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,20]],"date-time":"2025-09-20T20:35:50Z","timestamp":1758400550248},"publisher-location":"Cham","reference-count":19,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319452753"},{"type":"electronic","value":"9783319452760"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-319-45276-0_1","type":"book-chapter","created":{"date-parts":[[2016,8,25]],"date-time":"2016-08-25T08:18:04Z","timestamp":1472113084000},"page":"1-17","source":"Crossref","is-referenced-by-count":5,"title":["On the Complexity of Evaluating Regular Path Queries over Linear Existential Rules"],"prefix":"10.1007","author":[{"given":"Meghyn","family":"Bienvenu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Micha\u00ebl","family":"Thomazo","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,8,26]]},"reference":[{"key":"1_CR1","unstructured":"Baget, J., Lecl\u00e8re, M., Mugnier, M., Salvat, E.: Extending decidable cases for rules with existential variables. In: Proceedings of IJCAI, pp. 677\u2013682 (2009)"},{"key":"1_CR2","unstructured":"Baget, J., Bienvenu, M., Mugnier, M., Rocher, S.: Combining existential rules and transitivity: next steps. In: Proceedings of IJCAI, pp. 2720\u20132726 (2015)"},{"key":"1_CR3","unstructured":"Bienvenu, M., Calvanese, D., Ortiz, M., \u0160imkus, M.: Nested regular path queries in description logics. In: Proceedings of KR (2014)"},{"key":"1_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"218","DOI":"10.1007\/978-3-319-21768-0_9","volume-title":"Reasoning Web. Web Logic Rules","author":"M Bienvenu","year":"2015","unstructured":"Bienvenu, M., Ortiz, M.: Ontology-mediated query answering with data-tractable description logics. In: Faber, W., Paschke, A. (eds.) Reasoning Web 2015. LNCS, vol. 9203, pp. 218\u2013307. Springer, Heidelberg (2015)"},{"key":"1_CR5","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1613\/jair.4577","volume":"53","author":"M Bienvenu","year":"2015","unstructured":"Bienvenu, M., Ortiz, M., Simkus, M.: Regular path queries in lightweight description logics: complexity and algorithms. J. Artif. Intell. Res. (JAIR) 53, 315\u2013374 (2015)","journal-title":"J. Artif. Intell. Res. (JAIR)"},{"key":"1_CR6","unstructured":"Bourhis, P., Kr\u00f6tzsch, M., Rudolph, S.: How to best nest regular path queries. In: Proceedings of DL, pp. 404\u2013415 (2014)"},{"key":"1_CR7","unstructured":"Cal\u00ec, A., Gottlob, G., Kifer, M.: Taming the infinite chase: query answering under expressive relational constraints. In: Proceedings of KR, pp. 70\u201380 (2008)"},{"key":"1_CR8","unstructured":"Calvanese, D., Eiter, T., Ortiz, M.: Answering regular path queries in expressive description logics: an automata-theoretic approach. In: Proceedings of AAAI, pp. 391\u2013396 (2007)"},{"key":"1_CR9","unstructured":"Calvanese, D., Eiter, T., Ortiz, M.: Regular path queries in expressive description logics with nominals. In: Proceedings of IJCAI, pp. 714\u2013720 (2009)"},{"key":"1_CR10","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1016\/j.ic.2014.04.002","volume":"237","author":"D Calvanese","year":"2014","unstructured":"Calvanese, D., Eiter, T., Ortiz, M.: Answering regular path queries in expressive description logics via alternating tree-automata. Inf. Comput. 237, 12\u201355 (2014)","journal-title":"Inf. Comput."},{"key":"1_CR11","doi-asserted-by":"crossref","unstructured":"Florescu, D., Levy, A., Suciu, D.: Query containment for conjunctive queries with regular expressions. In: Proceedings of PODS (1998)","DOI":"10.1145\/275487.275503"},{"issue":"1","key":"1_CR12","doi-asserted-by":"crossref","first-page":"104","DOI":"10.1016\/S0890-5401(03)00012-9","volume":"183","author":"G Gottlob","year":"2003","unstructured":"Gottlob, G., Papadimitriou, C.H.: On the complexity of single-rule datalog queries. Inf. Comput. 183(1), 104\u2013122 (2003)","journal-title":"Inf. Comput."},{"key":"1_CR13","doi-asserted-by":"crossref","first-page":"741","DOI":"10.1613\/jair.3949","volume":"47","author":"BC Grau","year":"2013","unstructured":"Grau, B.C., Horrocks, I., Kr\u00f6tzsch, M., Kupke, C., Magka, D., Motik, B., Wang, Z.: Acyclicity notions for existential rules and their application to query answering in ontologies. J. Artif. Intell. Res. (JAIR) 47, 741\u2013808 (2013)","journal-title":"J. Artif. Intell. Res. (JAIR)"},{"issue":"1","key":"1_CR14","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1016\/0022-0000(84)90081-3","volume":"28","author":"DS Johnson","year":"1984","unstructured":"Johnson, D.S., Klug, A.C.: Testing containment of conjunctive queries under functional and inclusion dependencies. J. Comput. Syst. Sci. 28(1), 167\u2013189 (1984)","journal-title":"J. Comput. Syst. Sci."},{"key":"1_CR15","doi-asserted-by":"crossref","unstructured":"Kostylev, E.V., Reutter, J.L., Vrgoc, D.: XPath for DL ontologies. In: Proceedings of AAAI (2015)","DOI":"10.1609\/aaai.v29i1.9396"},{"issue":"4","key":"1_CR16","doi-asserted-by":"crossref","first-page":"455","DOI":"10.1145\/320107.320115","volume":"4","author":"D Maier","year":"1979","unstructured":"Maier, D., Mendelzon, A.O., Sagiv, Y.: Testing implications of data dependencies. ACM Trans. Database Syst. 4(4), 455\u2013469 (1979)","journal-title":"ACM Trans. Database Syst."},{"key":"1_CR17","doi-asserted-by":"crossref","unstructured":"Marnette, B.: Generalized schema-mappings: from termination to tractability. In: Proceedings of PODS, pp. 13\u201322 (2009)","DOI":"10.1145\/1559795.1559799"},{"key":"1_CR18","unstructured":"Ortiz, M., Rudolph, S., \u0160imkus, M.: Query answering in the Horn fragments of the description logics $$\\cal {SHOIQ}$$ and $$\\cal {SROIQ}$$ . In: Proceedings of IJCAI (2011)"},{"key":"1_CR19","doi-asserted-by":"crossref","first-page":"645","DOI":"10.1613\/jair.4457","volume":"51","author":"G Stefanoni","year":"2014","unstructured":"Stefanoni, G., Motik, B., Kr\u00f6tzsch, M., Rudolph, S.: The complexity of answering conjunctive and navigational queries over OWL 2 EL knowledge bases. J. Artif. Intell. Res. (JAIR) 51, 645\u2013705 (2014)","journal-title":"J. Artif. Intell. Res. (JAIR)"}],"container-title":["Lecture Notes in Computer Science","Web Reasoning and Rule Systems"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-45276-0_1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,7,7]],"date-time":"2022-07-07T01:00:15Z","timestamp":1657155615000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-45276-0_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783319452753","9783319452760"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-45276-0_1","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]}}}