Linguistics 726: Mathematical Linguistics

Barbara Partee and Vladimir Borschev
Fall 2006, University of Massachusetts, Amherst

Ling726 2006 home | description | homework | book errata | links | LING 726 2004 Website


SCHEDULE for 2006

as of September 26, 2006 -- subject to change

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


Part 1. Basic notions of set theory.

Lectures 1-3, with Homeworks 1-3. September 7, 12, 14. 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).

Homework 2 Solutions (relations and functions)  | Homework 3 Solutions (Properties of relations)


Part 2. Intro to algebra.  

Lecture 4, Part 1. Algebra, Section1. Signature, algebra in a signature. Isomorphisms, homomorphisms, congruences and quotient algebras. Sep 19, 21 with Homework 4 (due Sep 26). Lecture 4, Part 2.  Algebra, Section 2. Lattices, Boolean algebra.  Sep 26, Homework 5 (due Sep 28)

Homework 4 Solutions (Algebra 1) | Homework 5 Solutions (Lattices and Boolean Algebra)


Sept 28, Oct 3:

Part 3: Infinities.

Lecture 5: Infinities, introduction. Finite vs. infinite. Denumerable, non-denumerable infinity. Diagonal arguments. Homework 6.

Lecture 6:  What is the cardinality of a natural language?  Finite (occasionally suggested, challenging aspects of competence/performance distinction), denumerably infinite (the standard Chomskyan view), non-denumerably infinite (Langendoen and Postal), unspecified as between denumerably and non-denumerably infinite (Pullum)? 

      Goal is not to settle the question but to become literate about the debate and be able to follow the arguments and to identify the assumptions on which they rest.

Homework 6 Solutions (Infinities)


October 5, 10, 12:

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

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

Lecture 8. Oct 10,12. Logic, Section 2: Predicate logic. Axioms and Theories. Second pass at formalizing trees. Supplements with tree definitions. Homework 8 due Oct 17.
Homework 8 Solutions (Predicate Logic)

 October 17-19: 

Lecture 9: Model theory 1. Consistency, independence, completeness, categoricity of axiom systems. Model theory and Proof theory. Examples.  Parts of PtMW Chapter 5, Chapter 8: 8.1- 8.5. Homework 9 due October 24.

Homework 9 Solutions (Model theory)

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

Homework 10 Solutions (Algebra review)


October 24:

Lecture 11: Proof by Induction. Homework 11 on induction.  Also some initial discussion of recursion, and how recursion and induction are related. Appendix “How to use induction in a proof”, taken from .

Homework 11 Solutions (Proof by induction)



October 26:

Lecture 12. Logic and algebra. Statement logic as a word algebra on the set of atomic statements. Lindenbaum algebra: logic as Boolean algebra. Homework 12.

Homework 12 Solutions (Lindenbaum Algebra)


October 31-Nov 2:

Lectures 13-14. 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 13.

Homework 13 Solutions (Finite State Automata)


Nov 7: 

