Weighted Extended Tree Transducers

• Autorzy: Fülöp Z. , Maletti A. , Vogler H.
• Języki publikacji: EN

Abstrakty

EN

Weighted extended tree transducers (wxtts) over countably complete semirings are systematically explored. It is proved that the extension in the left-hand sides of a wxtt can be simulated by the inverse of a linear and nondeleting tree homomorphism. In addition, a characterization of the class of weighted tree transformations computable by bottom-up wxtts in terms of bimorphisms is provided. Backward and forward application to recognizable weighted tree languages are standard operations for wxtts. It is shown that the backward application of a linear wxtt preserves recognizability and that the domain of an arbitrary bottom-up wxtt is recognizable. Examples demonstrate that neither backward nor forward application of arbitrary wxtts preserves recognizability. Finally, a HASSE diagram relates most of the important subclasses of weighted tree transformations computable by wxtts.

Słowa kluczowe

EN

weighted tree transducer; preservation of recognizability; HASSE diagram; forward application; backward application

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2011
• Tom: Vol. 111, nr 2
• Strony: 163--202
• Opis fizyczny: Bibliogr. 59 poz.

Twórcy

autor

Fülöp Z.

autor

Maletti A.

autor

Vogler H.

• Universität Stuttgart, Institute for Natural Language Processing, Azenbergstr. 12, D-70174 Stuttgart, Germany,

Bibliografia

