{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T00:26:54Z","timestamp":1761611214672},"publisher-location":"Berlin, Heidelberg","reference-count":14,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540671411"},{"type":"electronic","value":"9783540465416"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2000]]},"DOI":"10.1007\/3-540-46541-3_45","type":"book-chapter","created":{"date-parts":[[2007,8,2]],"date-time":"2007-08-02T12:03:24Z","timestamp":1186056204000},"page":"542-554","source":"Crossref","is-referenced-by-count":3,"title":["Characterizing and Deciding MSO-Definability of Macro Tree Transductions"],"prefix":"10.1007","author":[{"given":"Joost","family":"Engelfriet","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sebastian","family":"Maneth","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2000,3,24]]},"reference":[{"key":"45_CR1","doi-asserted-by":"publisher","first-page":"439","DOI":"10.1016\/S0019-9958(71)90706-6","volume":"19","author":"A. V. Aho","year":"1971","unstructured":"A. V. Aho and J. D. Ullman. Translations on a context-free grammar. Inform and Control, 19:439\u2013475, 1971.","journal-title":"Inform and Control"},{"key":"45_CR2","unstructured":"R. Bloem and J. Engelfriet. A comparison of tree transductions defined by monadic second order logic and by attribute grammars. Technical Report 98-02, Leiden University, 1998. To appear in J. of Comp. Syst. Sci."},{"key":"45_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. Theoret. Comput. Sci., 17:163\u2013191 and 235\u2013257, 1982.","journal-title":"Theoret. Comput. Sci."},{"key":"45_CR4","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/0304-3975(94)90268-2","volume":"126","author":"B. Courcelle","year":"1994","unstructured":"B. Courcelle. Monadic second-order definable graph transductions: a survey. Theoret. Comput. Sci., 126:53\u201375, 1994.","journal-title":"Theoret. Comput. Sci."},{"key":"45_CR5","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1006\/inco.1995.1020","volume":"116","author":"B. Courcelle","year":"1995","unstructured":"B. Courcelle. Structural properties of context-free sets of graphs generated by vertex replacement. Inform. and Comput., 116:275\u2013293, 1995.","journal-title":"Inform. and Comput."},{"key":"45_CR6","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":"45_CR7","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"234","DOI":"10.1007\/3-540-48321-7_19","volume-title":"Proc. FCT 99","author":"F. Drewes","year":"1999","unstructured":"F. Drewes. The complexity of the exponential output size problem for top-down tree transducers. In G. Ciobanu and Gh. P\u0102un, editors, Proc. FCT 99, volume 1684 of LNCS, pages 234\u2013245. Springer-Verlag, 1999."},{"key":"45_CR8","unstructured":"J. Engelfriet and S. Maneth. Macro tree transducers of linear size increase. In preparation, http:\/\/www.wi.leidenuniv.nl\/~maneth\/LSI.ps.gz ."},{"key":"45_CR9","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."},{"key":"45_CR10","doi-asserted-by":"publisher","first-page":"150","DOI":"10.1016\/0022-0000(80)90058-6","volume":"20","author":"J. Engelfriet","year":"1980","unstructured":"J. Engelfriet, G. Rozenberg, and G. Slutzki. Tree transducers, L systems, and two-way machines. J. of Comp. Syst. Sci., 20:150\u2013202, 1980.","journal-title":"J. of Comp. Syst. Sci."},{"key":"45_CR11","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1016\/0022-0000(85)90066-2","volume":"31","author":"J. Engelfriet","year":"1985","unstructured":"J. Engelfriet and H. Vogler. Macro tree transducers. J. of Comp. Syst. Sci., 31:71\u2013146, 1985.","journal-title":"J. of Comp. Syst. Sci."},{"key":"45_CR12","doi-asserted-by":"crossref","unstructured":"Z. F\u00fcl\u00f6p and H. Vogler. Syntax-Directed Semantics \u2014 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":"45_CR13","doi-asserted-by":"crossref","unstructured":"F. G\u00e9cseg and M. Steinby. Tree automata. In G. Rozenberg and A. Salomaa, editors, Handbook of Formal Languages. Vol. 3. Chap. 1. Springer-Verlag, 1997.","DOI":"10.1007\/978-3-642-59126-6_1"},{"key":"45_CR14","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1007\/BFb0017482","volume-title":"Proc. CAAP 94","author":"N. Klarlund","year":"1994","unstructured":"N. Klarlund and M. I. Schwartzbach. Graphs and decidable transductions based on edge constraints. In S. Tison, editor, Proc. CAAP 94, volume 787 of LNCS, pages 187\u2013201. Springer-Verlag, 1994."}],"container-title":["Lecture Notes in Computer Science","STACS 2000"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-46541-3_45","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,1]],"date-time":"2019-05-01T14:09:57Z","timestamp":1556719797000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-46541-3_45"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000]]},"ISBN":["9783540671411","9783540465416"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/3-540-46541-3_45","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2000]]}}}