Bimorphisms and synchronous grammars

• Autorzy: Shieber S. M.

Identyfikatory

DOI

10.15398/jlm.v2i1.84

• Języki publikacji: EN

Abstrakty

EN

We tend to think of the study of language as proceeding by characterizing the strings and structures of a language, and we think of natural-language processing as using those structures to build systems of utility in manipulating the language. But many language-related problems are more fruitfully viewed as requiring the specification of a relation between two languages, rather than the specification of a single language. In this paper, we provide a synthesis and extension of work that unifies two approaches to such language relations: the automata-theoretic approach based on tree transducers that transform trees to their counterparts in the relation, and the grammatical approach based on synchronous grammars that derive pairs of trees in the relation. In particular, we characterize synchronous tree-substitution grammars and synchronous tree-adjoining grammars in terms of bimorphisms, which have previously been used to characterize tree transducers. In the process, we provide new approaches to formalizing the various concepts: a metanotation for describing varieties of tree automata and transducers in equational terms; a rigorous formalization of tree-adjoining and tree-substitution grammars and their synchronous counterparts, using trees over ranked alphabets; and generalizations of tree-adjoining grammar allowing multiple adjunction.

Słowa kluczowe

EN

synchronous grammars; tree transducers; tree-adjoining grammars; tree-substitution grammars

• Wydawca: Instytut Podstaw Informatyki PAN
• Czasopismo: Journal of Language Modelling
• Rocznik: 2014
• Tom: Vol. 2, No. 1
• Strony: 51--104
• Opis fizyczny: Bibliogr. 32 poz., rys.

Twórcy

autor

Shieber S. M.

• School of Engineering and Applied Sciences, Harvard University, Cambridge MA, USA

Bibliografia

