{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:24:48Z","timestamp":1759638288802},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2008,12,3]],"date-time":"2008-12-03T00:00:00Z","timestamp":1228262400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Acta Informatica"],"published-print":{"date-parts":[[2009,4]]},"DOI":"10.1007\/s00236-008-0087-y","type":"journal-article","created":{"date-parts":[[2008,12,2]],"date-time":"2008-12-02T08:22:16Z","timestamp":1228206136000},"page":"139-154","source":"Crossref","is-referenced-by-count":3,"title":["The time complexity of typechecking tree-walking tree transducers"],"prefix":"10.1007","volume":"46","author":[{"given":"Joost","family":"Engelfriet","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2008,12,3]]},"reference":[{"key":"87_CR1","unstructured":"Aho, A.V., Lam, M.S., Sethi, R., Ullman, J.D.: Compilers: Principles, Techniques, and Tools, 2nd edn. Addison-Wesley, Reading, MA, USA (2006)"},{"key":"87_CR2","unstructured":"Bartha, M.: An algebraic definition of attributed transformations, Acta Cybernetica 5, 409\u2013421 (1982). In: G\u00e9cseg, F. (ed.) Preliminary version. Proc. FCT\u201981. Lecture Notes in Computer Science 117, pp. 51\u201360. Springer, Berlin (1981)"},{"key":"87_CR3","doi-asserted-by":"crossref","unstructured":"Engelfriet, J.: The complexity of the circularity problem for attribute grammars: a note on a counterexample for a simpler construction, SIGACT News, Summer, pp. 57\u201359 (1989)","DOI":"10.1145\/70642.70645"},{"key":"87_CR4","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1016\/S0019-9958(81)90466-6","volume":"49","author":"J. Engelfriet","year":"1981","unstructured":"Engelfriet J., Fil\u00e8 G. (1981) Passes and paths of attribute grammars. Inf. Control 49: 125\u2013169","journal-title":"Inf. Control"},{"key":"87_CR5","doi-asserted-by":"crossref","unstructured":"Engelfriet, J., Hoogeboom, H.J., Samwel, B.: XML transformation by tree-walking transducers with invisible pebbles. In: Libkin, L. (ed.) Proc. PODS\u201907, pp. 63\u201372. ACM Press, New York (2007)","DOI":"10.1145\/1265530.1265540"},{"key":"87_CR6","doi-asserted-by":"crossref","first-page":"613","DOI":"10.1007\/s00236-003-0120-0","volume":"39","author":"J. Engelfriet","year":"2003","unstructured":"Engelfriet J., Maneth S. (2003) A comparison of pebble tree transducers with macro tree transducers. Acta Informatica 39: 613\u2013698","journal-title":"Acta Informatica"},{"key":"87_CR7","first-page":"261","volume":"5","author":"Z. F\u00fcl\u00f6p","year":"1981","unstructured":"F\u00fcl\u00f6p Z. (1981) On attributed tree transducers. Acta Cybernetica 5: 261\u2013279","journal-title":"Acta Cybernetica"},{"key":"87_CR8","doi-asserted-by":"crossref","unstructured":"F\u00fcl\u00f6p, Z., Vogler, H.: Syntax-directed semantics, formal models based on tree transducers. In: Monographs in Theoretical Computer Science, An EATCS Series. Springer, Berlin (1998)","DOI":"10.1007\/978-3-642-72248-6"},{"key":"87_CR9","doi-asserted-by":"crossref","first-page":"715","DOI":"10.1145\/322276.322283","volume":"28","author":"M. Jazayeri","year":"1981","unstructured":"Jazayeri M. (1981) A simpler construction for showing the intrinsically exponential complexity of the circularity problem for attribute grammars. J. ACM 28: 715\u2013720","journal-title":"J. ACM"},{"key":"87_CR10","doi-asserted-by":"crossref","first-page":"697","DOI":"10.1145\/361227.361231","volume":"18","author":"M. Jazayeri","year":"1975","unstructured":"Jazayeri M., Ogden W.F., Rounds W.C. (1975) The intrinsically exponential complexity of the circularity problem for attribute grammars. Commun. ACM 18: 697\u2013706","journal-title":"Commun. ACM"},{"key":"87_CR11","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/S0019-9958(83)80021-7","volume":"57","author":"T. Kamimura","year":"1983","unstructured":"Kamimura T. (1983) Tree automata and attribute grammars. Inf. Control 57: 1\u201320","journal-title":"Inf. Control"},{"key":"87_CR12","doi-asserted-by":"crossref","first-page":"10","DOI":"10.1016\/S0019-9958(81)90438-1","volume":"49","author":"T. Kamimura","year":"1981","unstructured":"Kamimura T., Slutzki G. (1981) Parallel and two-way automata on directed ordered acyclic graphs. Inf. Control 49: 10\u201351","journal-title":"Inf. Control"},{"key":"87_CR13","doi-asserted-by":"crossref","unstructured":"Knuth, D.E.: Semantics of context-free languages. Math. Systems Theory 2, 127\u2013145 (1968). Correction: Math. Systems Theory 5, 95\u201396 (1971)","DOI":"10.1007\/BF01702865"},{"key":"87_CR14","doi-asserted-by":"crossref","unstructured":"Maneth, S., Berlea, A., Perst, T., Seidl, H.: XML type checking with macro tree transducers. In: Proc. PODS\u201905, pp. 283\u2013294. ACM Press, New York (2005)","DOI":"10.1145\/1065167.1065203"},{"key":"87_CR15","doi-asserted-by":"crossref","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. (2003) Typechecking for XML transformers. J. Comput. Syst. Sci. 66: 66\u201397","journal-title":"J. Comput. Syst. Sci."},{"key":"87_CR16","doi-asserted-by":"crossref","unstructured":"Neven, F.: Automata, Logic, and XML. In: Bradfield, J.C. (ed.) Proc. CSL\u201902. Lecture Notes in Computer Science, vol. 2471, pp. 2\u201326. Springer, Berlin (2002)","DOI":"10.1007\/3-540-45793-3_2"},{"key":"87_CR17","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1016\/j.ipl.2003.05.001","volume":"89","author":"T. Perst","year":"2004","unstructured":"Perst T., Seidl H. (2004) Macro forest transducers. Inf. Process. Lett. 89: 141\u2013149","journal-title":"Inf. Process. Lett."},{"key":"87_CR18","doi-asserted-by":"crossref","unstructured":"Samuelides, M., Segoufin, L.: Complexity of pebble tree-walking automata. In: Csuhaj-Varj\u00fa, E., \u00c9sik, Z. (eds.) Proc. FCT\u201907. Lecture Notes in Computer Science, vol. 4639, pp. 458\u2013469. Springer, Berlin (2007)","DOI":"10.1007\/978-3-540-74240-1_40"},{"key":"87_CR19","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1016\/0304-3975(85)90077-5","volume":"41","author":"G. Slutzki","year":"1985","unstructured":"Slutzki G. (1985) Alternating tree automata. Theor. Comput. Sci. 41: 305\u2013318","journal-title":"Theor. Comput. Sci."},{"key":"87_CR20","unstructured":"Yashiro, T.: Typechecking k-pebble tree transducers: practical efficiency. Bachelor Thesis, University of Tokyo, February 2006"}],"container-title":["Acta Informatica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-008-0087-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00236-008-0087-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-008-0087-y","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,24]],"date-time":"2019-05-24T13:41:55Z","timestamp":1558705315000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00236-008-0087-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,12,3]]},"references-count":20,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2009,4]]}},"alternative-id":["87"],"URL":"https:\/\/doi.org\/10.1007\/s00236-008-0087-y","relation":{},"ISSN":["0001-5903","1432-0525"],"issn-type":[{"value":"0001-5903","type":"print"},{"value":"1432-0525","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,12,3]]}}}