Linguistics 726: Mathematical Linguistics

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


Contact info:
Barbara H. Partee, Vladimir Borschev
Office: So. College 222
Phone: 545-0885

Required text:
Partee, ter Meulen and Wall (1990 - Corrected first edition, 1993 or later), Mathematical Methods in Linguistics, Dordrecht: Kluwer: Student edition (paperback). Available at Atticus* or through or .
Other readings will be xeroxed.
Other books useful for supplementary topics will be suggested, and we will work out how to make them available.

Course description:
(Note: a more accurate title for this course might be “mathematics in and for linguistics”; the term “mathematical linguistics” now mostly refers to ‘formal language theory’. But this course title is on the books, and it’s not unreasonable in principle.)

The first goal of the course is to strengthen students’ math background in the areas most widely relevant to linguistic theorizing: linguists in all subfields are concerned with “structures” and their formal properties. “Structures” are in general algebras; “theorizing” generally involves positing axioms (in some logic) and studying properties of the models that satisfy those axioms (this is what model theory is about). The algebraic notions of isomorphism and homomorphism formalize the notion of "same structure". Other basic background notions include elementary set theory and first-order logic. When we formalize the syntax and semantics of propositional and first-order logic, we can illustrate what it means to say “compositionality can be formalized as a homomorphism between a syntactic algebra and a semantic algebra”. We will look at the ingredients of the notion of ‘trees’ (formally, this is ‘graph theory’, but we won’t go into graph theory), and practice figuring out the consequences of varying different parameters in the definition. We will include a bit of automata theory and formal language theory in order to be able to talk about the Chomsky hierarchy of languages (finite-state languages, context-free languages, etc.) Some examples of simple algebras will include semilattices, lattices, and Boolean algebras: in the second part of the course we can consider applications to ‘feature algebras’, Link’s semantics for mass and plural, event algebras, type-shifting, and OT. The first part of 726 is similar to the undergraduate course 409, but we will go a little faster in 726 and there will be more opportunity for exploration of application to topics of particular interest to participants.

The second goal of the course, to be pursued in the second half, will be to explore linguistic applications of these basic notions and to work on more specific mathematical and logical tools that may be needed/useful in particular linguistic research paradigms. The following are some examples. Some may be of enough interest for us to look at together; other topics might be pursued by individual students or subgroups, depending on interest. (i) OT makes some use of lattice theory; (ii) Godehard Link's work uses lattice structures for the semantics of mass and plurals and Link, Bach, Krifka, Landman and others have extended such structures to the eventuality domain and for mappings between the entity domain and the eventuality domain. (iii) Angelika Kratzer has noted some interesting structural parallels among modality, OT, and pragmatics, all based on formal work on ways of revising inconsistent sets of premises and relating to the partitioning of sets of premises. (And the notion of giving priority to the more specific rule over the less specific may be part of this family of notions.) (iv) An algebraic perspective on categorial grammars links syntax, semantics, type theory, logical deduction (via the Lambek calculus), and the type-shifting exploited in Ades and Steedman processing models. (v) Keenan (course notes 2000) uses phonological feature systems to illustrate equivalence relations, partitions, Boolean lattices, closure properties, atomicity, and other algebraic properties. (vi) Unification-based grammar systems (LFG, GPSG, HPSG, and unification-based categorial grammars) build on feature structures that have much in common with phonological feature structures, and a glimpse at such structures and the algebra of unification may be of general interest.

The course has no specific prerequisites, but the pace and workload will be a bit more demanding than that of Linguistics 409, which will also be offered in Fall 2001 (by Partee and de Lacy). Students who would benefit from a slightly slower-paced course with more emphasis on the fundamentals might take 409 rather than 726. If in doubt, consult us.

Course Requirements:
First half: frequent homework. Second half: a choice between continued homeworks or an individual or team project such as working through some research paper(s) or book sections that require some mathematical tools, in consultation with the instructors.

Basic Plan:

Part 1. Basic notions of set theory.
Lectures 1-3, with Homeworks 1-3. September 6, 11, 13. Sets, subsets, operations on sets. Ordered pairs and Cartesians products. Relations. Functions and their compositions. Properties of relations and classes of relations.

Part 2. Intro to algebra.
Lecture 4, Part 1. Algebra, Section1. Signature, algebra in a signature. Isomorphisms, homomorphisms, congurences and quotient algebras. September 18, 20, with Homework 4. Lecture 4, Part 2. Algebra, Section 2. Lattices, Boolean algebra. September 25, Homework 4.2.

Part 3. Logic and formal systems. (about 5 classes)
Lecture 5. Logic, Section 1. Statement logic, including Syntax and Semantics as algebras with a homomorphism between them. (September 27, Oct 2), Homework 5.
Lecture 6. Logic, Section 2: Predicate logic. Axioms and Theories. Homework 6. Oct 4, 9.

Logic-algebra bridge
Lecture 7. Logic, Section 3: Axiomatic description of properties of relations. Algebra Section3: Homomorphisms, congruences and quotient algebras. Homework 7. (all Algebra) Oct 11.

