{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:32:26Z","timestamp":1725489146730},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540002253"},{"type":"electronic","value":"9783540362067"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2002]]},"DOI":"10.1007\/3-540-36206-1_24","type":"book-chapter","created":{"date-parts":[[2007,8,16]],"date-time":"2007-08-16T07:23:08Z","timestamp":1187248988000},"page":"265-276","source":"Crossref","is-referenced-by-count":9,"title":["The Complexity of Compositions of Deterministic Tree Transducers"],"prefix":"10.1007","author":[{"given":"Sebastian","family":"Maneth","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2002,12,16]]},"reference":[{"key":"24_CR1","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1080\/00207168108803261","volume":"10","author":"P.R.J. Asveld","year":"1981","unstructured":"P.R.J. Asveld. Time and space complexity of inside-out macro languages. Internat. J. Comput. Math., 10:3\u201314, 1981.","journal-title":"Internat. J. Comput. Math."},{"issue":"3","key":"24_CR2","doi-asserted-by":"publisher","first-page":"376","DOI":"10.1137\/0207030","volume":"7","author":"B. S. Baker","year":"1978","unstructured":"B. S. Baker. Generalized syntax directed translation, tree transducers, and linear space. SIAM J. Comput., 7(3):376\u2013391, 1978.","journal-title":"SIAM J. Comput."},{"key":"24_CR3","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1016\/0304-3975(82)90003-2","volume":"17","author":"B. Courcelle","year":"1982","unstructured":"B. Courcelle and P. Franchi-Zannettacci. Attribute grammars and recursive program schemes. TCS, 17:163\u2013191 and 235\u2013257, 1982.","journal-title":"TCS"},{"key":"24_CR4","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1016\/0304-3975(82)90009-3","volume":"20","author":"W. Damm","year":"1982","unstructured":"W. Damm. The IO-and OI-hierarchies. TCS, 20:95\u2013207, 1982.","journal-title":"TCS"},{"key":"24_CR5","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1006\/inco.1998.2715","volume":"145","author":"F. Drewes","year":"1998","unstructured":"F. Drewes and J. Engelfriet. Decidability of finiteness of ranges of tree transductions. Inform. and Comput., 145:1\u201350, 1998.","journal-title":"Inform. and Comput."},{"key":"24_CR6","series-title":"Lect Notes Comput Sci","volume-title":"Attribute Grammars, Definitions and Bibliography","author":"P. Deransart","year":"1988","unstructured":"P. Deransart, M. Jourdan, and B. Lorho. Attribute Grammars, Definitions and Bibliography. Number 323 in LNCS. Springer-Verlag, 1988."},{"key":"24_CR7","unstructured":"J. Engelfriet and S. Maneth. Work in progress."},{"key":"24_CR8","doi-asserted-by":"publisher","first-page":"34","DOI":"10.1006\/inco.1999.2807","volume":"154","author":"J. Engelfriet","year":"1999","unstructured":"J. Engelfriet and S. Maneth. Macro tree transducers, attribute grammars, and MSO definable tree translations. Inform. and Comput., 154:34\u201391, 1999.","journal-title":"Inform. and Comput."},{"issue":"2","key":"24_CR9","first-page":"350","volume":"64","author":"J. Engelfriet","year":"2002","unstructured":"J. Engelfriet and S. Maneth. Output string languages of compositions of deterministic macro tree transducers. JCSS, 64(2):350\u2013395, 2002.","journal-title":"JCSS"},{"issue":"3","key":"24_CR10","doi-asserted-by":"publisher","first-page":"198","DOI":"10.1007\/BF01704020","volume":"9","author":"J. Engelfriet","year":"1975","unstructured":"J. Engelfriet. Bottom-up and top-down tree transformations\u2013a comparison. Math. Systems Theory, 9(3):198\u2013231, 1975.","journal-title":"Math. Systems Theory"},{"issue":"1","key":"24_CR11","doi-asserted-by":"publisher","first-page":"70","DOI":"10.1137\/0215005","volume":"15","author":"J. Engelfriet","year":"1986","unstructured":"J. Engelfriet. The complexity of languages generated by attribute grammars. SIAM J. Comput., 15(1):70\u201386, 1986.","journal-title":"SIAM J. Comput."},{"key":"24_CR12","first-page":"71","volume":"31","author":"J. Engelfriet","year":"1985","unstructured":"J. Engelfriet and H. Vogler. Macro tree transducers. JCSS, 31:71\u2013146, 1985.","journal-title":"JCSS"},{"key":"24_CR13","doi-asserted-by":"crossref","unstructured":"M.J. Fischer. Grammars with macro-like productions. PhD thesis, Harvard University, Massachusetts, 1968.","DOI":"10.1109\/SWAT.1968.12"},{"key":"24_CR14","first-page":"261","volume":"5","author":"Z. F\u00fcl\u00f6p","year":"1981","unstructured":"Z. F\u00fcl\u00f6p. On attributed tree transducers. Acta Cybernetica, 5:261\u2013279, 1981.","journal-title":"Acta Cybernetica"},{"key":"24_CR15","doi-asserted-by":"crossref","unstructured":"Z. F\u00fcl\u00f6p and H. Vogler. Syntax-Directed Semantics-Formal Models based on Tree Transducers. EATCS Monographs on Theoretical Computer Science (W. Brauer, G. Rozenberg, A. Salomaa, eds.). Springer-Verlag, 1998.","DOI":"10.1007\/978-3-642-72248-6"},{"key":"24_CR16","unstructured":"F. G\u00e9cseg and M. Steinby. Tree Automata. Akad\u00e9miai Kiad\u00f3, Budapest, 1984."},{"key":"24_CR17","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1007\/BF01692511","volume":"2","author":"D.E. Knuth","year":"1968","unstructured":"D.E. Knuth. Semantics of context-free languages. Math. Systems Theory, 2:127\u2013145, 1968. (Corrections in Math. Systems Theory, 5:95\u201396, 1971).","journal-title":"Math. Systems Theory"},{"key":"24_CR18","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"146","DOI":"10.1007\/978-3-540-49382-2_13","volume-title":"Benefits of tree transducers for optimizing functional programs","author":"A. K\u00fchnemann","year":"1998","unstructured":"A. K\u00fchnemann. Benefits of tree transducers for optimizing functional programs. In V. Arvind and R. Ramanujam, editors, Proc. FST&TCS\u201998, volume 1530 of LNCS, pages 146\u2013157. Springer-Verlag, 1998."},{"key":"24_CR19","doi-asserted-by":"crossref","unstructured":"T. Milo, D. Suciu, and V. Vianu. Typechecking for XML transformers. In Proc. PODS\u20192000, pages 11\u201322. ACM Press, 2000.","DOI":"10.1145\/335168.335171"},{"key":"24_CR20","unstructured":"C. H. Papadimitriou. Computational Complexity. Addison-Wesley, 1994."},{"key":"24_CR21","doi-asserted-by":"crossref","unstructured":"V. Vianu. A Web Odyssey: From Codd to XML. In Proc. PODS\u20192001, pages 1\u201315. ACM Press, 2001.","DOI":"10.1145\/375551.375554"},{"issue":"3","key":"24_CR22","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1016\/0167-6423(91)90009-M","volume":"16","author":"H. Vogler","year":"1991","unstructured":"H. Vogler. Functional description of the contextual analysis in blockstructured programming languages: a case study of tree transducers. Science of Computer Programming, 16(3):251\u2013275, 1991.","journal-title":"Science of Computer Programming"},{"key":"24_CR23","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1016\/0304-3975(90)90147-A","volume":"73","author":"P. Wadler","year":"1990","unstructured":"P. Wadler. Deforestation: Transforming programs to eliminate trees. TCS, 73:231\u2013248, 1990.","journal-title":"TCS"}],"container-title":["Lecture Notes in Computer Science","FST TCS 2002: Foundations of Software Technology and Theoretical Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-36206-1_24","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,2]],"date-time":"2019-05-02T04:07:59Z","timestamp":1556770079000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-36206-1_24"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002]]},"ISBN":["9783540002253","9783540362067"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/3-540-36206-1_24","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2002]]}}}