Linguistics 726 – Mathematical Linguistics (really: mathematics for and in linguistics)


syllabus | course description | lectures | homework | book errata | links | readings | LING 726 2001 Website


Time and Place: T Th 1:00 – 2:15, Herter 114.


Instructors, Office Hours, and Contact Information:

Barbara H. Partee: by appointment

Vladimir Borschev: by appointment

Office: So. College 222;  545-0885

Home phone: 549-4501



Schedule for 2004, version of November 7


Part 1. Basic notions of set theory.

Lectures 1-3, with Homeworks 1-3. September 9, 14, 16. Sets, subsets, operations on sets. Ordered pairs and Cartesians products. Relations. Functions and their compositions. Properties of relations and classes of relations.  Quotient sets, kernel of a relation. Trees (first pass).


Part 2. Intro to algebra.  

Lecture 4, Part 1. Algebra, Section1. Signature, algebra in a signature. Isomorphisms, homomorphisms, congurences and quotient algebras. September 21, 23, with Homework 4. Lecture 4, Part 2.  Algebra, Section 2. Lattices, Boolean algebra.  September 28, Homework 5.


Sept 30 – OT1: Guest lecture by Rajesh Bhatt (Handout). First intro to formalizing OT (BHP and VB away).  Everyone welcome.  Optional background reading: Andries Coetzee’s dissertation, chapter 2: A Rank-Ordering Model of EVAL.
Rajesh’s description: I will present an introduction to some of the issues that arise in the formalization of Optimality Theory. The formalizations discussed will include the ones proposed by Samek-Lodovici and Prince (1999), Moreton (1999), and (in greatest detail) Coetzee (2004). These authors make different assumptions about the information an OT grammar makes available and the impact of their varying assumptions on their formalizations will be examined. The discussion will go into some of the details of Coetzee's formalization of Optimality Theory, setting the groundwork for discussion in future lectures of debates concerning the complexity and learnability properties of Optimality Theory.


October 5, 7, 12:

Part 3. Logic and formal systems.  (about 4 classes including Logic-Algebra bridge)

Lecture 5: Logic, Section 1. Statement logic, including Syntax and Semantics as algebras with a homomorphism between them. (Oct 5), Homework 6.

Lecture 6. Logic, Section 2: Predicate logic. Axioms and Theories. Second pass at formalizing trees. Appendix with tree definitions. Homework 7. Oct 7,12.


October 12-14: 

Lecture 7: Model theory 1. Consistency, independence, completeness, categoricity of axiom systems. Examples.  Parts of PtMW Chapter 8: 8.1, 8.4, 8.5. Homework 8. (=old Homework 10)


October 14:

Lecture 8: Axioms and theories, more examples: Axiomatic description of properties of relations. Homework 9: Algebra review: Homomorphisms, congruences and quotient algebras.


October 19:

Lecture 9: Proof by Induction. Homework 10 on induction. (= old Homework 11) Appendix “How to use induction in a proof”, taken from .


October 21:

Lecture 10. Logic and algebra. Statement logic as a word algebra on the set of atomic statements. Lindenbaum algebra: logic as Boolean algebra.  (old Lecture 9, Hw 11 = old hw 9)


October 26-28: (BHP away) 

Lectures 11-12. Automata theory and formal grammars I. Finite state automata and corresponding grammars. Finite state automata as a Boolean algebra.  Finite state automata and generation/recognition. Finite state grammars. Finite-state languages. Regular expressions. Ways of proving that a given language is not a finite-state language. Homework 12 (mislabeled as HW 11) (= old hw 15)


Nov 2: 

Lecture 13. Finite state languages and human languages.   Are natural languages finite-state languages? Weak and strong generative capacity, competence/performance issues. Hauser et al’s arguments that human language exceeds finite-state machine capacity, while animal language does not. (See links in Readings section)   [Note: Mark Hauser’s Freeman lecture is Thursday, November 4.] No homework.


Nov 4:

Lecture 14.  Context-free grammars and Push-Down Storage Automata.

      Proofs of non-context-freeness (The Pumping Lemma). Are natural languages context-free? No homework. (No more homework at all.)


Nov 9 GUEST LECTURE, ANDREW McCALLUM.  Mathematical linguistics in the real world. Abstract: An overview of the application of "mathematical linguistics" to information extraction.  The use of hidden Markov models, Bayesian classifiers, Maximum entropy models, and other models that can perform enough syntactic/semantic analysis to reliably fill a structured database from natural language text.  Examples and accuracy statistics for many domains, including extracting job opening from corporate Web pages, people relationships from newswire, information about weather events from ancient Chinese manuscripts, bibliographic information from research papers.  It will be educational, intuitive, fun.  Even if the students don't understand the models I describe, they should still get a lot from the lecture.


Nov 16-22: More on OT.

Nov 16.

Lecture 15. OT. Andries’ dissertation, the math chapter, and other OT issues. Besides Andries’s chapter 2, see the paper by Michael Hammond, The logic of Optimality Theory, ROA 390-0400.  (Since Rajesh already talked about Andries’s math chapter on Sept. 30, the agenda for today will be modified to set the stage for his second guest lecture Nov 16, perhaps by introduction of finite state transducers.


Nov 18 GUEST LECTURE, RAJESH BHATT  On the relationship between OT and finite state morphology.  The Eisner/Frank & Satta/Karttunen debate on how under certain restrictions OT has the same power as finite state morphology, and by extension SPE style phonology with replacement rules.  Readings to be determined, undoubtedly including Lauri Karttunen’s paper, The Proper Treatment of Optimality in Computational Phonology. To appear in the Proceedings of FSMNLP'98. The International Workshop on Finite-State Methods in Natural Language Processing. Bilkent University. Ankara, Turkey. June 29-July 1, 1998. (HTML, Postscript). (ROA-258-0498) (PDF) 


Nov 22

Lecture 16. Continuing discussion of OT and related issues. Maybe here include “infinities” as well as “how many grammars?”


Nov 23-Dec 2: Model theoretic syntax.

Nov 23. 

Lecture 17. Model-theoretic syntax, Russian version.  Volodja will present what is now known as model theoretic syntax as he and his collaborators developed it in Moscow several decades ago, adding his current perspective.


Nov 30, Dec 2. 2 GUEST LECTURES, CHRIS POTTS. Model theoretic syntax (and phonology): Chris’s description: “model theory inside linguistics but outside semantics".  I will show how to use a simple modal logic to talk about relational structures of the sort found in syntax and phonology.  I will point to some (welcome and unwelcome) limitations.


Dec 7 – 9. Formal language theory.

Lectures 18-19. The Chomsky Hierarchy. Grammars and Processing models.  Turing machines (very briefly), recursive enumerability. The Halting Problem and undecidability. Context-free and context-sensitive grammars. McCawley’s result about tree-checking grammars. Parsing algorithms for CFGs. Are natural languages CF?

    -- We won’t have time to do all of this with any thoroughness; the presentations will be designed mainly to whet your appetites for more of this stuff, to pursue when and where you can.



*Note about dates: Thursday Nov 11 is a holiday. Monday Nov 22 is a “Thursday”.  Thursday Nov 25 is Thanksgiving. Last class is Thursday Dec 9.  Last day for turning in homework (late homework or special projects) is Monday December 13, but since no homework will be assigned in December, we really hope to have all homeworks in hand by December 3.