Linguistics 726: Mathematical Linguistics

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

description | schedule and lectures | 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 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 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.

 

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.       See handout from 726 2004: http://people.umass.edu/partee/726_04/lectures/Lecture%2013%20revised%20Are%20NLs%20Finite-state.pdf ; links to readings available online are here: http://people.umass.edu/partee/726_04/readings.html

 (And/or see links in WHISC of September 23 2004:  http://people.umass.edu/potts/whisc/whisc-2004-9-23.html#hauser .)   Homework 14 (last).

 

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: 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: Christ 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.

 

(Schedule up to this point relatively concrete)

 

***** 

November 28, 30, December 5, 7, 12:

Further topics (choices and details to be decided later)

    -- There are more topics than days listed here, so there will be choices to be made. We certainly won’t have time to do these things with any thoroughness; whatever we do in these last topics will be designed mainly to whet your appetites and open up possibly unfamiliar topics or unfamiliar approaches to familiar topics, to pursue when and where you can.

 

Most likely to be included -- topics (1) and (2) below.

 

(1) One or two guest lectures by Rajesh Bhatt on OT.

TBA: OT1: Guest lecture 1 by Rajesh Bhatt. (Probably Nov 14 or 16) (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.

 

TBA: 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

 

(2) Model theory vs. proof theory: what is the difference, and why does it get into debates about the nature of grammars?

Kathryn Pruitt asked about this topic and noted the following reference to it: "Regarding the issue of proof-theoretic vs. model-theoretic in linguistic
theory, the June 2006 issue of Language (vol 82, no 2) includes a letter to the editor from Postal in which he indicates that NLs cannot have proof-
theoretic grammars "in the technical sense" because there can be "well-formed sentences in natural language L some of whose parts are not composed of elements drawn from any conceivable lexicon or morhpeme listing of L" (p 229). He also indicates that this is the conclusion reached in Ch 6 of his
book "Skeptical Linguistic Essays" (which is reviewed in the same volume of Language, p 442). I haven't read the book, but from its review, he appears to be arguing, among other things, that operations considered by minimalist syntacticians to be "virtual conceptual necessities" (merge, move, copy) are only viewed as such because of the adoption of a proof-theoretic grammar. Thus, they aren't 'necessary' outside of a proof-theoretic framework."  Since we will mention model theory vs. proof theory anyway, in Lecture 9, this is a natural topic to expand on. And at the same time we can describe briefly what is meant by "Model-theoretic syntax".  Volodja can 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, could give a brief introduction to contemporary work in this area (Rogers, Pullum, Potts and others).

 

(3) Formal language theory.

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 “mildly non-CF”?

 

(4) Recursion. What does recursion look like in grammars and in other kinds of systems? What sorts of claims have been made recently about recursion – look at the debates. By this time we will already have discussed the relevant mathematical notions and the focus will be on seeing how they are being used, and sometimes perhaps misused, in current discussions. Tom Roeper has some recent papers with William Snyder relating to acquisition and recursion, and there has been debate among Chomsky, Hauser, and Everett on the significance or not of evidence that ‘starlings have recursion’. (Our own) Bart Hollebrandse, visiting all this year, is preparing the materials on recursion that Everett is using in a big project that Uli Sauerland has organized – perhaps he would be willing to participate if we have a day on these issues. (These are related to topics already on the agenda above concerning whether natural languages are or are not finite-state, are or are not context-free.)

 

(5) A different topic: 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’, a classic book on vagueness and lexical meaning by Manfred Pinkal, 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.

 

(6) 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 will have introduced lattice theory earlier, and it might be nice to see it in action.)

 

(7) Language and mathematical reasoning – current Whorfian debates about what’s prerequisite for what.  See recent debate between Susan Carey (2004) On the Origin of Concepts  and Gelman and Butterworth (2005) ‘Number and language: how are they related?’.  What properties are similar/different between our innate capacity for language and our innate capacities in mathematical domains (counting, adding, comparing, etc)? This topic is not very technical, since it involves some of the most basic notions, but it could be quite thought-provoking, also because it involves some of the most basic notions.

  

Note about late homework:

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 December 5.