More Web Proxy on the site http://driver.im/

Article

Free access

Generalized multitext grammars

Authors:

I. Dan Melamed,

Benjamin WellingtonAuthors Info & Claims

ACL '04: Proceedings of the 42nd Annual Meeting on Association for Computational Linguistics

Pages 661 - es

https://doi.org/10.3115/1218955.1219039

Published: 21 July 2004 Publication History

Abstract

Generalized Multitext Grammar (GMTG) is a synchronous grammar formalism that is weakly equivalent to Linear Context-Free Rewriting Systems (LCFRS), but retains much of the notational and intuitive simplicity of Context-Free Grammar (CFG). GMTG allows both synchronous and independent rewriting. Such flexibility facilitates more perspicuous modeling of parallel text than what is possible with other synchronous formalisms. This paper investigates the generative capacity of GMTG, proves that each component grammar of a GMTG retains its generative power, and proposes a generalization of Chomsky Normal Form, which is necessary for synchronous CKY-style parsing.

References

[1]

A. Aho and J. Ullman. 1969. Syntax directed translations and the pushdown assembler. Journal of Computer and System Sciences, 3:37--56, February.

Digital Library

[2]

T. Becker, A. Joshi, and O. Rambow. 1991. Long-distance scrambling and tree adjoining grammars. In Proceedings of the 5th Meeting of the European Chapter of the Association for Computational Linguistics (EACL), Berlin, Germany.

Digital Library

[3]

E. Bertsch and M. J. Nederhof. 2001. On the complexity of some extensions of RCG parsing. In Proceedings of the 7th International Workshop on Parsing Technologies (IWPT), pages 66--77, Beijing, China.

[4]

M. Dras and T. Bleam. 2000. How problematic are clitics for S-TAG translation? In Proceedings of the 5th International Workshop on Tree Adjoining Grammars and Related Formalisms (TAG+5), Paris, France.

[5]

J. Hopcroft, R. Motwani, and J. Ullman. 2001. Introduction to Automota Theory, Languages and Computation. Addison-Wesley, USA.

Digital Library

[6]

I. Dan Melamed, G. Satta, and B. Wellington. 2004. Generalized multitext grammars. Technical Report 04-003, NYU Proteus Project. http://nlp.cs.nyu.edu/pubs/.

[7]

I. Dan Melamed. 2003. Multitext grammars and synchronous parsers. In Proceedings of the Human Language Technology Conference and the North American Association for Computational Linguistics (HLT-NAACL), pages 158--165, Edmonton, Canada.

Digital Library

[8]

I. Dan Melamed. 2004. Statistical machine translation by parsing. In Proceedings of the 42nd Annual Meeting of the Association for Computational Linguistics (ACL), Barcelona, Spain.

Digital Library

[9]

O. Rambow and G. Satta. 1996. Synchronous models of language. In Proceedings of the 34th Annual Meeting of the Association for Computational Linguistics (ACL), Santa Cruz, USA.

Digital Library

[10]

O. Rambow and G. Satta. 1999. Independent parallelism in finite copying parallel rewriting systems. Theoretical Computer Science, 223:87--120, July.

Digital Library

[11]

O. Rambow. 1995. Formal and Computational Aspects of Natural Language Syntax. Ph.D. thesis, University of Pennsylvania, Philadelphia, PA.

Digital Library

[12]

S. Shieber. 1994. Restricting the weak-generative capactiy of synchronous tree-adjoining grammars. Computational Intelligence, 10(4):371--386.

[13]

D. J. Weir. 1988. Characterizing Mildly Context-Sensitive Grammar Formalisms. Ph.D. thesis, Department of Computer and Information Science, University of Pennsylvania.

Digital Library

[14]

D. Wu. 1997. Stochastic inversion transduction grammars and bilingual parsing of parallel corpora. Computational Linguistics, 23(3):377--404, September.

Digital Library

[15]

D. H. Younger. 1967. Recognition and parsing of context-free languages in time n3. Information and Control, 10(2):189--208, February.

Cited By

Nederhof MSatta GBunt HNivre J(2011)Prefix probabilities for linear context-free rewriting systemsProceedings of the 12th International Conference on Parsing Technologies10.5555/2206329.2206348(151-162)Online publication date: 5-Oct-2011
https://dl.acm.org/doi/10.5555/2206329.2206348
Xue HHwa RJoshi AHuang CJurafsky D(2010)Syntax-driven machine translation as a model of ESL revisionProceedings of the 23rd International Conference on Computational Linguistics: Posters10.5555/1944566.1944723(1373-1381)Online publication date: 23-Aug-2010
https://dl.acm.org/doi/10.5555/1944566.1944723
Chiang DHajič J(2010)Learning to translate with source and target syntaxProceedings of the 48th Annual Meeting of the Association for Computational Linguistics10.5555/1858681.1858827(1443-1452)Online publication date: 11-Jul-2010
https://dl.acm.org/doi/10.5555/1858681.1858827
Show More Cited By