• [1] Alexandrakis, A., Bozapalidis, S.: Weighted grammars and Kleene's theorem, Inform. Process. Lett., 24(1), 1987, 1-4.
• [2] Arnold, A., Dauchet, M.: Bi-transduction de forêts, Proc. 3rd Int. Coll. Automata, Languages and Programming, Edinburgh University Press, 1976.
• [3] Arnold, A., Dauchet,M.: Morphismes et bimorphismes d'arbres, Theoret. Comput. Sci., 20(1), 1982, 33-93.
• [4] Berstel, J., Reutenauer, C.: Recognizable formal power series on trees, Theoret. Comput. Sci., 18(2), 1982, 115-148.
• [5] Borchardt, B.: The Theory of Recognizable Tree Series, Ph.D. Thesis, Technische Universität Dresden, 2004, Available at: Verlag fürWissenschaft und Forschung, Berlin.
• [6] Comon, H., Dauchet,M., Gilleron, R., Jacquemard, F., Löding, C., Lugiez, D., Tison, S., Tommasi, M.: Tree Automata Techniques and Applications, Available on: htp:/ta.gforge.inria.fr, 2007.
• [7] Droste, M., Kuich,W., Vogler, H., Eds.: Handbook of Weighted Automata, EATCS Monographs in Theoretical Computer Science, Springer-Verlag, Heidelberg, 2009.
• [8] Eilenberg, S.: Automata, Languages, and Machines - Volume A, vol. 59 of Pure and Applied Mathematics, Academic Press, New York, 1974.
• [9] Eisner, J.: Learning non-isomorphic tree mappings for machine translation, Companion volume of Proc. 41st Ann. Meeting of the ACL (Y. Matsumoto, Ed.), Association for Computational Linguistics, 2003.
• [10] Engelfriet, J.: Bottom-up and top-down tree transformations - a comparison, Math. Systems Theory, 9(3), 1975, 198-231.
• [11] Engelfriet, J.: Top-down tree transducers with regular look-ahead, Math. Systems Theory, 10(1), 1977, 289-303.
• [12] Engelfriet, J., Fülöp, Z., Vogler, H.: Bottom-up and top-down tree series transformations, J. Autom. Lang. Comb., 7(1), 2002, 11-70.
• [13] Engelfriet, J., Lilin, E., Maletti, A.: Composition and decomposition of extended multi bottom-up tree transducers, Acta Inform., 46(8), 2009, 561-590.
• [14] Engelfriet, J., Rozenberg, G., Slutzki, G.: Tree transducers, L systems, and two-way machines, J. Comput. System Sci., 20(2), 1980, 150-202.
• [15] Ésik, Z., Kuich,W.: Formal tree series, J. Autom. Lang. Comb., 8(2), 2003, 219-285.
• [16] Fülöp, Z., Maletti, A., Vogler, H.: Preservation of recognizability for synchronous tree substitution grammars, Proc. Applications of Tree Automata in Natural Language Processing, Association for Computational Linguistics, 2010.
• [17] Fülöp, Z., Vogler, H.: Syntax-directed Semantics-Formal Models Based on Tree Transducers, Monographs on Theoret. Comput. Sci. - An EATCS Series, Springer-Verlag, Heidelberg, 1998.
• [18] Fülöp, Z., Vogler, H.: Weighted tree automata and tree transducers, in: Droste et al. [7], chapter 9, 313-403.
• [19] Galley, M., Hopkins, M., Knight, K., Marcu, D.: What's in a translation rule?, Proc. Human Language Technology Conf. of the North American Chapter of the ACL (S. Dumais, D. Marcu, S. Roukos, Eds.), Association for Computational Linguistics, 2004.
• [20] Gécseg, F., Steinby, M.: Tree Automata, Akadémiai Kiadó, Budapest, 1984.
• [21] Gécseg, F., Steinby, M.: Tree Languages, in: Handbook of Formal Languages (G. Rozenberg, A. Salomaa, Eds.), vol. 3, chapter 1, Springer-Verlag, Heidelberg, 1997, 1-68.
• [22] Golan, J.: Semirings and their Applications, Kluwer Academic Publishers, Dordrecht, 1999.
• [23] Graehl, J., Knight, K.: Training tree transducers, Proc. Human Language Technology Conf. of the North American Chapter of the ACL (S. Dumais, D. Marcu, S. Roukos, Eds.), Association for Computational Linguistics, 2004.
• [24] Graehl, J., Knight, K., May, J.: Training tree transducers, Comput. Linguist., 34(3), 2008, 391-427.
• [25] Hebisch, U., Weinert, H.: Semirings - Algebraic Theory and Applications in Computer Science, World Scientific, Singapore, 1998.
• [26] Huang, L., Chiang, D.: Better k-best parsing, Proc. 9th Int. Workshop on Parsing Technology (H. Bunt, R. Malouf, A. Lavie, Eds.), Association for Computational Linguistics, 2005.
• [27] Karner, G.: Continuous monoids and semirings, Theoret. Comput. Sci., 318(3), 2004, 355-372.
• [28] Knight, K.: Capturing practical natural language transformations, Machine Translation, 21(2), 2007, 121-133.
• [29] Knight, K., Graehl, J.: An overview of probabilistic tree transducers for natural language processing, Proc. 6th Int. Conf. Computational Linguistics and Intelligent Text Processing (A. Gelbukh, Ed.), number 3406 in Lecture Notes in Computer Science, Springer-Verlag, Heidelberg, 2005.
• [30] Koehn, P.: Statistical Machine Translation, Cambridge University Press, 2010.
• [31] Kuich,W.: Formal power series over trees, Proc. 3rd Int. Conf. Developments in Language Theory (S. Bozapalidis, Ed.), Aristotle University of Thessaloniki, 1998.
• [32] Kuich,W.: Tree transducers and formal tree series, Acta Cybernet., 14(1), 1999, 135-149.
• [33] Kuich, W., Salomaa, A.: Semirings, Automata, Languages, Number 5 in Monographs on Theoret. Comput. Sci.- An EATCS Series, Springer-Verlag, Heidelberg, 1986.
• [34] Lopez, A.: Statistical machine translation, ACM Computing Surveys, 40(3), 2008.
• [35] Maletti, A.: Compositions of tree series transformations, Theoret. Comput. Sci., 366(3), 2006, 248-271.
• [36] Maletti, A.: Hierarchies of tree series transformations revisited, Proc. 10th Int. Conf. Developments in Language Theory (O. Ibarra, Z. Dang, Eds.), number 4036 in Lecture Notes in Computer Science, Springer-Verlag, Heidelberg, 2006.
• [37] Maletti, A.: Compositions of extended top-down tree transducers, Inform. and Comput., 206(9-10), 2008, 1187-1196.
• [38] Maletti, A.: Input products for weighted extended top-down tree transducers, Proc. 14th Int. Conf. Developments in Language Theory (Y. Gao, S. Yu, Eds.), number 6224 in Lecture Notes in Computer Science, Springer-Verlag, Heidelberg, 2010.
• [39] Maletti, A.: Weighted multi bottom-up tree transducers, Nat. Lang. Engrg., 17(2), 2011, 221-242.
• [40] Maletti, A., Graehl, J., Hopkins, M., Knight, K.: The power of extended top-down tree transducers, SIAM J. Comput., 39(2), 2008, 410-430.
• [41] Maletti, A., Satta, G.: Parsing algorithms based on tree automata, Proc. 11th Int. Conf. Parsing Technologies (E. Villemonte de la Clergerie, H. Bunt, L. Danlos, Eds.), Association for Computational Linguistics, 2009.
• [42] May, J., Knight, K.: Tiburon: a weighted tree automata toolkit, Proc. 11th Int. Conf. Implementation and Application of Automata (O. Ibarra, H. Yen, Eds.), number 4094 in Lecture Notes in Computer Science, Springer-Verlag, Heidelberg, 2006.
• [43] May, J., Knight, K., Vogler, H.: Efficient inference through cascades of weighted tree transducers, Proc. 48th Ann. Meeting of the ACL (J. Hajiˇc, S. Carberry, S. Clark, J. Nivre, Eds.), Association for Computational Linguistics, 2010.
• [44] Milo, T., Suciu, D., Vianu, V.: Typechecking for XML transformers, J. Comput. System Sci., 66(1), 2003, 66-97.
• [45] Nesson, R., Shieber, S. M., Rush, A.: Induction of probabilistic synchronous tree-insertion grammars, Technical Report TR-20-05, Computer Science Group, Harvard University, Cambridge,MA, 2005.
• [46] Nesson, R., Shieber, S. M., Rush, A.: Induction of probabilistic synchronous tree-insertion grammars for machine translation, Proc. 7th Int. Conf. of the Association for Machine Translation in the Americas, 2006.
• [47] Rounds, W.: Mappings and grammars on trees, Math. Systems Theory, 4(3), 1970, 257-287.
• [48] Shieber, S.: Synchronous grammars as tree transducers, Proc. 7th Int.Workshop on Tree AdjoiningGrammars and Related Formalisms, 2004.
• [49] Shieber, S. M.: Probabilistic synchronous tree-adjoining grammars for machine translation: the argument from bilingual dictionaries, Proc. Workshop on Syntax and Structure in Statistical Translation (D. Wu, D. Chiang, Eds.), Association for Computational Linguistics, 2007.
• [50] Shieber, S. M., Schabes, Y.: Synchronous tree-adjoining grammars, Proc. 13th Int. Conf. Computational Linguistics, Helsinki, Finland, 1990.
• [51] Sun, J., Zhang,M., Tan, C. L.: A non-contiguous tree sequence alignment-basedmodel for statistical machine translation, Proc. 47th Annual Meeting of the ACL (K.-Y. Su, J. Su, J. Wiebe, H. Li, Eds.), Association for Computational Linguistics, 2009.
• [52] Thatcher, J.: Generalized2 sequential machine maps, J. Comput. System Sci., 4(4), 1970, 339-367.
• [53] Thatcher, J.: There's a lot more to automata theory than you would have thought, Proc. 4th Ann. Princeton Conf. on Informations Sciences and Systems, 1970.
• [54] Thatcher, J.: Tree automata: an informal survey, in: Currents in the Theory of Computing (A. Aho, Ed.), Prentice Hall, Englewood Cliffs, NJ, 1973, 143-172.
• [55] Wang, H.: On characters of semirings, Houston J. Math., 23(3), 1997, 391-405.
• [56] Wang, H.: On rational series and rational languages, Theoret. Comput. Sci., 205(1-2), 1998, 329-336.
• [57] Yamada, K., Knight, K.: A syntax-based statistical translation model, Proc. 39th Ann. Meeting of the ACL, Association for Computational Linguistics, 2001.
• [58] Zhang,M., Jiang, H., Aw, A., Li, H., Tan, C. L., Li, S.: A tree sequence alignment-based tree-to-tree translation model, Proc. 46th Ann.Meeting of the ACL (J. D.Moore, S. Teufel, J. Allan, S. Furui, Eds.), Association for Computational Linguistics, 2008.
• [59] Zhang, M., Jiang, H., Li, H., Aw, A., Li, S.: Grammar comparison study for translational equivalence modeling and statistical machine translation, Proc. 22nd Int. Conference Computational Linguistics, Association for Computational Linguistics, 2008.