**Linguistics 570**

**Mathematical Linguistics**

**Required Texts**

Barbara Partee. 1983. * Foundations of Mathematics for
Linguistics.*

Course Description

This provides a variety of mathematical tools
used in linguistics in areas such
formal semantics, grammar formalisms,
and computational linguistics. Areas covered
include set theory, basic algebraic structures such
as groups, lattices, and boolean algebras, foundations of formal
language theory, and propositional and first-order logic. Some examples
of linguistic applications of the concepts covered
will be given. Some emphasis
is placed on doing proofs.

Grading

Assignments(40%)

Midterm (20%)

Final(40%)

### Course Outline

**
****Week 1-4: Introduction to set theory**

Sets, set membership, subsets, union, intersection,
complementation. Mappings, functions, and relations. Injections,
surjections, and bijections.

**Week 5,6: Groups and lattices**

**Week 7: Boolean algebras**

**Week 8: Elementary linguistic feature structures. **

Syntactic feature structures. Features structures as
a lattice. Feature structures as a Boolean algebra.

**Week 9: Automata and formal language theory. **

Finite-state automata and regular sets. Push down automata.

**Week 10,11: Finite-state and context-free grammars.**

Strong equivalence of finite-state grammars, finite-state-automata and
regular expressions. Center-embedding: Inadequacy of finite-state
grammars for natural languages. Equivalence of pushdown automata and
context-free languages.

**Week 12,13:**

Propositional logic.
Proofs and truth-table checking.
First-order logic.

**Week 14:**

Set theory and Tarskian first-order models of first-order
logic. Tarskian models as models of truth-conditions.
**Week 15:**

Heimian Dynamic semantics with Tarskian models.
Heimian information-states. Information-states
as a lattice with an informational
ordering.