Bimorphisms and synchronous grammars

What it is about

Language relations, such as translation or the relation between a sentence and its meaning, are often more natural to specify than single languages. The paper combines two approaches to such relations: tree transducers, which map input trees to output trees, and synchronous grammars, which derive pairs of trees. Both are expressed through the bimorphism, which uses a regular tree language and two homomorphisms that map it to the two output trees. The paper characterises synchronous tree substitution grammars and synchronous tree-adjoining grammars in these terms. To do this it gives a uniform metanotation for tree automata and transducers written as equations, a formalisation of tree-adjoining and tree-substitution grammars over ranked alphabets, and an extension of tree-adjoining grammar that allows multiple adjunction. The main result is that synchronous tree-substitution grammars are equivalent to bimorphisms whose component homomorphisms are linear and complete. The paper is theoretical and has no experiments.

Ideas

• I1. The meta-world as a bimorphism. Write the reader as one homomorphism and the encoder as the other, with the regular tree language of meta trees between them. Then the check that the composition reproduces the exact target on verse pairs is a test of the whole translator, not of a single stage.
• I2. Linear and complete checks on the reader. As in the 2004 paper, a rule that copies or drops a source token is a bug unless declared. Run the check on tools/translate rule tables and count violations per author.
• I3. Multiple adjunction for modifiers. A modifier phrase such as quite often may need to attach to more than one node in the meta-world. Test on verses whether allowing multiple adjunction changes the residual, before adding it to the reader.

For Mova

The code is tools/translate, in the meta-world (the shared tree between reader and encoder). The paper is a formal result, so no number is claimed for Mova. The first step is the linear and complete check of I2, which is a count over rule tables, and the result should be the same on two runs.

Topics: Machine translation

Cite

The paper itself, not this card. BibTeX from the library's record of the work. DOI 10.15398/jlm.v2i1.84

@article{shieber2014bimorphisms,
  title = {{Bimorphisms and synchronous grammars}},
  author = {Shieber, Stuart M.},
  journal = {Journal of Language Modelling},
  year = {2014},
  doi = {10.15398/jlm.v2i1.84},
  url = {https://doi.org/10.15398/jlm.v2i1.84}
}

References

32 references, 4 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

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 . ↗ our card
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 . ↗ our card
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. find
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. find
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 . ↗ our card
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 . ↗ our card
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 . This work is licensed under the Creative Commons Attribution 3.0 Unported License. http://creativecommons.org/licenses/by/3.0/ ↗

This page in Markdown → https://md.mova.elamur.ai/free/en/docs/papers/shieber-2014-bimorphisms-synchronous-grammars/