CSC 2517 -- Discrete Mathematical Models of Sentence Structure

Fall 2005

Index of this document

Contact information
Meeting times
Readings
Tentative course outline
Calendar of important course-related events
Evaluation
Announcements

Contact information

Instructor: Gerald Penn

Office: PT 396B (St. George campus)

Tel: 978-7390

Email: gpenn@cs.utoronto.ca

Back to the index

Meeting times

Lectures: T 4-6, BA 3000

Back to the index

Presented Readings


Who	When	What	Where
Mike Demko and Ewan Dunbar	19 October	Peters, P. S. and R. W. Ritchie (1973) On the Generative Power of Transformational Grammars.	Information Sciences 6, pp. 49-83.
Timothy Fowler	25 October	Carpenter, B. (1991) The Generative Power of Categorial Grammars and Head-driven Phrase Structure Grammars with Lexical Rules.	Computational Linguistics 17(3), pp. 301-313.
Kenji Oda	1 November	Maxwell, J. T. and R. M. Kaplan (1993) The Interface between Phrasal and Functional Constraints.	Computational Linguistics 19(4), pp. 571-590.
Milind Joshi	22 November	Satta, G. (1993) Tree-Adjoining Grammar Parsing and Boolean Matrix Multiplication.	Computational Linguistics 20(2), pp. 173-191.
Mike Demko	29 November	Vijay-Shankar, K. and Joshi, A. K. (1985) Some Computational Properties of Tree Adjoining Grammars.	ACL 1985, pp. 82-93.

Additional Readings for the Lectures


Title	Author	Publication Details
The Syntactic Process	M. Steedman	MIT Press, 2000.
Tree Adjoining Grammars	A. Abeille and O. Rambow	CSLI Publications, 2000.
The Algebraic Structure of Attributed Type Signatures	G. Penn	Carnegie Mellon Univ. dissertation, 2000
The Logic of Typed Feature Structures	B. Carpenter	Cambridge University Press, 1992.
Introduction to Lattices and Order, 2nd ed.	B.A. Davey and H.A. Priestley	Cambridge University Press, 2002.

Back to the index

Tentative course outline

Typed feature logic
Mildly context-sensitive languages
Parallel context-free grammars
Tree-adjoining grammars
Combinatory categorial grammar
Pre-group grammars
Tree transducers and tree-walking transducers

Back to the index

Calendar of important course-related events


Date	Event
Tue, 13 September	First lecture
Fri, 30 October	Last day to add course
Fri, 4 November	Last day to drop course
Tue, 6 December	Last lecture
Tue, 20 December	Term papers/projects due

Back to the index

Evaluation

Your final mark will be determined by a term paper/project, and a presentation of a paper in class. The relative weights of these components towards the final mark are shown in the table below:


Class presentation	20%
Term paper/project	80%

Back to the index

Announcements

In this space, you will find announcements related to the course. Please check this space at least weekly.

1 December: MATERIAL COVERED DURING WEEK 13: categorial grammars continued.
30 November: THE MEETING ON 29 NOVEMBER has been rescheduled to 1 December from 2-4pm in the CL lab.
30 November: MATERIAL COVERED DURING WEEK 12: categorial grammars.
30 November: MATERIAL COVERED DURING WEEK 11: head grammars.
30 November: MATERIAL COVERED DURING WEEK 10: Weir's theorem.
17 November: THE MEETING ON 22 NOVEMBER will take place in the CL lab(2nd floor Pratt) from 12-2pm. THE MEETING ON 6 DECEMBER has been rescheduled to 30 November from 3-5pm.
15 November: MATERIAL COVERED DURING WEEK 9: linear index grammars, tree-adjoining languages.
15 November: MATERIAL COVERED DURING WEEK 8: index grammars, MCFGs, TAGs, desiderata for the mildly context-sensitve languages.
3 November: MATERIAL COVERED DURING WEEKS 6-7: extended phrase structure grammars.
11 October: THERE WILL BE NO MEETING ON 18 OCTOBER: instead, we will meet on Wednesday, 19 October from 2-4pm in the CL lab (2nd floor of Pratt).
7 October: REMINDER: the first hour of our class on 11 October will be Stuart Russell's talk in PT 266.
7 October: MATERIAL COVERED DURING WEEKS 1-5: the logic of typed feature structures.
6 September: PREREQUISITES: CSC 2501 or CSC 2511 or permission of the instructor.

Back to the index

Gerald Penn, 1 December, 2005
This web-page was adapted from the web-page for another course, created by Vassos Hadzilacos.