CSC 2517 -- Discrete Mathematical Models of Sentence Structure

Fall 2016

Index of this document

Contact information

Instructor: Gerald Penn
Office: PT 396B (St. George campus)
Tel: 978-7390
Back to the index

Meeting times

Lectures: T 3-5, BA B025
Back to the index

Presented Readings


Gerald Penn 13 September On Panini and the Generative Capacity of Contextualized Replacement Systems COLING-12
Gerald Penn 20 September Control Strategies for Parsing with Freer Word-Order Languages part of this appears in an ACL-06 workshop paper
Zachary MacDonald 27 September Regular Models of Phonological Rule Systems Computational Linguistics 20(3), 1994.
Muuo Wambua 4 October Grammar Flow Analysis Attribute Grammars, Applications and Systems, Springer Lecture Notes in Computer Science vol. 545,  2005.
Serena Jeblee 4 October Guided Earley Parsing IWPT-03
Eric Corlett 11 October Computational Complexity of Probabilistic Disambiguation Grammars 5, 2002.
Toryn Klassen 18 October Probabilistic Automata Information and Control 6, 1963
Yue Jiang 25 October Supertagging: A Non-Statistical Parsing-Based Approach IWPT-03
Toryn Klassen 1 November The Importance of Rule Restrictions in CCG ACL-10
Yue Jiang 8 November Vector Addition Systems Reachability Problem (A Simpler Solution) Turing 100: The Alan Turing Centerary, A. Voronkov ed., EPiC Series in Computing 10, 2012.
Gerald Penn 15 November Petri Nets
Serena Jeblee 22 November Vector Addition Tree Automata LICS 2004.
Eric Corlett 29 November The General Vector Addition System Reachability Problem by Presburger Inductive Variants LICS 2010.

Additional Readings for the Lectures

Title Author Publication Details
A Context-free Language which is not Acceptable by a Probabilistic Automaton M. Nasu and N. Honda Information and Control 18(3), pp. 233-236.
Theory of Automata (esp. pp. 83-4 for a simpler proof of the Reduction Theorem) A. Salomaa Oxford, 1969.

Back to the index

Tentative course outline

Back to the index

Calendar of important course-related events

Date Event
Tue, 13 September First lecture
Sun, 25 September Last day to add course
Mon, 31 October Last day to drop course
Tue, 29 November Last lecture
Tue, 20 December Term papers/projects due

Back to the index


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


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

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