{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T20:09:31Z","timestamp":1725566971569},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540304951"},{"type":"electronic","value":"9783540324195"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11590156_40","type":"book-chapter","created":{"date-parts":[[2005,12,5]],"date-time":"2005-12-05T15:43:16Z","timestamp":1133797396000},"page":"495-504","source":"Crossref","is-referenced-by-count":2,"title":["The Equivalence Problem for Deterministic MSO Tree Transducers Is Decidable"],"prefix":"10.1007","author":[{"given":"Joost","family":"Engelfriet","sequence":"first","affiliation":[]},{"given":"Sebastian","family":"Maneth","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"40_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":"Aho, A.V., Ullman, J.D.: Translations on a context-free grammar. Inform. and Control\u00a019, 439\u2013475 (1971)","journal-title":"Inform. and Control"},{"key":"40_CR2","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1006\/jcss.1999.1684","volume":"61","author":"R. Bloem","year":"2000","unstructured":"Bloem, R., Engelfriet, J.: A comparison of tree transductions defined by monadic second order logic and by attribute grammars. J. Comp. Syst. Sci.\u00a061, 1\u201350 (2000)","journal-title":"J. Comp. Syst. Sci."},{"key":"40_CR3","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1016\/S0019-9958(82)90786-0","volume":"52","author":"B. Courcelle","year":"1982","unstructured":"Courcelle, B., Franchi-Zannettacci, P.: On the equivalence problem for attribute systems. Inform. and Control\u00a052, 275\u2013305 (1982)","journal-title":"Inform. and Control"},{"key":"40_CR4","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1137\/0216018","volume":"16","author":"K. Culik II","year":"1987","unstructured":"Culik II, K., Karhum\u00e4ki, J.: The equivalence problem for single-valued two-way transducers (on NPDT0L languages) is decidable. SIAM J. Comput.\u00a016, 221\u2013230 (1987)","journal-title":"SIAM J. Comput."},{"key":"40_CR5","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/0304-3975(94)90268-2","volume":"126","author":"B. Courcelle","year":"1994","unstructured":"Courcelle, B.: Monadic second-order definable graph transductions: a survey. Theoret. Comput. Sci.\u00a0126, 53\u201375 (1994)","journal-title":"Theoret. Comput. Sci."},{"key":"40_CR6","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1142\/9789812384720_0005","volume-title":"Handbook of graph grammars and computing by graph transformation","author":"B. Courcelle","year":"1997","unstructured":"Courcelle, B.: The expression of graph properties and graph transformations in monadic second-order logic. In: Handbook of graph grammars and computing by graph transformation, vol.\u00a01, pp. 313\u2013400. World Scientific, Singapore (1997)"},{"key":"40_CR7","doi-asserted-by":"publisher","first-page":"216","DOI":"10.1145\/371316.371512","volume":"2","author":"J. Engelfriet","year":"2001","unstructured":"Engelfriet, J., Hoogeboom, H.J.: MSO definable string transductions and twoway finite-state transducers. ACM Transactions on Computational Logic\u00a02, 216\u2013254 (2001)","journal-title":"ACM Transactions on Computational Logic"},{"key":"40_CR8","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, 34\u201391 (1999)","journal-title":"Inform. and Comput."},{"key":"40_CR9","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":"40_CR10","doi-asserted-by":"publisher","first-page":"950","DOI":"10.1137\/S0097539701394511","volume":"32","author":"J. Engelfriet","year":"2003","unstructured":"Engelfriet, J., Maneth, S.: Macro tree translations of linear size increase are MSO definable. SIAM J. Comput.\u00a032, 950\u20131006 (2003)","journal-title":"SIAM J. Comput."},{"key":"40_CR11","volume-title":"Formal language theory; perspectives and open problems","author":"J. Engelfriet","year":"1980","unstructured":"Engelfriet, J.: Some open questions and recent results on tree transducers and tree languages. In: Formal language theory; perspectives and open problems, Academic Press, London (1980)"},{"key":"40_CR12","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, vol.\u00a03, ch. 3, Springer, Heidelberg (1997)"},{"key":"40_CR13","doi-asserted-by":"publisher","first-page":"150","DOI":"10.1016\/0022-0000(80)90058-6","volume":"20","author":"J. Engelfriet","year":"1980","unstructured":"Engelfriet, J., Rozenberg, G., Slutzki, G.: Tree transducers, L systems, and two-way machines. J. Comp. Syst. Sci.\u00a020, 150\u2013202 (1980)","journal-title":"J. Comp. Syst. Sci."},{"key":"40_CR14","first-page":"1","volume":"5","author":"Z. \u00c9sik","year":"1980","unstructured":"\u00c9sik, Z.: Decidability results concerning tree transducers I. Acta Cybern.\u00a05, 1\u201320 (1980)","journal-title":"Acta Cybern."},{"key":"40_CR15","volume-title":"EATCS Monographs in Theoretical Computer Science","author":"Z. F\u00fcl\u00f6p","year":"1998","unstructured":"F\u00fcl\u00f6p, Z., Vogler, H.: Syntax-Directed Semantics \u2013 Formal Models based on Tree Transducers. In: Brauer, W., Rozenberg, G., Salomaa, A. (eds.) EATCS Monographs in Theoretical Computer Science, Springer, Heidelberg (1998)"},{"key":"40_CR16","volume-title":"The Mathematical Theory of Context-Free Languages","author":"S. Ginsburg","year":"1966","unstructured":"Ginsburg, S.: The Mathematical Theory of Context-Free Languages. McGraw-Hill, New York (1966)"},{"key":"40_CR17","doi-asserted-by":"publisher","first-page":"409","DOI":"10.1145\/321466.321473","volume":"15","author":"T.V. Griffiths","year":"1968","unstructured":"Griffiths, T.V.: The unsolvability of the equivalence problem for \u039b-free nondeterministic generalized machines. J. ACM\u00a015, 409\u2013413 (1968)","journal-title":"J. ACM"},{"key":"40_CR18","first-page":"333","volume":"113","author":"S. Ginsburg","year":"1964","unstructured":"Ginsburg, S., Spanier, E.H.: Bounded Algol-like languages. Trans. Amer. Math. Soc.\u00a0113, 333\u2013368 (1964)","journal-title":"Trans. Amer. Math. Soc."},{"issue":"3","key":"40_CR19","doi-asserted-by":"publisher","first-page":"448","DOI":"10.1137\/0211035","volume":"11","author":"E.M. Gurari","year":"1982","unstructured":"Gurari, E.M.: The equivalence problem for deterministic two-way sequential transducers is decidable. SIAM J. Comput.\u00a011(3), 448\u2013452 (1982)","journal-title":"SIAM J. Comput."},{"key":"40_CR20","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1016\/0304-3975(82)90061-5","volume":"19","author":"O.H. Ibarra","year":"1982","unstructured":"Ibarra, O.H.: 2DST mappings on languages and related problems. Theoret. Comput. Sci.\u00a019, 219\u2013227 (1982)","journal-title":"Theoret. Comput. Sci."},{"key":"40_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"326","DOI":"10.1007\/3-540-36206-1_24","volume-title":"FST TCS 2002: Foundations of Software Technology and Theoretical Computer Science","author":"S. Maneth","year":"2002","unstructured":"Maneth, S.: The macro tree transducer hierarchy collapses for functions of linear size increase. In: Agrawal, M., Seth, A.K. (eds.) FSTTCS 2002. LNCS, vol.\u00a02556, pp. 326\u2013337. Springer, Heidelberg (2002)"},{"key":"40_CR22","doi-asserted-by":"publisher","first-page":"283","DOI":"10.1145\/1065167.1065203","volume-title":"Proc. PODS 2005","author":"S. Maneth","year":"2005","unstructured":"Maneth, S., Berlea, A., Perst, T., Seidl, H.: XML type checking with macro tree transducers. In: Proc. PODS 2005, pp. 283\u2013294. ACM Press, New York (2005)"},{"key":"40_CR23","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":"40_CR24","doi-asserted-by":"publisher","first-page":"570","DOI":"10.1145\/321356.321364","volume":"13","author":"R.J. Parikh","year":"1966","unstructured":"Parikh, R.J.: On context-free languages. J. ACM\u00a013, 570\u2013581 (1966)","journal-title":"J. ACM"},{"key":"40_CR25","first-page":"167","volume":"4","author":"Z. Zachar","year":"1980","unstructured":"Zachar, Z.: The solvability of the equivalence problem for deterministic frontier-toroot tree transducers. Acta Cybern.\u00a04, 167\u2013177 (1980)","journal-title":"Acta Cybern."}],"container-title":["Lecture Notes in Computer Science","FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11590156_40.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T06:49:16Z","timestamp":1619506156000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11590156_40"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540304951","9783540324195"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/11590156_40","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2005]]}}}