References

  1. A. V. Aho (1968): Indexed Grammars - An Extension of Context-Free Grammars. J. ACM 15(4), pp. 647–671, doi:10.1145/321479.321488.
  2. A. V. Aho & J. D. Ullman (1971): Translations on a Context-Free Grammar. Information and Control 19(5), pp. 439–475, doi:10.1016/S0019-9958(71)90706-6.
  3. R. Alur & L. D'Antoni (2011): Streaming Tree Transducers. CoRR abs/1104.2599.
  4. R. Alur & P. Madhusudan (2004): Visibly pushdown languages. In: STOC, pp. 202–211, doi:10.1145/1007352.1007390.
  5. Y. Andre & F. Bossut (1995): The Equivalence Problem for Letter-to-Letter Bottom-up Tree Transducers is Solvable. In: TAPSOFT, pp. 155–171, doi:10.1007/3-540-59293-8_193.
  6. Y. Andre & F. Bossut (1998): On the Equivalence Problem for Letter-to-Letter Top-Down Tree Transducers. Theor. Comput. Sci. 205(1-2), pp. 207–229, doi:10.1016/S0304-3975(97)00080-7.
  7. M. Benedikt, J. Engelfriet & S. Maneth (2013): Determinacy and Rewriting of Top-Down and MSO Tree Transformations. In: MFCS, pp. 146–158, doi:10.1007/978-3-642-40313-2_15.
  8. J. Berstel (1979): Transductions and context-free languages. Teubner, Stuttgart.
  9. S. Bozapalidis (1992): Alphabetic Tree Relations. Theor. Comput. Sci. 99(2), pp. 177–211, doi:10.1016/0304-3975(92)90348-J.
  10. M. Caralp, E. Filiot, P.-A. Reynier, F. Servais & J.-M. Talbot (2013): Expressiveness of Visibly Pushdown Transducers. In: TTATT, pp. 17–26, doi:10.4204/EPTCS.134.3.
  11. H. Comon, M. Dauchet, R. Gilleron, F. Jacquemard, C. Löding, D. Lugiez, S. Tison & M. Tommasi (2007): Tree Automata Techniques and Applications. Available at: http://www.grappa.univ-lille3.fr/tata.
  12. B. Courcelle & J. Engelfriet (2012): Graph Structure and Monadic Second-Order Logic - A Language-Theoretic Approach. Encyclopedia of mathematics and its applications 138. Cambridge University Press, doi:10.1017/CBO9780511977619.
  13. B. Courcelle & P. Franchi-Zannettacci (1982): Attribute Grammars and Recursive Program Schemes I. Theor. Comput. Sci. 17, pp. 163–191, doi:10.1016/0304-3975(82)90003-2.
  14. B. Courcelle & P. Franchi-Zannettacci (1982): Attribute Grammars and Recursive Program Schemes II. Theor. Comput. Sci. 17, pp. 235–257, doi:10.1016/0304-3975(82)90024-X.
  15. B. Courcelle & P. Franchi-Zannettacci (1982): On the Equivalence Problem for Attribute Systems. Information and Control 52(3), pp. 275–305, doi:10.1016/S0019-9958(82)90786-0.
  16. K. Culik II (1976): On the Decidability of the Sequence Equivalence Problem for D0L-Systems. Theor. Comput. Sci. 3(1), pp. 75–84, doi:10.1016/0304-3975(76)90066-9.
  17. K. Culik II & I. Fris (1977): The Decidability of the Equivalence Problem for D0L-Systems. Information and Control 35(1), pp. 20–39, doi:10.1016/S0019-9958(77)90512-5.
  18. K. Culik II & J. Karhumäki (1986): A new proof for the D0L Sequence Equivalence Problem and its implications, doi:10.1007/978-3-642-95486-3_5. In: G. Rozenberg & A. Salomaa: The book of L. Springer, Berlin, pp. 63–74.
  19. J. Engelfriet (1977): Top-down Tree Transducers with Regular Look-ahead. Mathematical Systems Theory 10, pp. 289–303, doi:10.1007/BF01683280.
  20. J. Engelfriet (1980): Some open questions and recent results on tree transducers and tree languages. In: R. V. Book: Formal Language Theory; Perspectives and Open Problems. Academic Press, New York.
  21. J. Engelfriet & S. Maneth (1999): Macro Tree Transducers, Attribute Grammars, and MSO Definable Tree Translations. Inf. Comput. 154(1), pp. 34–91, doi:10.1137/S0097539701394511.
  22. J. Engelfriet & S. Maneth (2002): Output String Languages of Compositions of Deterministic Macro Tree Transducers. J. Comput. Syst. Sci. 64(2), pp. 350–395, doi:10.1006/jcss.2001.1816.
  23. J. Engelfriet & S. Maneth (2003): A comparison of pebble tree transducers with macro tree transducers. Acta Inf. 39(9), pp. 613–698, doi:10.1007/s00236-003-0120-0.
  24. J. Engelfriet & S. Maneth (2003): Macro Tree Translations of Linear Size Increase are MSO Definable. SIAM J. Comput. 32(4), pp. 950–1006, doi:10.1137/S0097539701394511.
  25. J. Engelfriet & S. Maneth (2006): The equivalence problem for deterministic MSO tree transducers is decidable. Inf. Process. Lett. 100(5), pp. 206–212, doi:10.1016/j.ipl.2006.05.015.
  26. J. Engelfriet, S. Maneth & H. Seidl (2009): Deciding equivalence of top-down XML transformations in polynomial time. J. Comput. Syst. Sci. 75(5), pp. 271–286, doi:10.1016/j.jcss.2009.01.001.
  27. J. Engelfriet, S. Maneth & H. Seidl (2013): Look-Ahead Removal for Top-Down Tree Transducers. CoRR abs/1311.2400.
  28. J. Engelfriet, G. Rozenberg & G. Slutzki (1980): Tree Transducers, L Systems, and Two-Way Machines. J. Comput. Syst. Sci. 20(2), pp. 150–202, doi:10.1016/0022-0000(80)90058-6.
  29. J. Engelfriet & H. Vogler (1985): Macro Tree Transducers. J. Comput. Syst. Sci. 31(1), pp. 71–146, doi:10.1016/0022-0000(85)90066-2.
  30. Z. Ésik (1981): Decidability results concerning tree transducers I. Acta Cybern. 5(1), pp. 1–20.
  31. J. Esparza (1997): Petri Nets, Commutative Context-Free Grammars, and Basic Parallel Processes. Fundam. Inform. 31(1), pp. 13–25, doi:10.3233/FI-1997-3112.
  32. E. Filiot, J.-F. Raskin, P.-A. Reynier, F. Servais & J.-M. Talbot (2010): Properties of Visibly Pushdown Transducers. In: MFCS, pp. 355–367, doi:10.1007/978-3-642-15155-2_32.
  33. E. Filiot & F. Servais (2012): Visibly Pushdown Transducers with Look-Ahead. In: SOFSEM, pp. 251–263, doi:10.1007/978-3-642-27660-6_21.
  34. M. J. Fischer (1968): Grammars with Marcro-like Productions. Harvard University.
  35. S. Friese (2011): On Normalization and Type Checking for Tree Transducers. Institut für Informatik, Technische Universität München. Available at http://mediatum.ub.tum.de/doc/1078090/1078090.pdf.
  36. S. Friese, H. Seidl & S. Maneth (2011): Earliest Normal Form and Minimization for Bottom-up Tree Transducers. Int. J. Found. Comput. Sci. 22(7), pp. 1607–1623, doi:10.1142/S012905411100891X.
  37. Z. Fülöp & H. Vogler (1998): Syntax-Directed Semantics - Formal Models Based on Tree Transducers. Monographs in Theoretical Computer Science. An EATCS Series. Springer, doi:10.1007/978-3-642-72248-6.
  38. S. Ginsburg (1966): The Mathematical Theory of Context-Free Languages. McGraw-Hill.
  39. S. Ginsburg & E. H. Spanier (1964): Bounded ALGOL-like languages. Trans. Amer. Math. Soc 113, pp. 333–368, doi:10.2307/1994067.
  40. T. V. Griffiths (1968): The Unsolvability of the Equivalence Problem for Lambda-Free Nondeterministic Generalized Machines. J. ACM 15(3), pp. 409–413, doi:10.1145/321466.321473.
  41. E. M. Gurari (1982): The Equivalence Problem for Deterministic Two-Way Sequential Transducers is Decidable. SIAM J. Comput. 11(3), pp. 448–452, doi:10.1137/0211035.
  42. S. Hakuta, S. Maneth, K. Nakano & H. Iwasaki (2014): XQuery Streaming by Forest Transducers. In: ICDE, pp. 417–428.
  43. J. Honkala (2000): A short solution for the HDT0L sequence equivalence problem. Theor. Comput. Sci. 244(1-2), pp. 267–270, doi:10.1016/S0304-3975(00)00158-4.
  44. J. E. Hopcroft & J. D. Ullman (1979): Introduction to Automata Theory, Languages and Computation. Addison-Wesley.
  45. J. Karhumäki, W. Plandowski & W. Rytter (1995): Polynomial Size Test Sets for Context-Free Languages. J. Comput. Syst. Sci. 50(1), pp. 11–19, doi:10.1006/jcss.1995.1002.
  46. D. E. Knuth (1968): Semantics of Context-Free Languages. Mathematical Systems Theory 2(2), pp. 127–145, doi:10.1007/BF01692511.
  47. A. Lemay, S. Maneth & J. Niehren (2010): A learning algorithm for top-down XML transformations. In: PODS, pp. 285–296, doi:10.1145/1807085.1807122.
  48. S. Maneth (2003): The Macro Tree Transducer Hierarchy Collapses for Functions of Linear Size Increase. In: FSTTCS, pp. 326–337, doi:10.1007/978-3-540-24597-1_28.
  49. S. Maneth, A. Berlea, T. Perst & H. Seidl (2005): XML type checking with macro tree transducers. In: PODS, pp. 283–294, doi:10.1145/1065167.1065203.
  50. S. Maneth, T. Perst & H. Seidl (2007): Exact XML Type Checking in Polynomial Time. In: ICDT, pp. 254–268, doi:10.1007/11965893_18.
  51. T. Milo, D. Suciu & V. Vianu (2003): Typechecking for XML transformers. J. Comput. Syst. Sci. 66(1), pp. 66–97, doi:10.1016/S0022-0000(02)00030-2.
  52. K. Nakano & S.-C. Mu (2006): A Pushdown Machine for Recursive XML Processing. In: APLAS, pp. 340–356, doi:10.1007/11924661_21.
  53. R. Parikh (1966): On Context-Free Languages. J. ACM 13(4), pp. 570–581, doi:10.1145/321356.321364.
  54. T. Perst & H. Seidl (2004): Macro forest transducers. Inf. Process. Lett. 89(3), pp. 141–149, doi:10.1016/j.ipl.2003.05.001.
  55. W. Plandowski (1994): Testing Equivalence of Morphisms on Context-Free Languages. In: ESA, pp. 460–470.
  56. J.-F. Raskin & F. Servais (2008): Visibly Pushdown Transducers. In: ICALP (2), pp. 386–397, doi:10.1007/978-3-540-70583-3_32.
  57. W. C. Rounds (1969): Context-Free Grammars on Trees. In: STOC, pp. 143–148, doi:10.1145/800169.805428.
  58. W. C. Rounds (1970): Mappings and Grammars on Trees. Mathematical Systems Theory 4(3), pp. 257–287, doi:10.1007/BF01695769.
  59. K. Ruohonen (1986): Equivalence problems for regular sets of word morphisms, doi:10.1007/978-3-642-95486-3_33. In: G. Rozenberg & A. Salomaa: The book of L. Springer, Berlin, pp. 393–401.
  60. H. Seidl (1992): Single-Valuedness of Tree Transducers is Decidable in Polynomial Time. Theor. Comput. Sci. 106(1), pp. 135–181, doi:10.1016/0304-3975(92)90281-J.
  61. H. Seidl (1994): Equivalence of Finite-Valued Tree Transducers Is Decidable. Mathematical Systems Theory 27(4), pp. 285–346, doi:10.1007/BF01192143.
  62. H. Seidl (1994): Haskell Overloading is DEXPTIME-Complete. Inf. Process. Lett. 52(2), pp. 57–60, doi:10.1016/0020-0190(94)00130-8.
  63. H. Seidl (2014): Private Communication.
  64. H. Seidl, T. Schwentick, A. Muscholl & P. Habermehl (2004): Counting in Trees for Free. In: ICALP, pp. 1136–1149, doi:10.1007/978-3-540-27836-8_94.
  65. F. Servais (2011): Visibly Pushdown Transducers. Université Libre de Bruxelles.
  66. S. Staworko, G. Laurence, A. Lemay & J. Niehren (2009): Equivalence of Deterministic Nested Word to Word Transducers. In: FCT, pp. 310–322, doi:10.1007/978-3-642-03409-1_28.
  67. J. W. Thatcher (1970): Generalized Sequential Machine Maps. J. Comput. Syst. Sci. 4(4), pp. 339–367, doi:10.1016/S0022-0000(70)80017-4.
  68. H. Vogler (1991): Functional Description of the Contextual Analysis in Block-Structured Programming Languages: A Case Study of Tree Transducers. Sci. Comput. Program. 16(3), pp. 251–275, doi:10.1016/0167-6423(91)90009-M.
  69. J. Voigtländer (2005): Tree transducer composition as program transformation. Technical University Dresden.
  70. Z. Zachar (1979): The solvability of the equivalence problem for deterministic frontier-to-root tree transducers. Acta Cybern. 4(2), pp. 167–177.
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org