{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,11]],"date-time":"2026-03-11T01:32:22Z","timestamp":1773192742346,"version":"3.50.1"},"reference-count":48,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2005,3,1]],"date-time":"2005-03-01T00:00:00Z","timestamp":1109635200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2005,3]]},"abstract":"<jats:p>\n            We study the complexity of two central XML processing problems. The first is XPath 1.0 query processing, which has been shown to be in PTIME in previous work. We prove that both the data complexity and the query complexity of XPath 1.0 fall into lower (highly parallelizable) complexity classes, while the combined complexity is PTIME-hard. Subsequently, we study the sources of this hardness and identify a large and practically important fragment of XPath 1.0 for which the combined complexity is LOGCFL-complete and, therefore, in the highly parallelizable complexity class NC\n            <jats:sup>2<\/jats:sup>\n            . The second problem is the complexity of validating XML documents against various typing schemes like Document Type Definitions (DTDs), XML Schema Definitions (XSDs), and tree automata, both with respect to data and to combined complexity. For data complexity, we prove that validation is in LOGSPACE and depends crucially on how XML data is represented. For the combined complexity, we show that the complexity ranges from LOGSPACE to LOGCFL, depending on the typing scheme.\n          <\/jats:p>","DOI":"10.1145\/1059513.1059520","type":"journal-article","created":{"date-parts":[[2005,8,3]],"date-time":"2005-08-03T08:30:55Z","timestamp":1123057855000},"page":"284-335","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":52,"title":["The complexity of XPath query evaluation and XML typing"],"prefix":"10.1145","volume":"52","author":[{"given":"Georg","family":"Gottlob","sequence":"first","affiliation":[{"name":"Technische Universit\u00e4t Wien, Wien, Austria"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christoph","family":"Koch","sequence":"additional","affiliation":[{"name":"Technische Universit\u00e4t Wien, Wien, Austria"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Reinhard","family":"Pichler","sequence":"additional","affiliation":[{"name":"Technische Universit\u00e4t Wien, Wien, Austria"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Luc","family":"Segoufin","sequence":"additional","affiliation":[{"name":"INRIA, France"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2005,3]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/871816.871875"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(71)90706-6"},{"key":"e_1_2_1_3_1","first-page":"61","article-title":"The division breakthroughs","volume":"74","author":"Allender E.","year":"2001","unstructured":"Allender , E. 2001 . The division breakthroughs . The Computational Complexity Column, EATCS Bull. 74 , 61 -- 77 .]] Allender, E. 2001. The division breakthroughs. The Computational Complexity Column, EATCS Bull. 74, 61--77.]]","journal-title":"The Computational Complexity Column, EATCS Bull."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(89)90052-5"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(90)90022-D"},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the 7th International Conference on Database Theory (ICDT'99)","volume":"1540","author":"Beeri C.","unstructured":"Beeri , C. , and Milo , T . 1999. Schemas for integration and translation of structured and semi-structured data . In Proceedings of the 7th International Conference on Database Theory (ICDT'99) . Lecture Notes in Computer Science , vol. 1540 . Springer-Verlag, New York, 296--313.]] Beeri, C., and Milo, T. 1999. Schemas for integration and translation of structured and semi-structured data. In Proceedings of the 7th International Conference on Database Theory (ICDT'99). Lecture Notes in Computer Science, vol. 1540. Springer-Verlag, New York, 296--313.]]"},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the 31st International Colloquium on Automata, Languages and Programming (ICALP).]]","author":"Bojanczyk M.","unstructured":"Bojanczyk , M. , and Colcombet , T . 2004. TWA cannot be determinized . In Proceedings of the 31st International Colloquium on Automata, Languages and Programming (ICALP).]] Bojanczyk, M., and Colcombet, T. 2004. TWA cannot be determinized. In Proceedings of the 31st International Colloquium on Automata, Languages and Programming (ICALP).]]"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/0218038"},{"key":"e_1_2_1_9_1","volume-title":"Tech. Rep. HKUST-TCSC-2001-05","author":"Br\u00fcggemann-Klein A.","year":"2001","unstructured":"Br\u00fcggemann-Klein , A. , Murata , M. , and Wood , D . 2001 . Regular tree and regular hedge languages over non-ranked alphabets: Version 1, April 3, 2001. Tech. Rep. HKUST-TCSC-2001-05 , Hong Kong University of Science and Technology, Hong Kong SAR, China. (Available at ftp:\/\/ftp11.informatik.tu-muenchen.de\/pub\/misc\/caterpillars\/.)]] Br\u00fcggemann-Klein, A., Murata, M., and Wood, D. 2001. Regular tree and regular hedge languages over non-ranked alphabets: Version 1, April 3, 2001. Tech. Rep. HKUST-TCSC-2001-05, Hong Kong University of Science and Technology, Hong Kong SAR, China. (Available at ftp:\/\/ftp11.informatik.tu-muenchen.de\/pub\/misc\/caterpillars\/.)]]"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/28395.28409"},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the 3rd International Workshop on the Web and Databases (WebDB). Lecture Note in Computer Science.","volume":"1997","author":"Chamberlin D.","unstructured":"Chamberlin , D. , Robie , J. , and Florescu , D . 2000. Quilt: An XML query language for heterogeneous data sources . In Proceedings of the 3rd International Workshop on the Web and Databases (WebDB). Lecture Note in Computer Science. vol. 1997 . Springer-Verlag, New York, 1--25.]] Chamberlin, D., Robie, J., and Florescu, D. 2000. Quilt: An XML query language for heterogeneous data sources. In Proceedings of the 3rd International Workshop on the Web and Databases (WebDB). Lecture Note in Computer Science. vol. 1997. Springer-Verlag, New York, 1--25.]]"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/276304.276321"},{"key":"e_1_2_1_13_1","unstructured":"Comon H. Dauchet M. Gilleron R. Jacquemard F. Lugiez D. Tison S. and Tommasi M. 1999. Tree automata techniques and applications. Available at http:\/\/www.grappa.univ-lille3.fr\/tata.]]  Comon H. Dauchet M. Gilleron R. Jacquemard F. Lugiez D. Tison S. and Tommasi M. 1999. Tree automata techniques and applications. Available at http:\/\/www.grappa.univ-lille3.fr\/tata.]]"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(87)90018-6"},{"key":"e_1_2_1_15_1","doi-asserted-by":"crossref","unstructured":"Engelfriet J. and Hoogeboom H. J. 1999. Tree-walking pebble automata. In Jewels Are Forever Contributions to Theoretical Computer Science in Honor of Arto Salomaa J. Karhumki H. Maurer G. Paun and G.Rozenberg Eds. Springer-Verlag New York 72--83.]]   Engelfriet J. and Hoogeboom H. J. 1999. Tree-walking pebble automata. In Jewels Are Forever Contributions to Theoretical Computer Science in Honor of Arto Salomaa J. Karhumki H. Maurer G. Paun and G.Rozenberg Eds. Springer-Verlag New York 72--83.]]","DOI":"10.1007\/978-3-642-60207-8_7"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/310955.310961"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1485"},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the 28th International Conference on Very Large Data Bases (VLDB'02)","author":"Gottlob G.","unstructured":"Gottlob , G. , Koch , C. , and Pichler , R . 2002. Efficient algorithms for processing XPath queries . In Proceedings of the 28th International Conference on Very Large Data Bases (VLDB'02) . 95--106.]] Gottlob, G., Koch, C., and Pichler, R. 2002. Efficient algorithms for processing XPath queries. In Proceedings of the 28th International Conference on Very Large Data Bases (VLDB'02). 95--106.]]"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/773153.773171"},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the 19th IEEE International Conference on Data Engineering (ICDE'03)","author":"Gottlob G.","unstructured":"Gottlob , G. , Koch , C. , and Pichler , R . 2003b. XPath query evaluation: Improving time and space efficiency . In Proceedings of the 19th IEEE International Conference on Data Engineering (ICDE'03) . IEEE Computer Society Press, Los Alamitos, Calif., 379--390.]] Gottlob, G., Koch, C., and Pichler, R. 2003b. XPath query evaluation: Improving time and space efficiency. In Proceedings of the 19th IEEE International Conference on Data Engineering (ICDE'03). IEEE Computer Society Press, Los Alamitos, Calif., 379--390.]]"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/382780.382783"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/203244"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/1710842.1710848"},{"key":"e_1_2_1_24_1","volume-title":"Handbook of Theoretical Computer Science","author":"Johnson D. S.","unstructured":"Johnson , D. S. 1990. A catalog of complexity classes . In Handbook of Theoretical Computer Science , J. van Leeuwen, Ed. Vol. 1. Elsevier Science Publishers B.V. , Amsterdam, The Netherlands, Chapt. 2, 67--161.]] Johnson, D. S. 1990. A catalog of complexity classes. In Handbook of Theoretical Computer Science, J. van Leeuwen, Ed. Vol. 1. Elsevier Science Publishers B.V., Amsterdam, The Netherlands, Chapt. 2, 67--161.]]"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(75)80050-X"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/129712.129750"},{"key":"e_1_2_1_27_1","series-title":"Lecture Notes in Computer Science","volume-title":"Proceedings of the Rewriting Techniques and Applications (RTA'01)","author":"Lohrey M.","unstructured":"Lohrey , M. 2001. On the parallel complexity of tree automata . In Proceedings of the Rewriting Techniques and Applications (RTA'01) . Lecture Notes in Computer Science , vol. 2051 . Springer-Verlag , New York , 201--215.]] Lohrey, M. 2001. On the parallel complexity of tree automata. In Proceedings of the Rewriting Techniques and Applications (RTA'01). Lecture Notes in Computer Science, vol. 2051. Springer-Verlag, New York, 201--215.]]"},{"key":"e_1_2_1_28_1","unstructured":"Lyons R. 2001. Turing machine markup language. http:\/\/www.unidex.com\/turing\/.]]  Lyons R. 2001. Turing machine markup language. http:\/\/www.unidex.com\/turing\/.]]"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/321406.321411"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.5555\/647852.737555"},{"key":"e_1_2_1_31_1","volume-title":"Proceedings of the Workshop on XML-Based Data Management (XMLDM'02)","author":"Olteanu D.","year":"2001","unstructured":"Olteanu , D. , Meuss , H. , Furche , T. , and Bry , F . 2002. XPath: Looking forward . In Proceedings of the Workshop on XML-Based Data Management (XMLDM'02) . (A full version, Technical Report PMS-FB- 2001 -17, is available at http:\/\/www.pms.ifi.lmu.de\/publikationen\/PMS-FB\/PMS-FB-2002-4.pdf).]] Olteanu, D., Meuss, H., Furche, T., and Bry, F. 2002. XPath: Looking forward. In Proceedings of the Workshop on XML-Based Data Management (XMLDM'02). (A full version, Technical Report PMS-FB-2001-17, is available at http:\/\/www.pms.ifi.lmu.de\/publikationen\/PMS-FB\/PMS-FB-2002-4.pdf).]]"},{"key":"e_1_2_1_32_1","volume-title":"Computational Complexity","author":"Papadimitriou C. H.","unstructured":"Papadimitriou , C. H. 1994. Computational Complexity . Addison-Wesley , Reading Mass .]] Papadimitriou, C. H. 1994. Computational Complexity. Addison-Wesley, Reading Mass.]]"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/335168.335173"},{"key":"e_1_2_1_34_1","volume-title":"Proceedings of the 9th International Conference on Database Theory (ICDT'03)","volume":"2572","author":"Papakonstantinou Y.","unstructured":"Papakonstantinou , Y. , and Vianu , V . 2003. Incremental validation of XML documents . In Proceedings of the 9th International Conference on Database Theory (ICDT'03) . Lecture Notes in Computer Science , vol. 2572 . Springer-Verlag, New York, 47--63.]] Papakonstantinou, Y., and Vianu, V. 2003. Incremental validation of XML documents. In Proceedings of the 9th International Conference on Database Theory (ICDT'03). Lecture Notes in Computer Science, vol. 2572. Springer-Verlag, New York, 47--63.]]"},{"key":"e_1_2_1_35_1","volume-title":"Eds","author":"Rozenberg G.","year":"1997","unstructured":"Rozenberg , G. , and Salomaa , A. , Eds . 1997 . Handbook of Formal Languages. Springer-Verlag , New York.]] Rozenberg, G., and Salomaa, A., Eds. 1997. Handbook of Formal Languages. Springer-Verlag, New York.]]"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(80)90036-7"},{"key":"e_1_2_1_37_1","unstructured":"SAX Project Collaboration. 2004. Simple API for XML. Available at http:\/\/www.saxproject.org\/.]]  SAX Project Collaboration. 2004. Simple API for XML. Available at http:\/\/www.saxproject.org\/.]]"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/773153.773170"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/543613.543622"},{"key":"e_1_2_1_40_1","volume-title":"Proceedings of the 8th International Workshop on Database Programming Languages (DBPL'01)","volume":"2397","author":"Suciu D.","year":"2001","unstructured":"Suciu , D. 2001 . Typechecking for semistructured data . In Proceedings of the 8th International Workshop on Database Programming Languages (DBPL'01) . Lecture Notes in Computer Science , vol. 2397 . Springer-Verlag, New York, 1--20.]] Suciu, D. 2001. Typechecking for semistructured data. In Proceedings of the 8th International Workshop on Database Programming Languages (DBPL'01). Lecture Notes in Computer Science, vol. 2397. Springer-Verlag, New York, 1--20.]]"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-08353-7_172"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/322077.322083"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/800070.802186"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(91)90020-6"},{"key":"e_1_2_1_45_1","volume-title":"Introduction to circuit complexity","author":"Vollmer H.","unstructured":"Vollmer , H. 1999. Introduction to circuit complexity . Springer .]] Vollmer, H. 1999. Introduction to circuit complexity. Springer.]]"},{"key":"e_1_2_1_46_1","unstructured":"Wadler P. 2000. Two semantics for XPath. Draft paper available at http:\/\/www.research.avayalabs.com\/user\/wadler\/.]]  Wadler P. 2000. Two semantics for XPath. Draft paper available at http:\/\/www.research.avayalabs.com\/user\/wadler\/.]]"},{"key":"e_1_2_1_47_1","unstructured":"World Wide Web Consortium. 1999. XML path language (XPath) recommendation. http:\/\/www. w3c.org\/TR\/xpath\/.]]  World Wide Web Consortium. 1999. XML path language (XPath) recommendation. http:\/\/www. w3c.org\/TR\/xpath\/.]]"},{"key":"e_1_2_1_48_1","unstructured":"World Wide Web Consortium. 2004. Document object model. Available at http:\/\/www.w3c.org\/dom level 1 specification available at http:\/\/www.w3.org\/TR\/REC-DOM-Level-1\/.]]  World Wide Web Consortium. 2004. Document object model. Available at http:\/\/www.w3c.org\/dom level 1 specification available at http:\/\/www.w3.org\/TR\/REC-DOM-Level-1\/.]]"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1059513.1059520","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1059513.1059520","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T21:37:03Z","timestamp":1750282623000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1059513.1059520"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,3]]},"references-count":48,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2005,3]]}},"alternative-id":["10.1145\/1059513.1059520"],"URL":"https:\/\/doi.org\/10.1145\/1059513.1059520","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,3]]},"assertion":[{"value":"2005-03-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}