**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

Office: So. College 222; 545-0885

Home phone: 549-4501

E-mail: partee@linguist.umass.edu,
borschev@linguist.umass.edu

**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 http://www.cs.uoregon.edu/~dhofer/induction.html
.

**
**

**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**.

**
**

**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**

**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.