Alphabetic Pushdown Tree Transducers

  • George Rahonis
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 2710)


We introduce the concept of an alphabetic pushdown tree transducer, by adding a stack to an alphabetic tree transducer in the same way as a pushdown tree automaton is obtained from a top-down tree automaton. The stack of the general model contains trees, however, we also consider a restricted model of which the stack contains only unary trees. We give a characterization of the tree transformation induced by a restricted alphabetic pushdown tree transducer in terms of an algebraic forest over a suitable ranked alphabet and a bimorphism. We compare the class of tree relations induced by the alphabetic pushdown tree transducers with known classes of tree transformations. Finally, a new hierarchy of tree relations is established.


Tree Relation Restricted Model Tree Automaton Tree Language Algebraic Characterization 
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.


Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.


  1. 1.
    A.V. Aho and J.D. Ullman, The Theory of Parsing, Translation and Compiling, Vol1, Prentice-Hall, Englewood Cliffs, NJ, 1972.Google Scholar
  2. 2.
    S. Bozapalidis, Alphabetic tree relations, Theoret. Comput. Sci. 99 (1992) 177–211.zbMATHCrossRefMathSciNetGoogle Scholar
  3. 3.
    S. Bozapalidis and G. Rahonis, On two families of forests, Acta Inform. 31 (1994) 235–260.zbMATHCrossRefMathSciNetGoogle Scholar
  4. 4.
    C. Choffrut and K. Culik II, Properties of finite and pushdown transducers, Siam J. Comput. 12,2, (1983) 300–315.zbMATHCrossRefMathSciNetGoogle Scholar
  5. 5.
    J. Engelfriet, Bottom-up and top-down tree transformations. A comparison, Math. Systems Theory 9 (1975) 198–231.zbMATHCrossRefMathSciNetGoogle Scholar
  6. 6.
    J. Engelfriet, Top-down tree transducers with regular look-ahead, Math. Systems Theory 10 (1976/1977) 289–303.CrossRefMathSciNetGoogle Scholar
  7. 7.
    J. Engelfriet and H. Vogler, Macro Tree Transducers, J. Comput. System Sci. 31 (1985) 71–146.zbMATHCrossRefMathSciNetGoogle Scholar
  8. 8.
    M. Fliess, Transductions algébriques, R.A.I.R.O. R1 (1970) 109–125.MathSciNetGoogle Scholar
  9. 9.
    Z. Fülöp and S. Vágvölgyi, Iterated deterministic top-down look-ahead, Lecture Notes in Computer Science 380 (1989) 175–184.Google Scholar
  10. 10.
    Z. Fülöp and S. Vágvölgyi, Top-down tree transducers with regular look-ahead, Inform. Process. Lett. 33 (1989/1990) 3–5.zbMATHCrossRefMathSciNetGoogle Scholar
  11. 11.
    Z. Fülöp and S. Vágvölgyi, Variants of top-down tree transducers with look-ahead, Math. Systems Theory 21 (1989) 125–145.CrossRefMathSciNetGoogle Scholar
  12. 12.
    Z. Fülöp and H. Vogler, Syntax-Directed Semantics, Springer-Verlag, 1998.Google Scholar
  13. 13.
    F. Gécseg and M. Steinby, Tree Automata, Akadémiai Kiadó, Budapest 1984.zbMATHGoogle Scholar
  14. 14.
    F. Gécseg and M. Steinby, Tree Languages, in: Handbook of Formal Languages, Vol III, G. Rozenberg and A. Salomaa, eds., Springer-Verlag, 1997, pp.1–68.Google Scholar
  15. 15.
    I. Guessarian, Pushdown tree automata, Math. Systems Theory 16 (1983) 237–263.zbMATHCrossRefMathSciNetGoogle Scholar
  16. 16.
    G. Rahonis and K. Salomaa, On the size of stack and synchronization alphabets of tree automata, Fund. Inform. 36 (1998) 57–69.zbMATHMathSciNetGoogle Scholar
  17. 17.
    G. Rahonis, Alphabetic and synchronized tree transducers, Theoret. Comput. Sci. 255 (2001) 377–399.zbMATHCrossRefMathSciNetGoogle Scholar
  18. 18.
    G. Rahonis, Alphabetic pushdown tree transducers, Dept. of Mathematics, University of Thessaloniki, Greece, preprint.Google Scholar
  19. 19.
    K. Salomaa, Synchronized tree automata, Theoret. Comput. Sci. 127 (1994) 25–51.zbMATHCrossRefMathSciNetGoogle Scholar
  20. 20.
    K. Yamasaki, Fundamental Properties of Pushdown Tree Transducers (PDTT) — A Top-Down Case, IEICE Trans. Inf. & Syst. E76-D,10 (1993) 1234–1242.Google Scholar
  21. 21.
    K. Yamasaki, Note on Domain/Surface Tree Languages of t-PDTT’s, IEICE Trans. Inf. & Syst. E79-D,6 (1996) 829–839.Google Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2003

Authors and Affiliations

  • George Rahonis
    • 1
  1. 1.Department of MathematicsAristotle University of ThessalonikiThessalonikiGreece

Personalised recommendations