Recommendations

Tree-structured models of multitext: theory, design and experiments
Parsing expression grammars: a recognition-based syntactic foundation
POPL '04: Proceedings of the 31st ACM SIGPLAN-SIGACT symposium on Principles of programming languages

For decades we have been using Chomsky's generative system of grammars, particularly context-free grammars (CFGs) and regular expressions (REs), to express the syntax of programming languages and protocols. The power of generative grammars to express ...
On Generalized Ajdukiewicz and Lambek Calculi and Grammars

We show that derivation trees in the generalized Lambek calculus can be transformed to a normal form. This fact is employed in the proof of the inclusion of the class of phrase languages generated by categorial grammars based on the generalized Lambek ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image DL Hosted proceedings

ACL '04: Proceedings of the 42nd Annual Meeting on Association for Computational Linguistics

July 2004

729 pages

General Chair:
Donia Scott
ITRI, University of Brighton

Publisher

Association for Computational Linguistics

United States

Publication History

Published: 21 July 2004

Qualifiers

Article

Acceptance Rates

Overall Acceptance Rate 85 of 443 submissions, 19%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

12
Total Citations
View Citations
302
Total Downloads

Downloads (Last 12 months)34
Downloads (Last 6 weeks)6

Reflects downloads up to 18 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Nederhof MSatta GBunt HNivre J(2011)Prefix probabilities for linear context-free rewriting systemsProceedings of the 12th International Conference on Parsing Technologies10.5555/2206329.2206348(151-162)Online publication date: 5-Oct-2011
https://dl.acm.org/doi/10.5555/2206329.2206348
Xue HHwa RJoshi AHuang CJurafsky D(2010)Syntax-driven machine translation as a model of ESL revisionProceedings of the 23rd International Conference on Computational Linguistics: Posters10.5555/1944566.1944723(1373-1381)Online publication date: 23-Aug-2010
https://dl.acm.org/doi/10.5555/1944566.1944723
Chiang DHajič J(2010)Learning to translate with source and target syntaxProceedings of the 48th Annual Meeting of the Association for Computational Linguistics10.5555/1858681.1858827(1443-1452)Online publication date: 11-Jul-2010
https://dl.acm.org/doi/10.5555/1858681.1858827
Gildea DKaplan R(2010)Optimal parsing strategies for linear context-free rewriting systemsHuman Language Technologies: The 2010 Annual Conference of the North American Chapter of the Association for Computational Linguistics10.5555/1857999.1858117(769-776)Online publication date: 2-Jun-2010
https://dl.acm.org/doi/10.5555/1857999.1858117
Gómez-Rodríguez CKuhlmann MSatta GWeir DOstendorf MCollins MNarayanan SOard D(2009)Optimal reduction of rule length in linear context-free rewriting systemsProceedings of Human Language Technologies: The 2009 Annual Conference of the North American Chapter of the Association for Computational Linguistics10.5555/1620754.1620833(539-547)Online publication date: 31-May-2009
https://dl.acm.org/doi/10.5555/1620754.1620833
Lopez A(2008)Statistical machine translationACM Computing Surveys10.1145/1380584.138058640:3(1-49)Online publication date: 13-Aug-2008
https://dl.acm.org/doi/10.1145/1380584.1380586
Smith DEisner JKoehn PMonz C(2006)Quasi-synchronous grammarsProceedings of the Workshop on Statistical Machine Translation10.5555/1654650.1654655(23-30)Online publication date: 8-Jun-2006
https://dl.acm.org/doi/10.5555/1654650.1654655
Wellington BWaxmonsky SMelamed I(2006)Empirical lower bounds on the complexity of translational equivalenceProceedings of the 21st International Conference on Computational Linguistics and the 44th annual meeting of the Association for Computational Linguistics10.3115/1220175.1220298(977-984)Online publication date: 17-Jul-2006
https://dl.acm.org/doi/10.3115/1220175.1220298
Satta GPeserico EMooney R(2005)Some computational complexity results for synchronous context-free grammarsProceedings of the conference on Human Language Technology and Empirical Methods in Natural Language Processing10.3115/1220575.1220676(803-810)Online publication date: 6-Oct-2005
https://dl.acm.org/doi/10.3115/1220575.1220676
Hwa RResnik PWeinberg ACabezas CKolak O(2005)Bootstrapping parsers via syntactic projection across parallel textsNatural Language Engineering10.1017/S135132490500384011:3(311-325)Online publication date: 1-Sep-2005
https://dl.acm.org/doi/10.1017/S1351324905003840
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents