|
Contact info:
Barbara H. Partee, Vladimir Borschev
Office: So. College 222
Phone: 545-0885
E-mail: partee@linguist.umass.edu, borschev@linguist.umass.edu
Webpage: http://www.people.umass.edu/partee
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
www.amazon.com
or www.barnesandnoble.com .
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: partee@linguist.umass.edu
and borschev@linguist.umass.edu ) 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?
|