• [1] Alfred V. Aho and Jeffrey D. Ullman (1969), Syntax Directed Translations and the Pushdown Assembler, Journal of Computer and System Sciences, 3 (1): 37-56, doi:10.1016/S0022-0000(69)80006-1.
• [2] Hiyan Alshawi, Srinivas Bangalore, and Shona Douglas (2000), Learning Dependency Translation Models as Collections of Finite State Head Transducers, Computational Linguistics, 26 (1): 45-60, doi:10.1162/089120100561629.
• [3] André Arnold and Max Dauchet (1982), Morphismes et bimorphismes d’arbres [Morphisms and bimorphisms of trees], Theoretical Computer Science, 20 (1): 33-93, doi:10.1016/0304-3975(82)90098-6.
• [4] Matthias Büchse, Andreas Maletti, and Heiko Vogler (2012), Unidirectional Derivation Semantics for Synchronous Tree-Adjoining Grammars, in Developments in Language Theory, volume 7410 of Lecture Notes in Computer Science, pp. 368-379, Springer, doi:10.1007/978-3-642-31653-1_33.
• [5] Matthias Büchse, Heiko Vogler, and Mark-Jan Nederhof (2014), Tree Parsing for Tree-Adjoining Machine Translation, Journal of Logic and Computation, 24 (2): 351-373, doi:10.1093/logcom/exs050.
• [6] Hubert Comon, Max Dauchet, Remi Gilleron, Florent Jacquemard, Denis Lugiez, Sophie Tison, and Marc Tommasi (2008), Tree Automata Techniques and Applications, http://tata.gforge.inria.fr/, release of November 18, 2008.
• [7] Steve DeNeefe and Kevin Knight (2009), Synchronous Tree Adjoining Machine Translation, in Proceedings of the 2009 Conference on Empirical Methods in Natural Language Processing, pp. 727-736, Association for Computational Linguistics, Singapore, http://aclweb.org/anthology/D09-1076.
• [8] Akio Fujiyoshi and Takumi Kasai (2000), Spinal-Formed Context-Free Tree Grammars, Theory of Computing Systems, 33: 59-83, doi: 10.1007/s002249910004.
• [9] Michel Galley, Mark Hopkins, Kevin Knight, and Daniel Marcu (2004), What’s In a Translation Rule, in Proceedings of the Human Language Technology Conference of the North American Chapter of the Association for Computational Linguistics: HLT-NAACL 2004, pp. 273-280, Association for Computational Linguistics, Boston, Massachusetts, http://aclweb.org/anthology/N04-1035.
• [10] Jonathan Graehl and Kevin Knight (2004), Training Tree Transducers, in Proceedings of the Human Language Technology Conference of the North American Chapter of the Association for Computational Linguistics: HLT-NAACL 2004, pp. 105-112, Association for Computational Linguistics, Boston, Massachusetts, http://aclweb.org/anthology/N04-1014.
• [11] Chung-Hye Han and Nancy Hedberg (2008), Syntax and Semantics of It-Clefts: A Tree Adjoining Grammar Analysis, Journal of Semantics, 25: 345-380, doi: 10.1093/jos/ffn007.
• [12] Aravind Joshi and Yves Schabes (1997), Tree-Adjoining Grammars, in G. Rozenberg and A. Salomaa, editors, Handbook of Formal Languages, volume 3, pp. 69-124, Springer, Berlin.
• [13] Alexander Koller and Marco Kuhlmann (2011), A Generalized View on Parsing and Translation, in Proceedings of the 12th International Conference on Parsing Technologies, IWPT’11, pp. 2-13, Association for Computational Linguistics, Stroudsburg, PA, USA, ISBN 978-1-932432-04-6, http://dl.acm.org/citation.cfm?id=2206329.2206331.
• [14] Philip M. Lewis II and Richard E. Stearns (1968), Syntax-Directed Transduction, Journal of the Association for Computing Machinery, 15 (3): 465-488, ISSN 0004-5411, doi: 10.1145/321466.321477.
• [15] Andreas Maletti (2008), Compositions of Extended Top-down Tree Transducers, Information and Computation, 206 (9-10): 1187-1196, doi: 10.1016/j.ic.2008.03.019.
• [16] Andreas Maletti, Jonathan Graehl, Mark Hopkins, and Kevin Knight (2009), The power of extended top-down tree transducers, SIAM Journal on Computing, 39: 410-430, doi: 10.1137/070699160.
• [17] I. Dan Melamed (2003), Multitext Grammars and Synchronous Parsers, in Proceedings of the 2003 Human Language Technology Conference of the North American Chapter of the Association for Computational Linguistics, pp. 79-86, Association for Computational Linguistics, Edmonton, Canada, doi: 10.3115/1073445.1073466.
• [18] I. Dan Melamed (2004), Statistical Machine Translation by Parsing, in Proceedings of the 42nd Annual Conference of the Association for Computational Linguistics, pp. 653-660, Association for Computational Linguistics, Barcelona, Spain, doi: 10.3115/1218955.1219038.
• [19] Mark-Jan Nederhof and Heiko Vogler (2012), Synchronous Context-Free Tree Grammars, in Proceedings of the 11th International Workshop on Tree Adjoining Grammars and Related Formalisms (TAG + 11), pp. 55-63, Paris, France.
• [20] Rebecca Nesson and Stuart M. Shieber (2006), Simpler TAG Semantics Through Synchronization, in Proceedings of the 11th Conference on Formal Grammar, pp. 129-142, Center for the Study of Language and Information, Malaga, Spain, http://nrs.harvard.edu/urn-3:HUL.InstRepos:2252595.
• [21] Rebecca Nesson, Stuart M. Shieber, and Alexander Rush (2006), Induction of Probabilistic Synchronous Tree-Insertion Grammars for Machine Translation, in Proceedings of the 7th Conference of the Association for Machine Translation in the Americas (AMTA 2006), pp. 128-137, Association for Machine Translation in the Americas, Cambridge, Massachusetts, http://nrs.harvard.edu/urn-3:HUL.InstRepos:2261232.
• [22] William C. Rounds (1970), Mappings and Grammars on Trees, Mathematical Systems Theory, 4 (3): 257-287, doi: 10.1007/BF01695769.
• [23] Yves Schabes and Stuart M. Shieber (1994), An Alternative Conception of Tree-Adjoining Derivation, Computational Linguistics, 20 (1): 91-124, http://aclweb.org/anthology/J94-1004.
• [24] Yves Schabes and K. Vijay-Shanker (1990), Deterministic Left to Right Parsing of Tree Adjoining Languages, in Proceedings of the 28th Annual Meeting of the Association for Computational Linguistics, pp. 276-283, Association for Computational Linguistics, Pittsburgh, Pennsylvania, doi: 10.3115/981823.981858.
• [25] Stuart M. Shieber (1994), Restricting the Weak-Generative Capacity of Synchronous Tree-Adjoining Grammars, Computational Intelligence, 10 (4): 371-385, doi: 10.1111/j.1467-8640.1994.tb00003.x.
• [26] Stuart M. Shieber (2004), Synchronous Grammars as Tree Transducers, in Proceedings of the Seventh International Workshop on Tree Adjoining Grammar and Related Formalisms (TAG + 7), pp. 88-95, Vancouver, Canada, http://nrs.harvard.edu/urn-3:HUL.InstRepos:2019322.
• [27] Stuart M. Shieber (2006), Unifying Synchronous Tree-Adjoining Grammars and Tree Transducers via Bimorphisms, in Proceedings of the 11th Conference of the European Chapter of the Association for Computational Linguistics (EACL-06), pp. 377-384, European Chapter of the Association for Computational Linguistics, Trento, Italy, http://nrs.harvard.edu/urn-3:HUL.InstRepos:2252609.
• [28] Stuart M. Shieber and Yves Schabes (1990), Synchronous Tree-Adjoining Grammars, in Proceedings of the 13th International Conference on Computational Linguistics, volume 3, pp. 253-258, International Committee on Computational Linguistics, Helsinki, Finland, doi: 10.3115/991146.991191.
• [29] K. Vijay-Shanker (1987), A Study of Tree Adjoining Grammars, Ph.D. thesis, Department of Computer and Information Science, University of Pennsylvania, Philadelphia, Pennsylvania, http://repository.upenn.edu/dissertations/AAI8804974/.
• [30] Dekai Wu (1996), A Polynomial-Time Algorithm for Statistical Machine Translation, in Proceedings of the 34th Annual Meeting of the Association for Computational Linguistics, pp. 152-158, Association for Computational Linguistics, Santa Cruz, California, doi: 10.3115/981863.981884.
• [31] Dekai Wu (1997), Stochastic Inversion Transduction Grammars and Bilingual Parsing of Parallel Corpora, Computational Linguistics, 23 (3): 377-404, http://aclweb.org/anthology/J97-3002.
• [32] Elif Yamangil and Stuart M. Shieber (2010), Bayesian Synchronous Tree-Substitution Grammar Induction and Its Application to Sentence Compression, in Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics, pp. 937-947, Association for Computational Linguistics, Uppsala, Sweden, http://nrs.harvard.edu/urn-3:HUL.InstRepos:4733833.

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2020).