CS 290/577: LANGUAGE, PARSING, AND COMPLEXITY

Instructor: Dan Gildea
Fall 2006
Tu-Th 11:05-12:20
CSB 632

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, write summaries for each paper, and do a term project.

Schedule

9/5: Organization

Context-Free Formalisms

9/7: On the Complexity of ID/LP Parsing, G. Edward Barton, Jr. Computational Linguistics, 11(4):205-218, 1985.

9/12: 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), 1999.

9/14: Finite-State Transducers in Language and Speech Processing, Mehryar Mohri. Computational Linguistics, 23(2):269-312, 1997.

9/19: 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. (Matt)

9/21: Evidence against the context-freeness of natural language, Stuart M. Shieber. Linguistics and Philosophy, 8:333-343, 1985.

9/26: Attribute-Value Logic and the Theory of Grammar, Mark Johnson. CSLI Lecture Notes. Chicago University Press, Chicago, 1988. chapter 3 (Benjamin)

Tree Adjoining Grammar

9/28: 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. (Sam)

10/3: 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/5: Complexity of Scrambling: A New Twist to the Competence - Performance Distinction, Aravind K. Joshi, Tilman Becker, and Owen Rambow. In 3e Colloque International sur les grammaires d'Arbres Adjoints, 1994. (Hao)

10/10: 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), 1987.

10/12: A geometric hierarchy beyond context-free languages, David Weir. Theoretical Computer Science, 104:235-261, 1992. (Saurabh)

10/17: 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. (Arrvindh)

10/19: Parsing some constrained grammar formalisms, K. Vijay-Shanker and David Weir. Computational Linguistics, 19:591-636, 1993. (Bin)

Tree Substitution Grammars

10/24: 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. (Pin)
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, August 1996. (Arrvindh)

10/26: The DOP estimation method is biased and inconsistent, Mark Johnson. Computational Linguistics, 28:71-76, 2002. (Xiao)

Synchronous Grammars

10/31: 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 (Saurabh)

11/2: 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, 1990. (Xiao)

11/7: Preserving semantic dependencies in synchronous tree adjoining grammar, William Schuler. In Proceedings of the 37th Annual Conference of the Association for Computational Linguistics (ACL-99), 1999. A meta-level grammar: redefining synchronous TAG for translation and paraphrase, Mark Dras. In Proceedings of the 37th Annual Conference of the Association for Computational Linguistics (ACL-99), 1999. (Bin)

11/9: Independent Parallelism in Finite Copying Parallel Rewriting Systems., Owen Rambow and Giorgio Satta. Theor. Comput. Sci., 223(1-2):87-120, 1999. (Pin)

11/14: 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, October 2005. (Matt)

Tree Transducers

11/16: Tree Automata, F. Gécseg and M. Steinby. Akadémiai Kiadó, Budapest, 1984. pages 138-173

11/21: Synchronous grammars as tree transducers, Stuart M. Shieber. In Proceedings of the Seventh International Workshop on Tree Adjoining Grammar and Related Formalisms (TAG+ 7), 2004. (Matt)

11/28: Unifying synchronous tree-adjoining grammars and tree transducers via bimorphisms, Stuart M. Shieber. In Proceedings of the 11th Conference of the European Chapter of the Association for Computational Linguistics (EACL-06), 2006. (Arrvindh)

Search

11/30: 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. (Sam)

12/5: Better k-best Parsing, Liang Huang and David Chiang. In International Workshop on Parsing Technologies (IWPT05), Vancouver, BC, 2005. (Xiao)

12/7: Probability Propagation, G. Shafer and P. Shenoy. Annals of Mathematics and Artificial Intelligence, 2:327-353, 1990. (Saurabh)

12/12: Complexity of Finding Embeddings in a $k$-Tree, Stefen Arnborg, Derek G. Corneil, and Andrzej Proskurowski. SIAM Journal of Algebraic and Discrete Methods, 8:277-284, April 1987.