{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T00:26:34Z","timestamp":1761611194095},"publisher-location":"Berlin, Heidelberg","reference-count":28,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540692690"},{"type":"electronic","value":"9783540692706"}],"license":[{"start":{"date-parts":[[2006,1,1]],"date-time":"2006-01-01T00:00:00Z","timestamp":1136073600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11965893_18","type":"book-chapter","created":{"date-parts":[[2006,12,7]],"date-time":"2006-12-07T07:52:22Z","timestamp":1165477942000},"page":"254-268","source":"Crossref","is-referenced-by-count":25,"title":["Exact XML Type Checking in Polynomial Time"],"prefix":"10.1007","author":[{"given":"Sebastian","family":"Maneth","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Thomas","family":"Perst","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Helmut","family":"Seidl","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"18_CR1","doi-asserted-by":"crossref","unstructured":"Boag, S., Chamberlin, D., et al. (eds.): XQuery 1.0: An XML Query Language. World Wide Web Consortium Working Draft (2003), Available at: http:\/\/www.w3.org\/TR\/xquery\/","DOI":"10.1145\/872757.872877"},{"key":"18_CR2","unstructured":"Boja\u0144czyk, M., Walukiewicz, I.: Unranked Tree Algebra. Technical report, University of Warsaw (2005)"},{"key":"18_CR3","unstructured":"Clark, J., Murata, M., et al.: RelaxNG Specification. OASIS, Available online: http:\/\/www.oasis-open.org\/committees\/relax-ng"},{"key":"18_CR4","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1007\/978-3-642-59126-6_3","volume-title":"Handbook of Formal Languages","author":"J. Engelfriet","year":"1997","unstructured":"Engelfriet, J.: Context-Free Graph Grammars. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages, pp. 125\u2013213. Springer, Berlin (1997)"},{"issue":"1","key":"18_CR5","doi-asserted-by":"publisher","first-page":"34","DOI":"10.1006\/inco.1999.2807","volume":"154","author":"J. Engelfriet","year":"1999","unstructured":"Engelfriet, J., Maneth, S.: Macro Tree Transducers, Attribute Grammars, and MSO Definable Tree Translations. Inform. and Comput.\u00a0154(1), 34\u201391 (1999)","journal-title":"Inform. and Comput."},{"key":"18_CR6","doi-asserted-by":"publisher","first-page":"613","DOI":"10.1007\/s00236-003-0120-0","volume":"39","author":"J. Engelfriet","year":"2003","unstructured":"Engelfriet, J., Maneth, S.: A Comparison of Pebble Tree Transducers with Macro Tree Transducers. Acta Informatica\u00a039, 613\u2013698 (2003)","journal-title":"Acta Informatica"},{"key":"18_CR7","doi-asserted-by":"publisher","first-page":"328","DOI":"10.1016\/S0022-0000(77)80034-2","volume":"15","author":"J. Engelfriet","year":"1977","unstructured":"Engelfriet, J., Schmidt, E.M.: IO and OI (I&II). J. Comp. Syst. Sci.\u00a015, 328\u2013353 (1977), 16, 67\u201399 (1978)","journal-title":"J. Comp. Syst. Sci."},{"key":"18_CR8","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1016\/0022-0000(85)90066-2","volume":"31","author":"J. Engelfriet","year":"1985","unstructured":"Engelfriet, J., Vogler, H.: Macro Tree Transducers. J. Comp. Syst. Sci.\u00a031, 71\u2013146 (1985)","journal-title":"J. Comp. Syst. Sci."},{"key":"18_CR9","doi-asserted-by":"crossref","unstructured":"Fischer, M.J.: Grammars with Macro-like Productions. PhD thesis, Harvard University, Massachusetts (1968)","DOI":"10.1109\/SWAT.1968.12"},{"key":"18_CR10","doi-asserted-by":"crossref","unstructured":"Frisch, A.: Regular Tree Language Recognition with Static Information. In: PLAN-X (2004)","DOI":"10.1007\/1-4020-8141-3_50"},{"key":"18_CR11","doi-asserted-by":"crossref","first-page":"50","DOI":"10.1145\/1040305.1040310","volume-title":"POPL","author":"H. Hosoya","year":"2005","unstructured":"Hosoya, H., Frisch, A., Castagna, G.: Parametric Polymorphism for XML. In: POPL, pp. 50\u201362. ACM Press, New York (2005)"},{"issue":"6","key":"18_CR12","doi-asserted-by":"publisher","first-page":"961","DOI":"10.1017\/S0956796802004410","volume":"13","author":"H. Hosoya","year":"2002","unstructured":"Hosoya, H., Pierce, B.C.: Regular expression pattern matching for XML. Journal of Functional Programming\u00a013(6), 961\u20131004 (2002)","journal-title":"Journal of Functional Programming"},{"issue":"2","key":"18_CR13","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1145\/767193.767195","volume":"3","author":"H. Hosoya","year":"2003","unstructured":"Hosoya, H., Pierce, B.C.: XDuce: A Statically Typed XML Processing Language. ACM Trans. Inter. Tech.\u00a03(2), 117\u2013148 (2003)","journal-title":"ACM Trans. Inter. Tech."},{"key":"18_CR14","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1109\/TSE.2004.1271173","volume":"30","author":"C. Kirkegaard","year":"2004","unstructured":"Kirkegaard, C., M\u00f8ller, A., Schwartzbach, M.I.: Static Analysis of XML Transformations in Java. IEEE Trans. Soft. Eng.\u00a030, 181\u2013192 (2004)","journal-title":"IEEE Trans. Soft. Eng."},{"key":"18_CR15","first-page":"283","volume-title":"PODS","author":"S. Maneth","year":"2005","unstructured":"Maneth, S., Berlea, A., Perst, T., Seidl, H.: XML Type Checking with Macro Tree Transducers. In: PODS, pp. 283\u2013294. ACM Press, New York (2005)"},{"key":"18_CR16","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1145\/1055558.1055563","volume-title":"PODS","author":"W. Martens","year":"2004","unstructured":"Martens, W., Neven, F.: Frontiers of Tractability for Typechecking Simple XML Transformations. In: PODS, pp. 23\u201334. ACM Press, New York (2004)"},{"key":"18_CR17","doi-asserted-by":"publisher","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.\u00a0336, 153\u2013180 (2005)","journal-title":"Theor. Comput. Sci."},{"key":"18_CR18","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1016\/S0022-0000(02)00030-2","volume":"66","author":"T. Milo","year":"2003","unstructured":"Milo, T., Suciu, D., Vianu, V.: Typechecking for XML Transformers. J. Comp. Syst. Sci.\u00a066, 66\u201397 (2003)","journal-title":"J. Comp. Syst. Sci."},{"key":"18_CR19","doi-asserted-by":"crossref","unstructured":"M\u00f8ller, A., Olesen, M., Schwartzbach, M.: Static Validation of XSL Transformations. Technical Report RS-05-32, BRICS (October 2005)","DOI":"10.7146\/brics.v12i32.21899"},{"key":"18_CR20","first-page":"17","volume-title":"ICDT","author":"A. M\u00f8ller","year":"2005","unstructured":"M\u00f8ller, A., Schwartzbach, M.I.: The Design Space of Type Checkers for XML Transformation Languages. In: ICDT, pp. 17\u201336. Springer, Heidelberg (2005)"},{"key":"18_CR21","unstructured":"Murata, M., Lee, D., Mani, M.: Taxonomy of XML Schema Languages using Formal Language Theory. In: Extreme Markup Languages (2000)"},{"issue":"3","key":"18_CR22","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1145\/601858.601869","volume":"31","author":"F. Neven","year":"2002","unstructured":"Neven, F.: Automata Theory for XML Researchers. SIGMOD Record\u00a031(3), 39\u201346 (2002)","journal-title":"SIGMOD Record"},{"key":"18_CR23","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1016\/j.ipl.2003.05.001","volume":"89","author":"T. Perst","year":"2004","unstructured":"Perst, T., Seidl, H.: Macro Forest Transducers. Inf. Proc. Letters\u00a089, 141\u2013149 (2004)","journal-title":"Inf. Proc. Letters"},{"key":"18_CR24","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1007\/BF01695769","volume":"4","author":"W.C. Rounds","year":"1970","unstructured":"Rounds, W.C.: Mappings and Grammars on Trees. Math. Systems Theory\u00a04, 257\u2013287 (1970)","journal-title":"Math. Systems Theory"},{"key":"18_CR25","first-page":"974","volume-title":"VLDB","author":"A. Schmidt","year":"2002","unstructured":"Schmidt, A., Waas, F., Kersten, M.L., Carey, M.J., Manolescu, I., Busse, R.: Xmark: A benchmark for XML data management. In: VLDB, pp. 974\u2013985. Morgan Kaufmann, San Francisco (2002)"},{"key":"18_CR26","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1016\/0020-0190(94)00130-8","volume":"52","author":"H. Seidl","year":"1994","unstructured":"Seidl, H.: Haskell Overloading is DEXPTIME Complete. Inf. Proc. Letters\u00a052, 57\u201360 (1994)","journal-title":"Inf. Proc. Letters"},{"key":"18_CR27","first-page":"400","volume-title":"ICALP","author":"H. Seidl","year":"1994","unstructured":"Seidl, H.: Least Solutions of Equations over $\\cal N$ . In: ICALP, pp. 400\u2013411. Springer, Heidelberg (1994)"},{"key":"18_CR28","unstructured":"W3C. Extensible Markup Language (XML) 1.0, 2nd edn. (October 6, 2000), Available online: http:\/\/www.w3.org\/TR\/2000\/REC-xml-20001006"}],"container-title":["Lecture Notes in Computer Science","Database Theory \u2013 ICDT 2007"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11965893_18","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,9]],"date-time":"2023-05-09T22:13:22Z","timestamp":1683670402000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11965893_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540692690","9783540692706"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/11965893_18","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}