The time complexity of typechecking tree-walking tree transducers

1. Aho, A.V., Lam, M.S., Sethi, R., Ullman, J.D.: Compilers: Principles, Techniques, and Tools, 2nd edn. Addison-Wesley, Reading, MA, USA (2006)

2. Bartha, M.: An algebraic definition of attributed transformations, Acta Cybernetica 5, 409–421 (1982). In: Gécseg, F. (ed.) Preliminary version. Proc. FCT’81. Lecture Notes in Computer Science 117, pp. 51–60. Springer, Berlin (1981)

   Google Scholar 

3. Engelfriet, J.: The complexity of the circularity problem for attribute grammars: a note on a counterexample for a simpler construction, SIGACT News, Summer, pp. 57–59 (1989)

4. Engelfriet J., Filè G. (1981) Passes and paths of attribute grammars. Inf. Control 49: 125–169

   Article  MATH  Google Scholar 

5. Engelfriet, J., Hoogeboom, H.J., Samwel, B.: XML transformation by tree-walking transducers with invisible pebbles. In: Libkin, L. (ed.) Proc. PODS’07, pp. 63–72. ACM Press, New York (2007)

6. Engelfriet J., Maneth S. (2003) A comparison of pebble tree transducers with macro tree transducers. Acta Informatica 39: 613–698

   Article  MATH  MathSciNet  Google Scholar 

7. Fülöp Z. (1981) On attributed tree transducers. Acta Cybernetica 5: 261–279

   MATH  Google Scholar 

8. Fülöp, Z., Vogler, H.: Syntax-directed semantics, formal models based on tree transducers. In: Monographs in Theoretical Computer Science, An EATCS Series. Springer, Berlin (1998)

9. Jazayeri M. (1981) A simpler construction for showing the intrinsically exponential complexity of the circularity problem for attribute grammars. J. ACM 28: 715–720

   Article  MATH  MathSciNet  Google Scholar 

10. Jazayeri M., Ogden W.F., Rounds W.C. (1975) The intrinsically exponential complexity of the circularity problem for attribute grammars. Commun. ACM 18: 697–706

    Article  MATH  MathSciNet  Google Scholar 

11. Kamimura T. (1983) Tree automata and attribute grammars. Inf. Control 57: 1–20

    Article  MATH  MathSciNet  Google Scholar 

12. Kamimura T., Slutzki G. (1981) Parallel and two-way automata on directed ordered acyclic graphs. Inf. Control 49: 10–51

    Article  MATH  MathSciNet  Google Scholar 

13. Knuth, D.E.: Semantics of context-free languages. Math. Systems Theory 2, 127–145 (1968). Correction: Math. Systems Theory 5, 95–96 (1971)

14. Maneth, S., Berlea, A., Perst, T., Seidl, H.: XML type checking with macro tree transducers. In: Proc. PODS’05, pp. 283–294. ACM Press, New York (2005)

15. Milo T., Suciu D., Vianu V. (2003) Typechecking for XML transformers. J. Comput. Syst. Sci. 66: 66–97

    Article  MATH  MathSciNet  Google Scholar 

16. Neven, F.: Automata, Logic, and XML. In: Bradfield, J.C. (ed.) Proc. CSL’02. Lecture Notes in Computer Science, vol. 2471, pp. 2–26. Springer, Berlin (2002)

17. Perst T., Seidl H. (2004) Macro forest transducers. Inf. Process. Lett. 89: 141–149

    Article  MathSciNet  Google Scholar 

18. Samuelides, M., Segoufin, L.: Complexity of pebble tree-walking automata. In: Csuhaj-Varjú, E., Ésik, Z. (eds.) Proc. FCT’07. Lecture Notes in Computer Science, vol. 4639, pp. 458–469. Springer, Berlin (2007)

19. Slutzki G. (1985) Alternating tree automata. Theor. Comput. Sci. 41: 305–318

    Article  MATH  MathSciNet  Google Scholar 

20. Yashiro, T.: Typechecking k-pebble tree transducers: practical efficiency. Bachelor Thesis, University of Tokyo, February 2006

Download references