Lecture 15. 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. Links to readings available online are in the handout and also here:

 (And/or see links in WHISC of September 23 2004:   No homework.


Nov 9:

Lecture 16.  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 14, 16, 21: Guest lectures by Chris Potts  (Partee and Borschev away)


Nov 14: Lecture 17. Chris Potts, "Computational methods in theoretical linguistics", with the goal being to show some of the ways that computers can help linguists with their *theoretical* (not experimental) work. (I say "not experimental" because it seems a given that they should be using computers for that stuff.)


Nov 16, 21: Lectures 18-19. Chris Potts, Game Theory and applications to linguistics. The first lecture will provide background and technical details on game theory. The second will be about how the concepts might be applied in linguistics. One key reading: the introductory chapter to: Benz, Anton, Gerhard Jaeger, and Robert van Rooij, eds. 2005. Game Theory and Pragmatics. Basingstoke, Hampshire: Palgrave McMillan. . As Chris says, "Benz, Jaeger, and van Rooij have made it easy to assign reading on game theory for linguistics. Their introduction to their recent edited volume is first-rate." The entire book is HERE in pdf format.



Tues, Nov 28: Lecture 20. Semantic automata. Natural Language Quantifiers as Finite State Automata. Representing the semantics of quantifiers such as every, no, some, not all, at least 3, more than 5, etc., with finite state automata and gaining a measure of relative complexity of determiner meanings in terms of the relative complexity of automata that can represent them.

Reading:  van Benthem, Johan. 1986. Semantic automata. In Studies in Discourse Representation Theory and the Theory of Generalized Quantifiers (GRASS 8), eds. J. Groenendijk, D. de Jongh and M. Stokhof, 1-25. Dordrecht: Foris.


Thurs, Nov 30: Lecture 21. Applications of Lattice theory: its use in the semantics of mass nouns and plurals, homomorphisms between NP-denotation domains and VP-denotation domains to account for interaction of NP-semantics and telicity. (Bach 1986, Krifka 1992, Link 1998). (mini-introduction; we introduced lattice theory earlier, and it will be nice to see it in action.) Readings:

Bach, Emmon. 1986. The algebra of events. Linguistics and Philosophy 9:5-16. Reprinted in Paul Portner and Barbara H. Partee, eds., Formal Semantics: The Essential Readings, Oxford: Blackwell (324-333).

Krifka, Manfred. 1992. Thematic relations as links between nominal reference and temporal constitution. In Lexical Matters, eds. Ivan Sag and Anna Szabolcsi, 29-53. Stanford: CSLI.

Link, Godehard. 1998. Algebraic Semantics in Language and Philosophy: CSLI lecture notes No. 74. Stanford, Calif.: CSLI Publications.


**Mon** Dec 4, 10-11:15: Lecture 22. OT1: Guest lecture 1 by Rajesh Bhatt.  (Description from 2004, to be revised:) First intro to formalizing OT.  Everyone welcome.  Optional background reading: Andries Coetzee’s dissertation, chapter 2: A Rank-Ordering Model of EVAL.  Available in “Readings” section of the Ling 726 website .  Rajesh’s handout will be in the Lectures section on the course website.

Rajesh’s description from 2004: 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.


Tues Dec 5: Lecture 23. Model-theoretic syntax.  Volodja will present what is now known as model theoretic syntax as he and his collaborators developed it in Moscow several decades ago; he and Barbara, possibly with help from Chris Potts, will give a brief introduction to contemporary work in this area (Rogers, Pullum, Potts and others).


Thurs Dec 7: Lecture 24. Fuzzy logic, fuzzy set theory, theories of vagueness.  Vagueness is central at least in semantics. Possibly also in syntax, with respect to vague boundaries of grammaticality.  Certainly important in computational linguistics and processing theories, w.r.t. processing of less than perfectly well-formed inputs. What kinds of theories of grammar allow us to account for vague boundaries of well-formedness, intensions and extensions? And what kinds of semantic theories are adequate for describing vague concepts and their composition?  In particular: classical fuzzy logic tried but has serious inadequacies; modern versions of fuzzy logic (Petkevič, recent articles) may do better. General question that relates to the earlier topics: Are systems of constraints (e.g. OT) easier to render ‘fuzzy’ than grammars? This topic partly stimulated by recent correspondence with Petkevič, who wishes linguists would stop bad-mouthing fuzzy logic on only the grounds of inadequacies of Zadeh’s earliest versions of it from 40 years ago (Zadeh 1965). References include (Kamp and Partee 1995) on Prototype Theory and Compositionality, a new manuscript by Petkevič, Lasersohn’s work on ‘pragmatic halos’ (Lasersohn 1999), a classic book on vagueness and lexical meaning by Manfred Pinkal (Pinkal 1995), and much more. But we would try to pack some of the key issues into a single lecture as an ‘appetizer’ to a big and important area.


**Mon** Dec 11, 10-11:15 (last class): Lecture 25.  OT2: Guest lecture 2 by Rajesh Bhatt  (Description from 2004, possibly to be revised) 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


Note about late homework:

Absolute last day for turning in homework (late homework or special projects) is Friday December 15, but since no homework will be assigned after mid-November, we really hope to have all homeworks in hand by November 28. There are 12 homeworks total; they are numbered 1-13, but #10 was optional. For late homeworks it's even more important than usual that you first check it yourself (using the back of the book plus the website), and annotate it with corrections, queries, etc.