@article(DBLP:journals/jacm/Aho68, author = "A. V. Aho", year = "1968", title = "Indexed Grammars - An Extension of Context-Free Grammars", journal = "J. ACM", volume = "15", number = "4", pages = "647--671", doi = "10.1145/321479.321488", ) @article(DBLP:journals/iandc/AhoU71, author = "A. V. Aho and J. D. Ullman", year = "1971", title = "Translations on a Context-Free Grammar", journal = "Information and Control", volume = "19", number = "5", pages = "439--475", doi = "10.1016/S0019-9958(71)90706-6", ) @article(DBLP:journals/corr/abs-1104-2599, author = "R. Alur and L. D'Antoni", year = "2011", title = "Streaming Tree Transducers", journal = "CoRR", volume = "abs/1104.2599", ) @inproceedings(DBLP:conf/stoc/AlurM04, author = "R. Alur and P. Madhusudan", year = "2004", title = "Visibly pushdown languages", booktitle = "STOC", pages = "202--211", doi = "10.1145/1007352.1007390", ) @inproceedings(DBLP:conf/tapsoft/AndreB95, author = "Y. Andre and F. Bossut", year = "1995", title = "The Equivalence Problem for Letter-to-Letter Bottom-up Tree Transducers is Solvable", booktitle = "TAPSOFT", pages = "155--171", doi = "10.1007/3-540-59293-8\_193", ) @article(DBLP:journals/tcs/AndreB98, author = "Y. Andre and F. Bossut", year = "1998", title = "On the Equivalence Problem for Letter-to-Letter Top-Down Tree Transducers", journal = "Theor. Comput. Sci.", volume = "205", number = "1-2", pages = "207--229", doi = "10.1016/S0304-3975(97)00080-7", ) @inproceedings(DBLP:conf/mfcs/BenediktEM13, author = "M. Benedikt and J. Engelfriet and S. Maneth", year = "2013", title = "Determinacy and Rewriting of Top-Down and {MSO} Tree Transformations", booktitle = "MFCS", pages = "146--158", doi = "10.1007/978-3-642-40313-2\_15", ) @article(Berstel79transductionsand, author = "J. Berstel", year = "1979", title = "Transductions and context-free languages", journal = "Teubner, Stuttgart", ) @article(DBLP:journals/tcs/Bozapalidis92, author = "S. Bozapalidis", year = "1992", title = "Alphabetic Tree Relations", journal = "Theor. Comput. Sci.", volume = "99", number = "2", pages = "177--211", doi = "10.1016/0304-3975(92)90348-J", ) @inproceedings(DBLP:journals/corr/CaralpFRST13, author = "M. Caralp and E. Filiot and P.-A. Reynier and F. Servais and J.-M. Talbot", year = "2013", title = "Expressiveness of Visibly Pushdown Transducers", booktitle = "TTATT", pages = "17--26", doi = "10.4204/EPTCS.134.3", ) @misc(tata07, author = "H. Comon and M. Dauchet and R. Gilleron and F. Jacquemard and C. L{\"o}ding and D. Lugiez and S. Tison and M. Tommasi", year = "2007", title = "Tree Automata Techniques and Applications", howpublished = "Available at: http://www.grappa.univ-lille3.fr/tata", ) @book(DBLP:books/daglib/0030804, author = "B. Courcelle and J. Engelfriet", year = "2012", title = "Graph Structure and Monadic Second-Order Logic - A Language-Theoretic Approach", series = "Encyclopedia of mathematics and its applications", volume = "138", publisher = "Cambridge University Press", doi = "10.1017/CBO9780511977619", ) @article(DBLP:journals/tcs/CourcelleF82, author = "B. Courcelle and P. Franchi-Zannettacci", year = "1982", title = "Attribute Grammars and Recursive Program Schemes I", journal = "Theor. Comput. Sci.", volume = "17", pages = "163--191", doi = "10.1016/0304-3975(82)90003-2", ) @article(DBLP:journals/tcs/CourcelleF82a, author = "B. Courcelle and P. Franchi-Zannettacci", year = "1982", title = "Attribute Grammars and Recursive Program Schemes II", journal = "Theor. Comput. Sci.", volume = "17", pages = "235--257", doi = "10.1016/0304-3975(82)90024-X", ) @article(DBLP:journals/iandc/CourcelleF82, author = "B. Courcelle and P. Franchi-Zannettacci", year = "1982", title = "On the Equivalence Problem for Attribute Systems", journal = "Information and Control", volume = "52", number = "3", pages = "275--305", doi = "10.1016/S0019-9958(82)90786-0", ) @article(DBLP:journals/tcs/Culik76, author = "K. {Culik II}", year = "1976", title = "On the Decidability of the Sequence Equivalence Problem for {D0L}-Systems", journal = "Theor. Comput. Sci.", volume = "3", number = "1", pages = "75--84", doi = "10.1016/0304-3975(76)90066-9", ) @article(DBLP:journals/iandc/CulikF77, author = "K. {Culik II} and I. Fris", year = "1977", title = "The Decidability of the Equivalence Problem for {D0L}-Systems", journal = "Information and Control", volume = "35", number = "1", pages = "20--39", doi = "10.1016/S0019-9958(77)90512-5", ) @incollection(culkar86, author = "K. {Culik II} and J. Karhum{\"a}ki", year = "1986", title = "A new proof for the {D0L} Sequence Equivalence Problem and its implications", doi = "10.1007/978-3-642-95486-3\_5", editor = "G. Rozenberg and A. Salomaa", booktitle = "The book of {L}", publisher = "Springer, Berlin", pages = "63--74", ) @article(DBLP:journals/mst/Engelfriet77, author = "J. Engelfriet", year = "1977", title = "Top-down Tree Transducers with Regular Look-ahead", journal = "Mathematical Systems Theory", volume = "10", pages = "289--303", doi = "10.1007/BF01683280", ) @inproceedings(eng80, author = "J. Engelfriet", year = "1980", title = "Some open questions and recent results on tree transducers and tree languages", editor = "R. V. Book", booktitle = "Formal Language Theory; Perspectives and Open Problems", publisher = "Academic Press, New York", ) @article(DBLP:journals/iandc/EngelfrietM99, author = "J. Engelfriet and S. Maneth", year = "1999", title = "Macro Tree Transducers, Attribute Grammars, and {MSO} Definable Tree Translations", journal = "Inf. Comput.", volume = "154", number = "1", pages = "34--91", doi = "10.1137/S0097539701394511", ) @article(DBLP:journals/jcss/EngelfrietM02, author = "J. Engelfriet and S. Maneth", year = "2002", title = "Output String Languages of Compositions of Deterministic Macro Tree Transducers", journal = "J. Comput. Syst. Sci.", volume = "64", number = "2", pages = "350--395", doi = "10.1006/jcss.2001.1816", ) @article(DBLP:journals/acta/EngelfrietM03, author = "J. Engelfriet and S. Maneth", year = "2003", title = "A comparison of pebble tree transducers with macro tree transducers", journal = "Acta Inf.", volume = "39", number = "9", pages = "613--698", doi = "10.1007/s00236-003-0120-0", ) @article(DBLP:journals/siamcomp/EngelfrietM03, author = "J. Engelfriet and S. Maneth", year = "2003", title = "Macro Tree Translations of Linear Size Increase are {MSO} Definable", journal = "SIAM J. Comput.", volume = "32", number = "4", pages = "950--1006", doi = "10.1137/S0097539701394511", ) @article(DBLP:journals/ipl/EngelfrietM06, author = "J. Engelfriet and S. Maneth", year = "2006", title = "The equivalence problem for deterministic {MSO} tree transducers is decidable", journal = "Inf. Process. Lett.", volume = "100", number = "5", pages = "206--212", doi = "10.1016/j.ipl.2006.05.015", ) @article(DBLP:journals/jcss/EngelfrietMS09, author = "J. Engelfriet and S. Maneth and H. Seidl", year = "2009", title = "Deciding equivalence of top-down {XML} transformations in polynomial time", journal = "J. Comput. Syst. Sci.", volume = "75", number = "5", pages = "271--286", doi = "10.1016/j.jcss.2009.01.001", ) @article(DBLP:journals/corr/EngelfrietMS13, author = "J. Engelfriet and S. Maneth and H. Seidl", year = "2013", title = "Look-Ahead Removal for Top-Down Tree Transducers", journal = "CoRR", volume = "abs/1311.2400", ) @article(DBLP:journals/jcss/EngelfrietRS80, author = "J. Engelfriet and G. Rozenberg and G. Slutzki", year = "1980", title = "Tree Transducers, {L} Systems, and Two-Way Machines", journal = "J. Comput. Syst. Sci.", volume = "20", number = "2", pages = "150--202", doi = "10.1016/0022-0000(80)90058-6", ) @article(DBLP:journals/jcss/EngelfrietV85, author = "J. Engelfriet and H. Vogler", year = "1985", title = "Macro Tree Transducers", journal = "J. Comput. Syst. Sci.", volume = "31", number = "1", pages = "71--146", doi = "10.1016/0022-0000(85)90066-2", ) @article(DBLP:journals/actaC/Esik81, author = "Z. {\'E}sik", year = "1981", title = "Decidability results concerning tree transducers {I}", journal = "Acta Cybern.", volume = "5", number = "1", pages = "1--20", ) @article(DBLP:journals/fuin/Esparza97, author = "J. Esparza", year = "1997", title = "Petri Nets, Commutative Context-Free Grammars, and Basic Parallel Processes", journal = "Fundam. Inform.", volume = "31", number = "1", pages = "13--25", doi = "10.3233/FI-1997-3112", ) @inproceedings(DBLP:conf/mfcs/FiliotRRST10, author = "E. Filiot and J.-F. Raskin and P.-A. Reynier and F. Servais and J.-M. Talbot", year = "2010", title = "Properties of Visibly Pushdown Transducers", booktitle = "MFCS", pages = "355--367", doi = "10.1007/978-3-642-15155-2\_32", ) @inproceedings(DBLP:conf/sofsem/FiliotS12, author = "E. Filiot and F. Servais", year = "2012", title = "Visibly Pushdown Transducers with Look-Ahead", booktitle = "SOFSEM", pages = "251--263", doi = "10.1007/978-3-642-27660-6\_21", ) @phdthesis(fis68, author = "M. J. Fischer", year = "1968", title = "Grammars with Marcro-like Productions", school = "Harvard University", ) @phdthesis(Friese10Thesis, author = "S. Friese", year = "2011", title = "On {N}ormalization and {T}ype {C}hecking for {T}ree {T}ransducers", school = "Institut f\"ur Informatik", address = "Technische Universit\"at M\"unchen", note = "Available at http://mediatum.ub.tum.de/doc/1078090/1078090.pdf", ) @article(DBLP:journals/ijfcs/FrieseSM11, author = "S. Friese and H. Seidl and S. Maneth", year = "2011", title = "Earliest Normal Form and Minimization for Bottom-up Tree Transducers", journal = "Int. J. Found. Comput. Sci.", volume = "22", number = "7", pages = "1607--1623", doi = "10.1142/S012905411100891X", ) @book(DBLP:series/eatcs/FulopV98, author = "Z. F{\"u}l{\"o}p and H. Vogler", year = "1998", title = "Syntax-Directed Semantics - Formal Models Based on Tree Transducers", series = "Monographs in Theoretical Computer Science. An EATCS Series", publisher = "Springer", doi = "10.1007/978-3-642-72248-6", ) @book(gin66, author = "S. Ginsburg", year = "1966", title = "The Mathematical Theory of Context-Free Languages", publisher = "McGraw-Hill", ) @article(ginspa64, author = "S. Ginsburg and E. H. Spanier", year = "1964", title = "Bounded {ALGOL}-like languages", journal = "Trans. Amer. Math. Soc", volume = "113", pages = "333--368", doi = "10.2307/1994067", ) @article(DBLP:journals/jacm/Griffiths68, author = "T. V. Griffiths", year = "1968", title = "The Unsolvability of the Equivalence Problem for Lambda-Free Nondeterministic Generalized Machines", journal = "J. ACM", volume = "15", number = "3", pages = "409--413", doi = "10.1145/321466.321473", ) @article(DBLP:journals/siamcomp/Gurari82, author = "E. M. Gurari", year = "1982", title = "The Equivalence Problem for Deterministic Two-Way Sequential Transducers is Decidable", journal = "SIAM J. Comput.", volume = "11", number = "3", pages = "448--452", doi = "10.1137/0211035", ) @inproceedings(icde2014, author = "S. Hakuta and S. Maneth and K. Nakano and H. Iwasaki", year = "2014", title = "XQuery Streaming by Forest Transducers", booktitle = "ICDE", pages = "417--428", ) @article(DBLP:journals/tcs/Honkala00a, author = "J. Honkala", year = "2000", title = "A short solution for the {HDT0L} sequence equivalence problem", journal = "Theor. Comput. Sci.", volume = "244", number = "1-2", pages = "267--270", doi = "10.1016/S0304-3975(00)00158-4", ) @book(DBLP:books/aw/HopcroftU79, author = "J. E. Hopcroft and J. D. Ullman", year = "1979", title = "Introduction to Automata Theory, Languages and Computation", publisher = "Addison-Wesley", ) @article(DBLP:journals/jcss/KarhumakiPR95, author = "J. Karhum{\"a}ki and W. Plandowski and W. Rytter", year = "1995", title = "Polynomial Size Test Sets for Context-Free Languages", journal = "J. Comput. Syst. Sci.", volume = "50", number = "1", pages = "11--19", doi = "10.1006/jcss.1995.1002", ) @article(DBLP:journals/mst/Knuth68, author = "D. E. Knuth", year = "1968", title = "Semantics of Context-Free Languages", journal = "Mathematical Systems Theory", volume = "2", number = "2", pages = "127--145", doi = "10.1007/BF01692511", ) @inproceedings(DBLP:conf/pods/LemayMN10, author = "A. Lemay and S. Maneth and J. Niehren", year = "2010", title = "A learning algorithm for top-down {XML} transformations", booktitle = "PODS", pages = "285--296", doi = "10.1145/1807085.1807122", ) @inproceedings(DBLP:conf/fsttcs/Maneth03, author = "S. Maneth", year = "2003", title = "The Macro Tree Transducer Hierarchy Collapses for Functions of Linear Size Increase", booktitle = "FSTTCS", pages = "326--337", doi = "10.1007/978-3-540-24597-1\_28", ) @inproceedings(DBLP:conf/pods/ManethBPS05, author = "S. Maneth and A. Berlea and T. Perst and H. Seidl", year = "2005", title = "{XML} type checking with macro tree transducers", booktitle = "PODS", pages = "283--294", doi = "10.1145/1065167.1065203", ) @inproceedings(DBLP:conf/icdt/ManethPS07, author = "S. Maneth and T. Perst and H. Seidl", year = "2007", title = "Exact {XML} Type Checking in Polynomial Time", booktitle = "ICDT", pages = "254--268", doi = "10.1007/11965893\_18", ) @article(DBLP:journals/jcss/MiloSV03, author = "T. Milo and D. Suciu and V. Vianu", year = "2003", title = "Typechecking for {XML} transformers", journal = "J. Comput. Syst. Sci.", volume = "66", number = "1", pages = "66--97", doi = "10.1016/S0022-0000(02)00030-2", ) @inproceedings(DBLP:conf/aplas/NakanoM06, author = "K. Nakano and S.-C. Mu", year = "2006", title = "A Pushdown Machine for Recursive {XML} Processing", booktitle = "APLAS", pages = "340--356", doi = "10.1007/11924661\_21", ) @article(DBLP:journals/jacm/Parikh66, author = "R. Parikh", year = "1966", title = "On Context-Free Languages", journal = "J. ACM", volume = "13", number = "4", pages = "570--581", doi = "10.1145/321356.321364", ) @article(DBLP:journals/ipl/PerstS04, author = "T. Perst and H. Seidl", year = "2004", title = "Macro forest transducers", journal = "Inf. Process. Lett.", volume = "89", number = "3", pages = "141--149", doi = "10.1016/j.ipl.2003.05.001", ) @inproceedings(DBLP:conf/esa/Plandowski94, author = "W. Plandowski", year = "1994", title = "Testing Equivalence of Morphisms on Context-Free Languages", booktitle = "ESA", pages = "460--470", ) @inproceedings(DBLP:conf/icalp/RaskinS08, author = "J.-F. Raskin and F. Servais", year = "2008", title = "Visibly Pushdown Transducers", booktitle = "ICALP (2)", pages = "386--397", doi = "10.1007/978-3-540-70583-3\_32", ) @inproceedings(DBLP:conf/stoc/Rounds69, author = "W. C. Rounds", year = "1969", title = "Context-Free Grammars on Trees", booktitle = "STOC", pages = "143--148", doi = "10.1145/800169.805428", ) @article(DBLP:journals/mst/Rounds70, author = "W. C. Rounds", year = "1970", title = "Mappings and Grammars on Trees", journal = "Mathematical Systems Theory", volume = "4", number = "3", pages = "257--287", doi = "10.1007/BF01695769", ) @incollection(ruh86, author = "K. Ruohonen", year = "1986", title = "Equivalence problems for regular sets of word morphisms", doi = "10.1007/978-3-642-95486-3\_33", editor = "G. Rozenberg and A. Salomaa", booktitle = "The book of {L}", publisher = "Springer, Berlin", pages = "393--401", ) @article(DBLP:journals/tcs/Seidl92, author = "H. Seidl", year = "1992", title = "Single-Valuedness of Tree Transducers is Decidable in Polynomial Time", journal = "Theor. Comput. Sci.", volume = "106", number = "1", pages = "135--181", doi = "10.1016/0304-3975(92)90281-J", ) @article(DBLP:journals/mst/Seidl94, author = "H. Seidl", year = "1994", title = "Equivalence of Finite-Valued Tree Transducers Is Decidable", journal = "Mathematical Systems Theory", volume = "27", number = "4", pages = "285--346", doi = "10.1007/BF01192143", ) @article(DBLP:journals/ipl/Seidl94, author = "H. Seidl", year = "1994", title = "Haskell Overloading is {DEXPTIME}-Complete", journal = "Inf. Process. Lett.", volume = "52", number = "2", pages = "57--60", doi = "10.1016/0020-0190(94)00130-8", ) @unpublished(sei2014, author = "H. Seidl", year = "2014", title = "Private Communication", ) @inproceedings(DBLP:conf/icalp/SeidlSMH04, author = "H. Seidl and T. Schwentick and A. Muscholl and P. Habermehl", year = "2004", title = "Counting in Trees for Free", booktitle = "ICALP", pages = "1136--1149", doi = "10.1007/978-3-540-27836-8\_94", ) @phdthesis(Servais11, author = "F. Servais", year = "2011", title = "Visibly Pushdown Transducers", school = "Universit{\'e} Libre de Bruxelles", ) @inproceedings(DBLP:conf/fct/StaworkoLLN09, author = "S. Staworko and G. Laurence and A. Lemay and J. Niehren", year = "2009", title = "Equivalence of Deterministic Nested Word to Word Transducers", booktitle = "FCT", pages = "310--322", doi = "10.1007/978-3-642-03409-1\_28", ) @article(DBLP:journals/jcss/Thatcher70, author = "J. W. Thatcher", year = "1970", title = "Generalized Sequential Machine Maps", journal = "J. Comput. Syst. Sci.", volume = "4", number = "4", pages = "339--367", doi = "10.1016/S0022-0000(70)80017-4", ) @article(DBLP:journals/scp/Vogler91, author = "H. Vogler", year = "1991", title = "Functional Description of the Contextual Analysis in Block-Structured Programming Languages: A Case Study of Tree Transducers", journal = "Sci. Comput. Program.", volume = "16", number = "3", pages = "251--275", doi = "10.1016/0167-6423(91)90009-M", ) @phdthesis(DBLP:phd/de/Voigtlander2005, author = "J. Voigtl{\"a}nder", year = "2005", title = "Tree transducer composition as program transformation", school = "Technical University Dresden", ) @article(DBLP:journals/actaC/Zachar80, author = "Z. Zachar", year = "1979", title = "The solvability of the equivalence problem for deterministic frontier-to-root tree transducers", journal = "Acta Cybern.", volume = "4", number = "2", pages = "167--177", )