{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,27]],"date-time":"2026-05-27T19:59:37Z","timestamp":1779911977104,"version":"3.53.1"},"reference-count":47,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2016,10,18]],"date-time":"2016-10-18T00:00:00Z","timestamp":1476748800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["MA 4938\/2-1"],"award-info":[{"award-number":["MA 4938\/2-1"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004359","name":"Vetenskapsr\u00e5det","doi-asserted-by":"publisher","award":["621-2011-6080"],"award-info":[{"award-number":["621-2011-6080"]}],"id":[{"id":"10.13039\/501100004359","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Acta Informatica"],"published-print":{"date-parts":[[2018,2]]},"DOI":"10.1007\/s00236-016-0282-1","type":"journal-article","created":{"date-parts":[[2016,10,18]],"date-time":"2016-10-18T15:44:47Z","timestamp":1476805487000},"page":"17-56","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Conjunctive query containment over trees using schema information"],"prefix":"10.1007","volume":"55","author":[{"given":"Henrik","family":"Bj\u00f6rklund","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Wim","family":"Martens","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Thomas","family":"Schwentick","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2016,10,18]]},"reference":[{"key":"282_CR1","doi-asserted-by":"crossref","unstructured":"Abiteboul, S., Bourhis, P., Muscholl, A., Wu, Z.: Recursive queries on trees and data trees. In: International Conference on Database Theory (ICDT), pp. 93\u2013104 (2013)","DOI":"10.1145\/2448496.2448509"},{"key":"282_CR2","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9781139060158","volume-title":"Foundations of Data Exchange","author":"M Arenas","year":"2014","unstructured":"Arenas, M., Barcel\u00f3, P., Libkin, L., Murlak, F.: Foundations of Data Exchange. Cambridge University Press, Cambridge (2014)"},{"issue":"1","key":"282_CR3","doi-asserted-by":"crossref","first-page":"4","DOI":"10.1145\/1870103.1870107","volume":"58","author":"P Barcel\u00f3","year":"2010","unstructured":"Barcel\u00f3, P., Libkin, L., Poggi, A., Sirangelo, C.: XML with incomplete information. J. ACM 58(1), 4 (2010)","journal-title":"J. ACM"},{"key":"282_CR4","doi-asserted-by":"crossref","unstructured":"Benedikt, M., Bourhis, P., Senellart, P.: Monadic datalog containment. In: International Colloquium on Automata, Languages, and Programming (ICALP), pp. 79\u201391 (2012)","DOI":"10.1007\/978-3-642-31585-5_11"},{"key":"282_CR5","doi-asserted-by":"publisher","unstructured":"Benedikt, M., Fan, W., Geerts, F.: XPath satisfiability in the presence of DTDs. J. ACM 55(2), Art. no. 8 (2008). doi: 10.1145\/1346330.1346333","DOI":"10.1145\/1346330.1346333"},{"key":"282_CR6","unstructured":"Berglund, A., Boag, S., Chamberlin, D., Fern\u00e1ndez, M.F., Kay, M., Robie, J., Sim\u00e9on, J.: XML path language (XPath) 2.0. Technical report, World Wide Web Consortium (2007). http:\/\/www.w3.org\/TR\/xpath20\/"},{"issue":"3","key":"282_CR7","doi-asserted-by":"crossref","first-page":"450","DOI":"10.1016\/j.jcss.2010.04.005","volume":"77","author":"H Bj\u00f6rklund","year":"2011","unstructured":"Bj\u00f6rklund, H., Martens, W., Schwentick, T.: Conjunctive query containment over trees. J. Comput. Syst. Sci. 77(3), 450\u2013472 (2011)","journal-title":"J. Comput. Syst. Sci."},{"key":"282_CR8","doi-asserted-by":"crossref","unstructured":"Bj\u00f6rklund, H., Martens, W., Schwentick, T.: Validity of tree pattern queries with respect to schema information. In: Mathematical Foundations of Computer Science (MFCS), pp. 171\u2013182 (2013)","DOI":"10.1007\/978-3-642-40313-2_17"},{"issue":"6","key":"282_CR9","doi-asserted-by":"crossref","first-page":"785","DOI":"10.1016\/j.jcss.2013.01.004","volume":"79","author":"M Bojanczyk","year":"2013","unstructured":"Bojanczyk, M., Kolodziejczyk, L.A., Murlak, F.: Solutions in XML data exchange. J. Comput. Syst. Sci. 79(6), 785\u2013815 (2013)","journal-title":"J. Comput. Syst. Sci."},{"key":"282_CR10","doi-asserted-by":"crossref","unstructured":"Bojanczyk, M., Murlak, F., Witkowski, A.: Containment of monadic datalog programs via bounded clique-width. In: International Colloquium on Automata, Languages, and Programming (ICALP), pp. 427\u2013439 (2015)","DOI":"10.1007\/978-3-662-47666-6_34"},{"key":"282_CR11","doi-asserted-by":"publisher","unstructured":"Bojanczyk, M., Muscholl, A., Schwentick, T., Segoufin, L.: Two-variable logic on data trees and XML reasoning. J. ACM 56(3), Art. no.13 (2009). doi: 10.1145\/1516512.1516515","DOI":"10.1145\/1516512.1516515"},{"issue":"2","key":"282_CR12","doi-asserted-by":"crossref","first-page":"182","DOI":"10.1006\/inco.1997.2695","volume":"142","author":"A Br\u00fcggemann-Klein","year":"1998","unstructured":"Br\u00fcggemann-Klein, A., Wood, D.: One-unambiguous regular languages. Inf. Comput. 142(2), 182\u2013206 (1998)","journal-title":"Inf. Comput."},{"issue":"1","key":"282_CR13","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1145\/322234.322243","volume":"28","author":"AK Chandra","year":"1981","unstructured":"Chandra, A.K., Kozen, D.C., Stockmeyer, L.J.: Alternation. J. ACM 28(1), 114\u2013133 (1981)","journal-title":"J. ACM"},{"key":"282_CR14","doi-asserted-by":"crossref","unstructured":"Chandra, A.K., Merlin, P.M.: Optimal implementation of conjunctive queries in relational data bases. In: STOC, pp. 77\u201390 (1977)","DOI":"10.1145\/800105.803397"},{"issue":"3","key":"282_CR15","doi-asserted-by":"crossref","first-page":"374","DOI":"10.1016\/0022-0000(86)90036-X","volume":"32","author":"BS Chlebus","year":"1986","unstructured":"Chlebus, B.S.: Domino-tiling games. J. Comput. Syst. Sci. 32(3), 374\u2013392 (1986)","journal-title":"J. Comput. Syst. Sci."},{"key":"282_CR16","unstructured":"Clark, J., Murata, M.: Relax NG specification (2001). http:\/\/www.relaxng.org\/spec-20011203.html"},{"key":"282_CR17","doi-asserted-by":"crossref","unstructured":"Czerwinski, W., David, C., Losemann, K., Martens, W.: Deciding definability by deterministic regular expressions. In: International Conference on Foundations of Software Science and Computation Structures (FOSSACS), pp 289\u2013304. Springer, Berlin (2013)","DOI":"10.1007\/978-3-642-37075-5_19"},{"key":"282_CR18","doi-asserted-by":"crossref","unstructured":"Czerwinski, W., Martens, W., Niewerth, M., Parys, P.: Minimization of tree pattern queries. In: Symposium on Principles of Database Systems (PODS), pp. 43\u201354 (2016)","DOI":"10.1145\/2902251.2902295"},{"key":"282_CR19","doi-asserted-by":"crossref","unstructured":"Czerwinski, W., Martens, W., Parys, P., Przybylko, M.: The (almost) complete guide to tree pattern containment. In: Symposium on Principles of Database Systems (PODS), pp. 117\u2013130 (2015)","DOI":"10.1145\/2745754.2745766"},{"key":"282_CR20","doi-asserted-by":"crossref","unstructured":"David, C.: Complexity of data tree patterns over XML documents. In: MFCS, pp. 278\u2013289 (2008)","DOI":"10.1007\/978-3-540-85238-4_22"},{"key":"282_CR21","doi-asserted-by":"crossref","unstructured":"David, C., Gheerbrant, A., Libkin, L., Martens, W.: Containment of pattern-based queries over data trees. In: International Conference on Database Theory (ICDT), pp. 201\u2013212 (2013)","DOI":"10.1145\/2448496.2448521"},{"key":"282_CR22","doi-asserted-by":"crossref","unstructured":"David, C., Hofman, P., Murlak, F., Pilipczuk, M.: Synthesizing transformations from XML schema mappings. In: International Conference on Database Theory (ICDT), pp. 61\u201371 (2014)","DOI":"10.1145\/2590773"},{"key":"282_CR23","doi-asserted-by":"crossref","unstructured":"David, C, Libkin, L., Murlak, F.: Certain answers for XML queries. In: Symposium on Principles of Database Systems (PODS), pp. 191\u2013202 (2010)","DOI":"10.1145\/1807085.1807112"},{"issue":"6","key":"282_CR24","doi-asserted-by":"crossref","first-page":"716","DOI":"10.1145\/602220.602222","volume":"49","author":"J\u00f6rg Flum","year":"2002","unstructured":"Flum, J\u00f6rg, Frick, Markus, Grohe, Martin: Query evaluation via tree-decompositions. J. ACM 49(6), 716\u2013752 (2002)","journal-title":"J. ACM"},{"issue":"1","key":"282_CR25","doi-asserted-by":"crossref","first-page":"50","DOI":"10.1016\/0022-0000(80)90004-5","volume":"20","author":"J Gallant","year":"1980","unstructured":"Gallant, J., Maier, D., Storer, J.A.: On finding minimal length superstrings. J. Comput. Syst. Sci. 20(1), 50\u201358 (1980)","journal-title":"J. Comput. Syst. Sci."},{"key":"282_CR26","doi-asserted-by":"crossref","unstructured":"Geerts, F., Fan, W.: Satisfiability of XPath queries with sibling axes. In: DBPL, pp. 122\u2013137 (2005)","DOI":"10.1007\/11601524_8"},{"key":"282_CR27","doi-asserted-by":"crossref","unstructured":"Gheerbrant, A., Libkin, L., Tan, T.: On the complexity of query answering over incomplete XML documents. In: ICDT, pp. 169\u2013181 (2012)","DOI":"10.1145\/2274576.2274595"},{"issue":"2","key":"282_CR28","doi-asserted-by":"crossref","first-page":"238","DOI":"10.1145\/1131342.1131345","volume":"53","author":"G Gottlob","year":"2006","unstructured":"Gottlob, G., Koch, C., Schulz, K.U.: Conjunctive queries over trees. J. ACM 53(2), 238\u2013272 (2006)","journal-title":"J. ACM"},{"key":"282_CR29","doi-asserted-by":"crossref","unstructured":"Hidders, J.: Satisfiability of XPath expressions. In: DBPL, pp. 21\u201336 (2003)","DOI":"10.1007\/978-3-540-24607-7_3"},{"key":"282_CR30","doi-asserted-by":"crossref","unstructured":"Kimelfeld, B., Sagiv, Y.: Revisiting redundancy and minimization in an XPath fragment. In: Extending Database Technology (EDBT), pp. 61\u201372 (2008)","DOI":"10.1145\/1353343.1353355"},{"issue":"2","key":"282_CR31","doi-asserted-by":"crossref","first-page":"302","DOI":"10.1006\/jcss.2000.1713","volume":"61","author":"PG Kolaitis","year":"2000","unstructured":"Kolaitis, P.G., Vardi, M.Y.: Conjunctive-query containment and constraint satisfaction. J. Comput. Syst. Sci. 61(2), 302\u2013332 (2000)","journal-title":"J. Comput. Syst. Sci."},{"key":"282_CR32","doi-asserted-by":"crossref","unstructured":"Lakshmanan, L.V.S., Ramesh, G., Wang, H., Zhao, Z.: On testing satisfiability of tree pattern queries. In: VLDB, pp. 120\u2013131 (2004)","DOI":"10.1016\/B978-012088469-8.50014-0"},{"key":"282_CR33","doi-asserted-by":"publisher","unstructured":"Lu, P., Bremer, J., Chen, H.: Deciding determinism of regular languages. Theory Comput. Syst. 57(1), 97\u2013139 (2015). doi: 10.1007\/s00224-014-9576-2","DOI":"10.1007\/s00224-014-9576-2"},{"issue":"1","key":"282_CR34","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1016\/j.tcs.2004.10.035","volume":"336","author":"W Martens","year":"2005","unstructured":"Martens, W., Neven, F.: On the complexity of typechecking top-down XML transformations. Theor. Comput. Sci. 336(1), 153\u2013180 (2005)","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"282_CR35","doi-asserted-by":"crossref","first-page":"1486","DOI":"10.1137\/080743457","volume":"39","author":"W Martens","year":"2009","unstructured":"Martens, W., Neven, F., Schwentick, T.: Complexity of decision problems for XML schemas and chain regular expressions. SIAM J. Comput. 39(4), 1486\u20131530 (2009)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"282_CR36","doi-asserted-by":"crossref","first-page":"770","DOI":"10.1145\/1166074.1166076","volume":"31","author":"W Martens","year":"2006","unstructured":"Martens, W., Neven, F., Schwentick, T., Bex, G.J.: Expressiveness and complexity of XML schema. ACM Trans. Database Syst. 31(3), 770\u2013813 (2006)","journal-title":"ACM Trans. Database Syst."},{"issue":"4","key":"282_CR37","doi-asserted-by":"crossref","first-page":"929","DOI":"10.1145\/1114244.1114247","volume":"30","author":"M Marx","year":"2005","unstructured":"Marx, M.: Conditional XPath. ACM TODS 30(4), 929\u2013959 (2005)","journal-title":"ACM TODS"},{"issue":"1","key":"282_CR38","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1145\/962446.962448","volume":"51","author":"G Miklau","year":"2004","unstructured":"Miklau, G., Suciu, D.: Containment and equivalence for a fragment of XPath. J. ACM 51(1), 2\u201345 (2004)","journal-title":"J. ACM"},{"key":"282_CR39","doi-asserted-by":"crossref","unstructured":"Murlak, F., Oginski, M., Przybylko, M.: Between tree patterns and conjunctive queries: Is there tractability beyond acyclicity? In: Mathematical Foundations of Computer Science (MFCS), pp. 705\u2013717 (2012)","DOI":"10.1007\/978-3-642-32589-2_61"},{"key":"282_CR40","doi-asserted-by":"publisher","unstructured":"Neven, F., Schwentick, T.: On the complexity of XPath containment in the presence of disjunction, DTDs, and variables. Log. Methods Comput. Sci. 2(3), Art. no. 1 (2006). doi: 10.2168\/LMCS-2(3:1)2006","DOI":"10.2168\/LMCS-2(3:1)2006"},{"issue":"4","key":"282_CR41","doi-asserted-by":"crossref","first-page":"264","DOI":"10.1090\/S0002-9904-1946-08555-9","volume":"52","author":"EL Post","year":"1946","unstructured":"Post, E.L.: A variant of a recursively unsolvable problem. Bull. AMS 52(4), 264\u2013268 (1946)","journal-title":"Bull. AMS"},{"issue":"2","key":"282_CR42","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1016\/0304-3975(81)90075-X","volume":"16","author":"KJ R\u00e4ih\u00e4","year":"1981","unstructured":"R\u00e4ih\u00e4, K.J., Ukkonen, E.: The shortest common supersequence problem over binary alphabet is NP-complete. Theor. Comput. Sci. 16(2), 187\u2013198 (1981)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"282_CR43","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/S0019-9958(75)90058-3","volume":"27","author":"M Takahashi","year":"1975","unstructured":"Takahashi, M.: Generalizations of regular sets and their application to a study of context-free languages. Inf. Control 27(1), 1\u201336 (1975)","journal-title":"Inf. Control"},{"key":"282_CR44","doi-asserted-by":"publisher","unstructured":"ten Cate, B., Lutz, C.: The complexity of query containment in expressive fragments of XPath 2. J. ACM 56(6), Art. no. 31 (2009). doi: 10.1145\/1568318.1568321","DOI":"10.1145\/1568318.1568321"},{"issue":"1","key":"282_CR45","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1007\/BF01691346","volume":"2","author":"James W Thatcher","year":"1968","unstructured":"Thatcher, James W., Wright, Jesse B.: Generalized finite automata theory with an application to a decision problem of second-order logic. Math. Syst. Theory 2(1), 57\u201381 (1968)","journal-title":"Math. Syst. Theory"},{"key":"282_CR46","doi-asserted-by":"crossref","unstructured":"Vardi, Moshe Y.: Reasoning about the past with two-way automata. In: Proceedings of the 25th International Colloquium on Automata, Languages and Programming (ICALP\u201998), Aalborg, Denmark, July 13\u201317, 1998, pp. 628\u2013641 (1998)","DOI":"10.1007\/BFb0055090"},{"key":"282_CR47","doi-asserted-by":"crossref","unstructured":"Wood, P.T.: Containment for XPath fragments under DTD constraints. In: ICDT, 2003. Full version, obtained through personal communication (2003)","DOI":"10.1007\/3-540-36285-1_20"}],"container-title":["Acta Informatica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00236-016-0282-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-016-0282-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-016-0282-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,8,20]],"date-time":"2023-08-20T14:03:44Z","timestamp":1692540224000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00236-016-0282-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,10,18]]},"references-count":47,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2018,2]]}},"alternative-id":["282"],"URL":"https:\/\/doi.org\/10.1007\/s00236-016-0282-1","relation":{},"ISSN":["0001-5903","1432-0525"],"issn-type":[{"value":"0001-5903","type":"print"},{"value":"1432-0525","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,10,18]]}}}