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%)
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.