Linguistics 726: Mathematical LinguisticsBarbara Partee and Vladimir Borschev

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 13, with Homeworks 13. 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, nondenumerable 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), nondenumerably infinite (Langendoen and Postal), unspecified as between denumerably and nondenumerably 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 LogicAlgebra 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)
Supplementary readings available online: (1) List of references: "A sampling of papers on trees or including definitions of trees", compiled with help from Chris Potts. [PDF file]. (2) From Chris Potts, a selection of definitions of trees from various sources. "Trees". [PDF file]. (3) Blackburn, Patrick, Gardent, Claire, and MeyerViol, Wilfried. 1993. Talking about trees. In Proceedings of the 6th Conference of the European Chapter of the Association for Computational Linguistics (EACL 93), 21  29. Utrecht, the Netherlands. [PDF file].
Supplementary readings handed out but not available online: (1) From Youri Zabbal 2004: Defining trees in graph theory. (2) Zwicky, Arnold M., Jr., and Isard, Stephen. 1963. Some aspects of tree theory. Working Paper. Bedford, MA: The MITRE Corporation.
October 1719:
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 http://www.cs.uoregon.edu/~dhofer/induction.html .
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 31Nov 2:
Lectures 1314. 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. Finitestate languages. Regular expressions. Ways of proving that a given language is not a finitestate language. Homework 13.
Homework 13 Solutions (Finite State Automata)
Nov 7:
Lecture 15. Finite state languages and human languages. Are natural languages finitestate languages? Weak and strong generative capacity, competence/performance issues. Hauser et al’s arguments that human language exceeds finitestate machine capacity, while animal language does not. Links to readings available online are in the handout and also here: http://people.umass.edu/partee/726_04/readings.html
(And/or see links in WHISC of September 23 2004: http://www.umass.edu/linguist/about/whisc/whisc2004923/.) No homework.
Nov 9:
Lecture 16. Contextfree grammars and PushDown Storage Automata.
Proofs of noncontextfreeness (The Pumping Lemma). Are natural languages contextfree? 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 1819. 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 firstrate." 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, 125. Dordrecht: Foris.
Thurs, Nov 30: Lecture 21. Applications of Lattice theory: its use in the semantics of mass nouns and plurals, homomorphisms between NPdenotation domains and VPdenotation domains to account for interaction of NPsemantics and telicity. (Bach 1986, Krifka 1992, Link 1998). (miniintroduction; 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:516. Reprinted in Paul Portner and Barbara H. Partee, eds., Formal Semantics: The Essential Readings, Oxford: Blackwell (324333).
Krifka, Manfred. 1992. Thematic relations as links between nominal reference and temporal constitution. In Lexical Matters, eds. Ivan Sag and Anna Szabolcsi, 2953. Stanford: CSLI.
Link, Godehard. 1998. Algebraic Semantics in Language and Philosophy: CSLI lecture notes No. 74. Stanford, Calif.: CSLI Publications.
**Mon** Dec 4, 1011: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 RankOrdering 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 SamekLodovici 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. Modeltheoretic 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 wellformed inputs. What kinds of theories of grammar allow us to account for vague boundaries of wellformedness, 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 badmouthing 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, 1011: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 FiniteState Methods in Natural Language Processing. Bilkent University. Ankara, Turkey. June 29July 1, 1998. (HTML, Postscript). (ROA2580498) (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 midNovember, we really hope to have all homeworks in hand by November 28. There are 12 homeworks total; they are numbered 113, 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.