Abstract
Extended multi bottom-up tree transducers are defined and investigated. They are an extension of multi bottom-up tree transducers by arbitrary, not just shallow, left-hand sides of rules; this includes rules that do not consume input. It is shown that such transducers can compute any transformation that is computed by a linear extended top-down tree transducer. Moreover, the classical composition results for bottom-up tree transducers are generalized to extended multi bottom-up tree transducers. Finally, a characterization in terms of extended top-down tree transducers is presented.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Knight, K.: Criteria for reasonable syntax-based translation models. Personal communication (2007)
Knight, K., Graehl, J.: An overview of probabilistic tree transducers for natural language processing. In: Gelbukh, A. (ed.) CICLing 2005. LNCS, vol. 3406, pp. 1–24. Springer, Heidelberg (2005)
DeNeefe, S., Knight, K., Wang, W., Marcu, D.: What can syntax-based MT learn from phrase-based MT? In: EMNLP & CoNLL, pp. 755–763 (2007)
Hopcroft, J.E., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation. Addison Wesley, Reading (1979)
Graehl, J., Knight, K.: Training tree transducers. In: HLT-NAACL, pp. 105–112 (2004)
Arnold, A., Dauchet, M.: Transductions inversibles de forêts. Thèse 3ème cycle M. Dauchet, Université de Lille (1975)
Arnold, A., Dauchet, M.: Bi-transductions de forêts. In: ICALP, pp. 74–86. Edinburgh University Press (1976)
Rounds, W.C.: Mappings and grammars on trees. Math. Systems Theory 4(3), 257–287 (1970)
Thatcher, J.W.: Generalized2 sequential machine maps. J. Comput. System Sci. 4(4), 339–367 (1970)
Steinby, M., Tîrnăucă, C.I.: Syntax-directed translations and quasi-alphabetic tree bimorphisms. In: Holub, J., Žďárek, J. (eds.) CIAA 2007. LNCS, vol. 4783, pp. 265–276. Springer, Heidelberg (2007)
Aho, A.V., Ullman, J.D.: Syntax directed translations and the pushdown assembler. J. Comput. System Sci. 3(1), 37–56 (1969)
Shabes, Y.: Mathematical and Computational Aspects of Lexicalized Grammars. PhD thesis, University of Pennsylvania (1990)
Shieber, S.M., Shabes, Y.: Synchronous tree-adjoining grammars. In: COLING, pp. 1–6 (1990)
Shieber, S.M.: Unifying synchronous tree adjoining grammars and tree transducers via bimorphisms. In: EACL. The Association for Computer Linguistics, pp. 377–384 (2006)
Arnold, A., Dauchet, M.: Morphismes et bimorphismes d’arbres. Theoret. Comput. Sci. 20, 33–93 (1982)
Fülöp, Z., Kühnemann, A., Vogler, H.: A bottom-up characterization of deterministic top-down tree transducers with regular look-ahead. Inf. Process. Lett. 91(2), 57–67 (2004)
Fülöp, Z., Kühnemann, A., Vogler, H.: Linear deterministic multi bottom-up tree transducers. Theoret. Comput. Sci. 347(1–2), 276–287 (2005)
Maletti, A.: Compositions of extended top-down tree transducers. Inform. and Comput. (to appear, 2008)
Engelfriet, J.: Bottom-up and top-down tree transformations: A comparison. Math. Systems Theory 9(3), 198–231 (1975)
Baker, B.S.: Composition of top-down and bottom-up tree transductions. Inform. and Control 41(2), 186–213 (1979)
Thatcher, J.W.: Tree automata: An informal survey. In: Currents in the Theory of Computing, pp. 143–172. Prentice Hall, Englewood Cliffs (1973)
Ganzinger, H.: Increasing modularity and language-independency in automatically generated compilers. Sci. Comput. Prog. 3(3), 223–278 (1983)
Giegerich, R.: Composition and evaluation of attribute coupled grammars. Acta Inform. 25(4), 355–423 (1988)
Kühnemann, A.: Berechnungsstärken von Teilklassen primitiv-rekursiver Programmschemata. PhD thesis, Technische Universität Dresden (1997)
Kühnemann, A.: Benefits of tree transducers for optimizing functional programs. In: Arvind, V., Ramanujam, R. (eds.) FST TCS 1998. LNCS, vol. 1530, pp. 146–157. Springer, Heidelberg (1998)
Engelfriet, J., Maneth, S.: Macro tree transducers, attribute grammars, and MSO definable tree translations. Inform. and Comput. 154(1), 34–91 (1999)
Engelfriet, J.: Top-down tree transducers with regular look-ahead. Math. Systems Theory 10(1), 289–303 (1977)
Gécseg, F., Steinby, M.: Tree Automata. Akadémiai Kiadó, Budapest (1984)
Gécseg, F., Steinby, M.: Tree languages. In: Handbook of Formal Languages, vol. 3, pp. 1–68. Springer, Heidelberg (1997)
Lilin, E.: Une généralisation des transducteurs d’états finis d’arbres: les S-transducteurs. Thèse 3ème cycle, Université de Lille (1978)
Lilin, E.: Propriétés de clôture d’une extension de transducteurs d’arbres déterministes. In: Astesiano, E., Böhm, C. (eds.) CAAP 1981. LNCS, vol. 112, pp. 280–289. Springer, Heidelberg (1981)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Engelfriet, J., Lilin, E., Maletti, A. (2008). Extended Multi Bottom-Up Tree Transducers. In: Ito, M., Toyama, M. (eds) Developments in Language Theory. DLT 2008. Lecture Notes in Computer Science, vol 5257. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-85780-8_23
Download citation
DOI: https://doi.org/10.1007/978-3-540-85780-8_23
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-85779-2
Online ISBN: 978-3-540-85780-8
eBook Packages: Computer ScienceComputer Science (R0)