Survey: Weighted Extended Top-Down Tree Transducers Part III -Composition
详细信息 查看全文
- 作者：Aurélie Lagoutte (18)
Andreas Maletti (19) - 关键词：weighted tree transducer ; top ; down tree transducer ; composition ; deletion ; copying
- 刊名：Lecture Notes in Computer Science
- 出版年：2011
- 出版时间：2011
- 年：2011
- 卷：7020
- 期：1
- 页码：309-346
- 全文大小：463KB
- 参考文献：1. Alexandrakis, A., Bozapalidis, S.: Weighted grammars and Kleene’s theorem. Inf. Process. Lett.?24(1), 1- (1987) CrossRef
2. Arnold, A., Dauchet, M.: Bi-transductions de forêts. In: Michaelson, S., Milner, R. (eds.) ICALP 1976, pp. 74-6. Edinburgh University Press, Edinburgh (1976)
3. Arnold, A., Dauchet, M.: Morphismes et bimorphismes d’arbres. Theoret. Comput. Sci.?20(4), 33-3 (1982) CrossRef
4. Baader, F., Nipkow, T.: Term Rewriting and All That. Cambridge University Press, Cambridge (1998)
5. Baker, B.S.: Composition of top-down and bottom-up tree transductions. Inform. and Control?41(2), 186-13 (1979) CrossRef
6. Berstel, J., Reutenauer, C.: Recognizable formal power series on trees. Theoret. Comput. Sci.?18(2), 115-48 (1982) CrossRef
7. Borchardt, B.: The Theory of Recognizable Tree Series. Ph.D. thesis, Technische Universit?t Dresden (2005)
8. Borchardt, B., Vogler, H.: Determinization of finite state weighted tree automata. J. Autom. Lang. Combin.?8(3), 417-63 (2003)
9. Bozapalidis, S., Louscou-Bozapalidou, O.: The rank of a formal tree power series. Theoret. Comput. Sci.?27(1-2), 211-15 (1983) CrossRef
10. Comon, H., Dauchet, M., Gilleron, R., Jacquemard, F., Lugiez, D., L?ding, C., Tison, S., Tommasi, M.: Tree automata techniques and applications (2007), http://tata.gforge.inria.fr
11. Dauchet, M.: Transductions inversibles de forêts. Thèse 3ème cycle, Université?de?Lille (1975)
12. Engelfriet, J.: Bottom-up and top-down tree transformations: A comparison. Math. Systems Theory?9(3), 198-31 (1975) CrossRef
13. Engelfriet, J.: Top-down tree transducers with regular look-ahead. Math. Systems Theory?10(1), 289-03 (1976) CrossRef
14. Engelfriet, J., Fül?p, Z., Vogler, H.: Bottom-up and top-down tree series transformations. J. Autom. Lang. Combin.?7(1), 11-0 (2002)
15. Engelfriet, J., Lilin, E., Maletti, A.: Extended multi bottom-up tree transducers. In: Ito, M., Toyama, M. (eds.) DLT 2008. LNCS, vol.?5257, pp. 289-00. Springer, Heidelberg (2008) CrossRef
16. Engelfriet, J., Lilin, E., Maletti, A.: Composition and decomposition of extended multi bottom-up tree transducers. Acta Inform.?46(8), 561-90 (2009) CrossRef
17. ésik, Z., Kuich, W.: Formal tree series. J. Autom. Lang. Combin.?8(2), 219-85 (2003)
18. Fül?p, Z., Gazdag, Z., Vogler, H.: Hierarchies of tree series transformations. Theoret. Comput. Sci.?314(3), 387-29 (2004) CrossRef
19. Fül?p, Z., Vogler, H.: Tree series transformations that respect copying. Theory Comput. Systems?36(3), 247-93 (2003) CrossRef
20. Fül?p, Z., Vogler, H.: Weighted tree automata and tree transducers. In: Droste, M., Kuich, W., Vogler, H. (eds.) Handbook of Weighted Automata, ch. 9, pp. 313-03. Springer, Heidelberg (2009) CrossRef
21. Gécseg, F., Steinby, M.: Tree Automata. Akadémiai Kiadó, Budapest (1984)
22. Gécseg, F., Steinby, M.: Tree languages. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages, vol.?3, ch. 1, pp. 1-8. Springer, Heidelberg (1997) CrossRef
23. Golan, J.S.: Semirings and their Applications. Kluwer Academic, Dordrecht (1999)
24. Graehl, J., Knight, K., May, J.: Training tree transducers. Comput. Linguist.?34(3), 391-27 (2008) CrossRef
25. Hebisch, U., Weinert, H.J.: Semirings -Algebraic Theory and Applications in Computer Science. Algebra, vol.?5. World Scientific, Singapore (1998)
26. Knight, K., Graehl, J.: An overview of probabilistic tree transducers for natural language processing. In: Gelbukh, A.F. (ed.) CICLing 2005. LNCS, vol.?3406, pp. 1-4. Springer, Heidelberg (2005) CrossRef
27. Koehn, P.: Statistical Machine Translation. Cambridge University Press, Cambridge (2010)
28. Koehn, P., Och, F.J., Marcu, D.: Statistical phrase-based translation. In: NAACL 2003, pp. 48-4. Association for Computational Linguistics (2003)
29. Kühnemann, A.: Benefits of tree transducers for optimizing functional programs. In: Arvind, V., Sarukkai, S. (eds.) FST TCS 1998. LNCS, vol.?1530, pp. 146-58. Springer, Heidelberg (1998) CrossRef
30. Kuich, W.: Formal power series over trees. In: Bozapalidis, S. (ed.) DLT 1997, pp. 61-01. Aristotle University of Thessaloniki (1998)
31. Kuich, W.: Full abstract families of tree series I. In: Karhum?ki, J., Maurer, H.A., Paun, G., Rozenberg, G. (eds.) Jewels are Forever, pp. 145-56. Springer, Heidelberg (1999) CrossRef
32. Kuich, W.: Tree transducers and formal tree series. Acta Cybernet.?14(1), 135-49 (1999)
33. Maletti, A.: Compositions of tree series transformations. Theoret. Comput. Sci.?366(3), 248-71 (2006) CrossRef
34. Maletti, A.: The Power of Tree Series Transducers. Ph.D. thesis, Technische Universit?t Dresden (2006)
35. Maletti, A.: Compositions of extended top-down tree transducers. Inform. and Comput.?206(9-10), 1187-196 (2008) CrossRef
36. Maletti, A.: Survey: Weighted extended top-down tree transducers -Part?I: Basics and expressive power. Acta Cybernet (2011), preprint available at: http://www.ims.uni-stuttgart.de/~maletti/pub/mal11.pdf
37. Maletti, A.: Survey: Weighted extended top-down tree transducers -Part?II: Application in machine translation. Fund. Inform (2011)
38. Maletti, A., Graehl, J., Hopkins, M., Knight, K.: The power of extended top-down tree transducers. SIAM J. Comput.?39(2), 410-30 (2009) CrossRef
39. Maletti, A., Vogler, H.: Compositions of top-down tree transducers with / ε-rules. In: Yli-Jyr?, A., Kornai, A., Sakarovitch, J., Watson, B. (eds.) FSMNLP 2009. LNCS (LNAI), vol.?6062, pp. 69-0. Springer, Heidelberg (2010) CrossRef
40. May, J., Knight, K., Vogler, H.: Efficient inference through cascades of weighted tree transducers. In: ACL 2010, pp. 1058-066. Association for Computational Linguistics (2010)
41. Rounds, W.C.: Mappings and grammars on trees. Math. Systems Theory?4(3), 257-87 (1970) CrossRef
42. Thatcher, J.W.: Generalized2 sequential machine maps. J. Comput. System Sci.?4(4), 339-67 (1970) CrossRef
43. Thatcher, J.W.: Tree automata: An informal survey. In: Aho, A.V. (ed.) Currents in the Theory of Computing, ch. 4, pp. 143-72. Prentice Hall, Englewood Cliffs (1973)
44. Wang, H.: On characters of semirings. Houston J. Math.?23(3), 391-05 (1997)
45. Wang, H.: On rational series and rational languages. Theoret. Comput. Sci.?205(1-2), 329-36 (1998) CrossRef
46. Yamada, K., Knight, K.: A decoder for syntax-based statistical MT. In: ACL 2002, pp. 303-10. Association for Computational Linguistics (2002) - 作者单位：Aurélie Lagoutte (18)
Andreas Maletti (19)
18. Département Informatique, école normale supérieure de Cachan, 61, avenue du Président Wilson, 94235, Cachan cedex, France
19. Institute for Natural Language Processing, Universit?t Stuttgart, Azenbergstra?e?12, 70174, Stuttgart, Germany
文摘
In this survey (functional) compositions of weighted tree transformations computable by weighted extended top-down tree transducers are investigated. The existing results in the literature are explained and illustrated. It is argued, why certain compositions are not possible in the general case, and 3?informed conjectures provide an insight into potentially 3?new composition results that extend and complement the existing results. In particular, if all were true, then the beautiful symmetry in the composition results for weighted top-down and bottom-up tree transducers would be recovered.