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.
9/5: Organization
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)
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)
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)
10/26:
The DOP estimation
method is biased and inconsistent,
Mark Johnson.
Computational Linguistics, 28:71-76, 2002.
(Xiao)
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)
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)
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.
Tree Adjoining Grammar
Tree Substitution Grammars
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)
Synchronous Grammars
Tree Transducers
Search