Instructor: Dan Gildea
Fall 2012
Tu-Th 3:25-4:40
CSB 703
This course will discuss theories of language that extend beyond the power of context-free langauges, such as tree adjoining grammar, combinatory categorial grammar, linear context-free rewriting systems, as well as their synchronous counterparts, and tree transformation automata. We will focus on complexity results for recognition and probabilistic decision problems for these various frameworks.
Students will present three papers.
8/30: Organization
9/4: On the Complexity of ID/LP Parsing, G. Edward Barton, Jr. Computational Linguistics, 11(4):205-218, 1985. (Mary)
9/6: Efficient Parsing for Bilexical Context-Free Grammars and Head Automaton Grammars, Jason Eisner and Giorgio Satta. In Proceedings of the 37th Annual Conference of the Association for Computational Linguistics (ACL-99), pages 457-464, 1999. (Elif)
9/11: Finite-State Transducers in Language and Speech Processing, Mehryar Mohri. Computational Linguistics, 23(2):269-312, 1997.
9/13: Computational Complexity of Problems on Probabilistic Grammars and Transducers, F. Casacuberta and Colin De La Higuera. In Grammatical Inference: Algorithms and Applications, 5th International Colloquium, ICGI 2000, pages 15-24. Springer, 2000. (Iftekhar)
9/18: Evidence against the context-freeness of natural language, Stuart M. Shieber. Linguistics and Philosophy, 8:333-343, 1985. (Maryam)
9/20: Attribute-Value Logic and the Theory of Grammar, Mark Johnson. CSLI Lecture Notes. Chicago University Press, Chicago, 1988. chapter 3
9/25: Tree-Adjoining Grammars, A.K. Joshi and Y. Schabes. In G. Rozenberg and A. Salomaa, editors, Handbook of Formal Languages, volume 3, pages 69-124. Springer, Berlin, 1997. (Iftekhar)
9/27: Constituency and Coordination in a Combinatory Grammar, Mark J. Steedman. In Mark R. Baltin and Anthony S. Kroch, editors, Alternative Conceptions of Phrase Structure, pages 201-231. University of Chicago, Chicago, 1989. (Mary)
10/2: Tree-Adjoining Grammars Are Not Closed Under Strong Lexicalization, Marco Kuhlmann and Giorgio Satta. Computational Linguistics, 38:617-629, 2012. (Scott)
10/4: Characterizing structural descriptions produced by various grammatical formalisms, K. Vijay-Shankar, D. L. Weir, and A. K. Joshi. In Proceedings of the 25th Annual Conference of the Association for Computational Linguistics (ACL-87), pages 104-111, Stanford, CA, 1987.
10/9: Fall break
10/11: Synchronous Tree-Adjoining Grammars, Stuart Shieber and Yves Schabes. In Proceedings of the 13th International Conference on Computational Linguistics (COLING-90), volume III, pages 253-258, Helsinki, 1990. (Maryam)
10/16: Restrictions on Tree Adjoining Languages, Giorgio Satta and William Schuler. In Proceedings of the 36th Conference of the Association for Computational Linguistics (ACL98), pages 1176-1182, Montreal, Canada, 1998.
10/18: Parsing some constrained grammar formalisms, K. Vijay-Shanker and David Weir. Computational Linguistics, 19:591-636, 1993. (Licheng)
10/23:
The Problem of Computing
the Most Probable Tree in Data-Oriented Parsing and Stochastic Tree
Grammars,
Rens Bod.
In Proceedings of the European Chapter of the ACL, 1995.
Computational Complexity of Probabilistic Disambiguation by means of Tree Grammars,
Khalil Sima'an.
In Proceedings of the International Conference on Computational
Linguistics (COLING '96), pages 1175-1180, Copenhagen, Denmark,
1996.
(Adam)
10/25: The DOP estimation method is biased and inconsistent, Mark Johnson. Computational Linguistics, 28:71-76, 2002. (Mary)
10/30: The Theory of Parsing, Translation, and Compiling, Albert V. Aho and Jeffery D. Ullman. volume 1. Prentice-Hall, Englewood Cliffs, NJ, 1972. pages 238-251
11/1: On Multiple Context-Free Grammars, H. Seki, T. Matsumura, M. Fujii, and T. Kasami. Theoretical Computer Science, 88:191-229, 1991. (Elif)
11/6: Binarization of Synchronous Context-Free Grammars, Liang Huang, Hao Zhang, Daniel Gildea, and Kevin Knight. Computational Linguistics, 35(4):559-595, 2009. (Iftekhar)
11/8: Independent Parallelism in Finite Copying Parallel Rewriting Systems, Owen Rambow and Giorgio Satta. Theor. Comput. Sci., 223(1-2):87-120, 1999. (Scott)
11/13: Some Computational Complexity Results for Synchronous Context-Free Grammars, Giorgio Satta and Enoch Peserico. In Proceedings of Human Language Technology Conference and Conference on Empirical Methods in Natural Language Processing (HLT/EMNLP), pages 803-810, Vancouver, Canada, 2005. (Licheng)
11/15: An Overview of Probabilistic Tree Transducers for Natural Language Processing, Kevin Knight and Jonathan Graehl. In Conference on Intelligent Text Processing and Computational Linguistics (CICLing), pages 1-24. Lecture Notes in Computer Science (Springer-Verlag), 2005. (Licheng)
11/20: A Better N-Best List: Practical Determinization of Weighted Finite Tree Automata, Jonathan May and Kevin Knight. In Proceedings of the 2006 Meeting of the North American chapter of the Association for Computational Linguistics (NAACL-06), 2006. Efficient Inference through Cascades of Weighted Tree Transducers, Jonathan May, Kevin Knight, and Heiko Vogler. In Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics (ACL-10), 2010. (Adam)
11/27: Why Synchronous Tree Substitution Grammars?, Andreas Maletti. In Proceedings of the 2010 Meeting of the North American chapter of the Association for Computational Linguistics (NAACL-10), pages 876-884, Los Angeles, California, 2010. (Scott)
11/29: A* Parsing: Fast Exact Viterbi Parse Selection, Dan Klein and Christopher D. Manning. In Proceedings of the 2003 Meeting of the North American chapter of the Association for Computational Linguistics (NAACL-03), 2003. Weighted Deductive Parsing and Knuth's Algorithm, M.-J. Nederhof. Computational Linguistics, 29(1):135-144, 2003. (Elif)
12/4: K-Best A* Parsing, Adam Pauls and Dan Klein. In Proceedings of the Joint Conference of the 47th Annual Meeting of the ACL and the 4th International Joint Conference on Natural Language Processing of the AFNLP, pages 958-966. Association for Computational Linguistics, 2009. Better k-best Parsing, Liang Huang and David Chiang. In International Workshop on Parsing Technologies (IWPT05), Vancouver, BC, 2005. (Maryam)
12/6: Grammar Factorization by Tree Decomposition, Daniel Gildea. Computational Linguistics, 37(1):231-248, 2011.
12/11: Efficient Incremental Decoding for Tree-to-String Translation, Liang Huang and Haitao Mi. In Proceedings of the 2010 Conference on Empirical Methods in Natural Language Processing, pages 273-283, Cambridge, MA, October 2010. (Adam)