Part 4. More Algebra.
Lecture 8. Algebra, Section 4. Word algebras and freeness. Oct. 16, 18. Homework 8.2.
Lecture 9. Logic and algebra. Statement logic as a word algebra on the set of atomic statements. Lindenbaum algebra: logic as Boolean algebra. Oct. 18, 23. Homework 9.

Part 5. A mixture of set theory, logic, and algebra, with some applications.
Lecture 10. Model theory. Consistency, independence, completeness, categoricity of axiom systems. Examples. Parts of PtMW Chapter 8: 8.1, 8.4, 8.5. Homework 10. Oct. 23, 25.
Lecture 11. Peano’s axioms and proof by induction. PtMW Ch 8.4. Homework 11. Oct 25.
Lecture 12. More algebra: groups, semigroups, monoids, concatenation, strings. PtMW Ch 10. Homework 12. October 30.
Lecture 13. Formal Phonology - Features and their Structure.
Lecture 14. Set theory: infinities. Diagonal proofs of non-denumerability. PtMW Ch 4. Homework 14. Nov 6.

More algebra: feature systems, unification, more lattices. Homework 13. Nov 1.

Part 6. Automata theory and formal grammars. (about 5 classes)
Lecture 15, Lecture 15.2. Finite state automata and corresponding grammars. Finite state automata as a Boolean algebra.
[Enrichment topic: Finite state transducers in phonology and morphology. ]
Lecture 16. Natural Language Quantifiers as Finite State Automata (van Benthem 1984).
Lecture 17. Push-Down Storage automata and Context-Free Grammars. Proofs of non-context-freeness (The Pumping Lemma). Are natural languages context-free? Turing machines (very briefly) and the Chomsky Hierarchy.

Part 7. Further topics. TBA. (see ideas on Sept 25 update) No homework in December.

1. Mildly context-sensitive grammars. Tree-Adjoining Grammars (TAGs) (Joshi 1987), Combinatory Categorial Grammars (Steedman 1996), Head Grammars (Roach 1987), Linear indexed grammars (Gazdar 1987): four different grammar formalisms that converge on a single class of languages. Of interest both for perspectives on grammar formalisms and because it has been suggested that natural languages are themselves mildly context-sensitive. We could go into this without going into all four grammar formalisms; the first two mentioned are the best known to BHP. In the context of CCGs we could also look at categorial grammars and “parsing as proof” (Lambek systems, etc.). Optional: Partee and Marsh on “How non-context-free is variable-binding?” (makes use of index grammars, includes a still-open question.)

2. Algebraic perspectives on grammars. Grammars as generating systems, tree-checking systems, other perspectives. Grammars of grammars. Volodja’s “neighborhood grammars”.

3. Relational data bases as models of predicate logic.

4. OT issues (we’ll need help from the phonologists). Karttunen’s work on modelling OT using finite transducers.

5. Modal logic, models and axioms. Belief-revision issues.

6. Dynamic logic.
Other suggestions? (also other possibilities mentioned in course description)

Note on Homework:
It is suggested that most students do most homeworks for the first part of the course, units 1-3 (set theory, Algebra Part I, logic and formal systems), allowing that whenever we are covering material you already know, you can opt out of the homework to do some exploring of potential further topics or enrichment topics. Around the mid-point of the course (first choice point), students can choose whether to continue with daily homework or to start on a separate project or projects alone or in teams, with our advice and involvement (by negotiation.)
In the last part of the course (the ‘to be determined’ topics), there will be even more possibility of splitting into groups to investigate particular units of interest.

What we’d like from you: “Your Ideas” Questionnaire.
Please give us (preferably via e-mail so it’s easier for Volodja to see it too while he’s in Russia: and ) a statement of intention, however tentative, of what you’d like to do.

Would you like to continue doing homeworks of the sort we’ve been assigning? As the course progresses, we will look for more real-life linguistic examples to include as the material to work with formally, so there will be a mixture of ‘pure math’ and ‘applied math’ here. Comments on the homework so far? Has it been helpful? (It looks like it has from our end.) [Note: some people are registered for credit but have given us few or no homeworks.

We would like to see what you’re doing even if you don’t need detailed feedback. We do require that those for credit do some reasonable amount of written work. (And we won’t always give detailed feedback if answers are available in the back of the book and/or on the web.)]Would you like to continue doing “some” homework but also try to find a small project that is closer to some area of interest of yours, perhaps with help and suggestions from us? Ideas about what sort of thing it might be? (Some suggested areas were mentioned in the syllabus, others might be suggested by the article by Pullum and Kornai distributed at the beginning. You could also borrow Ed Keenan’s course packet from me and see some of the things he did there.)

Would you like to soon start working mostly independently (or with a group) on some particular project that you already have ideas about? Tell us about it. We’ll ask for a more formal description later. (And the balance between how much regular homework and how big a project you do is open for negotiation – we’re flexible, just want you to spend a reasonable amount of time and effort overall.)

We would like to compile a list of useful references very soon to help all those who may be interested in projects. If you already know of some references that seem to you to be relevant to what you are interested in, write them down so we can include them on a sharable list.Other comments about the course and how it could be improved? Are you making use of the website and is it helpful?