Mathematical Linguistics Circle: Schedule of Talks

UCLA Department of Linguistics
Fall 2005

The Mathematical Linguistics Circle (Linguistics 261) will meet Fall Quarter 2005 in Haines A28.  
Meetings are typically Thursdays from 4 to 6.
If you would like to give a talk, please contact the convener, Edward Stabler.

Thursday, October 6:
"Modal Logic and Model Theoretic Syntax"
Marcus Kracht, UCLA

Model theoretic syntax is the study of syntactic structures
with logical means. It is often taken to assume that structures
are not generated but this is a misconception. In this talk
I shall provide an overview of my own attempts to formalise
Government and Binding as well as the Minimalist Program
using modal logic. The derivation is collapsed into a structure
in the same way as a context free derivation is collapsed into
an analysis tree. Every language L thus describes a class of
structures and therefore corresponds to a modal logic Lg(L). A
large class of these logics has been shown to be decidable and
it is hoped that eventually I shall be able to show that virtually
all logics that fall into this paradigm are decidable as well.
This will have applications that go beyond the interests of
linguists. I mention only research into path languages such as
XPath.

Thursday, Nov 3:
"On Characterizing the Context Free Languages"
Marcus Kracht with Alexis Manaster-Ramer
Special time and place:
Marcus Kracht, 919 Levering Avenue, Apt 107,
Los Angeles, CA 90024
Phone: (310) 208 7320
Time: 6pm

There are three classic results used to show that a language is not
context-free (a CFL): the pumping lemma, Ogden's lemma (a stronger
version of the former), and the Interchange lemma. In the early
1990's, Alexis MR, Andrew Moshier and Suzanne Zeitman proved another
result (apparently) strengthening the pumping and Ogden's lemmas,
which has never been published. It shows that for every CFL there
is a number K such that for every m and every string in which mK
positions are designated there are at least m indepedent pumping
pairs that involve each at least one but less than K designated
positions (an outline of the proof will be presented by Marcus K).

Several different directions of research, proposed at the time,
remain largely open. The only results in this area are Marcus K's.
He has proved (as will be discussed) that neither the independent
pumping lemma nor even its conjunction with the interchange lemma
characterize the CFL's. However, apparently nothing else has been
attempted on such problems as
(a) formulating even stronger pumping and/or interchange results
    for CFLs,
(b) proving similar results for other classes of languages, including
    both supersets of the CFLs and such (informally defined) classes
    of Alexis MR's "queue languages",
(c) attempting to find a strong enough pumping property to
    CHARACTERIZE the CFLs, if this is at all doable, or even
(d) showing that there are non-CFLs satisfying all the previous
    lemmas but not MR-M-Z's independent pumping lemma (i.e.,
    proving that it really is stronger than in particular Ogden's
    lemma).
Likewise, no further work has been done on the original linguistic
motivations for this approach advanced by Alexis MR in the late
80's and early 90's.  Some of those open problems will be discussed.