Workshops
Participation in workshops is open to all NASSLLI participants. For further
details about them, please contact the organizers directly.
Workshop on Mathematical Logic
Organizer: G.M. Mints (Stanford)
Description: The main goal of this workshop is to introduce the broad NASSLLI audience
to the four traditional areas of mathematical logic (model theory, proof
theory, recursion theory and set theory) through talks of well-known
researchers in these subfields presenting their current research
interests at an accessible level.
Workshop on Games, Logic, and Computation
Organizers: Johan van Benthem (Amsterdam) and Yoav Shoham (Stanford)
Description: Games form a common theme across several NASSLLI areas
these days, including computer science, logic, linguistics,
philosophy, and economics. This workshop will show some
recent developments by actors at this lively interface.
Schedule:
Monday
Rohit Parikh [Logic and Games: Using Games to Understand Semantics]
The use of two person games has been an important aspect
of semantics since the work of Ehrenfeucht and others. These
techniques can be extendedto other contexts, e.g. in IF logics,
reasoning about knowledge, and yet other contexts. We will
give an overview of some of this territory.
Tuesday
Johan van Benthem [Games and Logic: Using Logic to Understand Games]
Both mathematical logic and philosophical logic meet game
theory in a number of shared interests. We will discuss some
of these, including: (a) modeling games as processes up to
simulation, plus appropriate epistemic 'superstructure',
(b) what is the purpose of logical systems over these?
Note: This will be more of a logician's perspective:
the economists will have the last word on Friday.
Wednesday
Prashant Parikh [Language and Information Flow]
I will use game theory to show how the distinction between natural
and nonnatural meaning (or information flow) that Grice introduced
in the late forties can be defined. It will be shown how the
distinction gives rise to a range of concepts of information flow
and how game theory provides a neat way to capture this range.
In so doing, it will be seen that it is necessary to go beyond
the traditional confines of game theory and consider more general
structures that I call strategic interactions. I will also touch
upon how the game theory can be used to model ambiguity resolution
in language as well as implicatures.
Thursday
Moshe Tennenholtz [Introduction to Mechanism Design]
The talk will cover briefly some concepts in game theory, and
in particular Bayesian games, and introduce the theory of
economic mechanism design. We will illustrate the theory of
mechanism design through a discussion of auction theory.
Friday
Yossi Feinberg [Reasoning in Economics]
We provide a brief roadmap of the evolution of reasoning in game
theory. The role of reasoning about behavior is examined through
refinements to the Nash equilibrium solution. We emphasize refi-
nements for games with private information. These games have been
tremendously instrumental in economic theory, having followed the
formal modeling of uncertainty in interactive decision situations.
Finally, recent explicit models for reasoning are presented
demonstrating the convergence towards methods in logic
and computer science.
Workshop on Model-Theoretic Syntax
Organizer: Geoffrey K. Pullum (UCSC)
Description: Nearly all formally precise theoretical frameworks for natural language
syntax over the past fifty years have been based on a single idea:
generating sets of strings (or sets of other algebraic objects) using
techniques based on Post's production systems --- originally conceived
as a way of mathematicizing the application of inference rules to
axioms. A grammar of this sort is something like a program for a
nondeterministic abstract machine of which every run enumerates some
member of a specific set that the machine thereby defines. There is a
different way to look at syntax, based on model theory rather than proof
theory: we define a logical description language DL, and formulate in DL
a set G of statements about the structure of expressions of the natural
language NL which is to be described. We say that an expression of NL
is grammatical only if it satisfies all the members of G, in the usual
model-theoretic sense of satisfaction. Given some choice of a set M of
models for DL, we can also say that if a model in M satisfies G, then
that model is (or represents) a grammatical expression of NL. G can thus
be regarded as a grammar for NL, though it does not generate the members
of NL in the ordinary sense.
Under this view, issues like how many expressions of NL there might be
(are natural languages truly infinite?), or how large expressions of
NL can be (can there be infinitely long sentences?), are revealed as
pseudo-problems, entirely dependent on what class of models we choose
to focus on. Such questions have no clear substantive answer, and need
none. Instead, entirely different kinds of question are raised. What
sorts of constraints on expression structure are needed for describing
the syntax of natural languages? What sort of expressive power is needed
in a logical description language to permit such constraints to be
stated? How can it be ensured that satisfiability is decidable (so that
for a given grammar it is possible to determine whether it defines some
expressions as grammatical)? What is the complexity of satisfiability,
model checking, and other problems for particular logical description
languages? What kinds of abstract structure are the best candidates for
representing natural language expressions? What results in finite model
theory are there that pertain to models of that type?
Although almost all work in syntax has been tacitly proceeding along
other lines for decades, the ideas of model-theoretic syntax have slowly
been developing nonetheless. As early as the first half of the 1970s it
was adumbrated in ideas of syntacticians such as George Lakoff, David M.
Perlmutter, and Paul Postal. By the end of the 1970s it was the basis
for the arc pair grammar of Johnson and Postal. It clearly figured in
the formal bases of the LFG of Bresnan and Kaplan. During the 1980s,
such lines of research as GPSG and HPSG evolved towards it. GB theory
illustrated the possibility of a mixed approach involving an overlay of
constraints on a generative basis. Meanwhile the term "constraint-based"
became a familiar description for certain theoretical work in computational
lingistics.
However, it was only during the 1990s that rigorous foundational work
connecting model theory and syntax began to appear; particularly
important work has been published by (among others) Patrick Blackburn,
Claire Gardent, Hans-Peter Kolb, Marcus Kracht, Tore Langholm, Wilfried
Meyer-Viol, Uwe Moennich, Frank Morawietz, and James Rogers (the term
"model-theoretic syntax" appears to have been coined by Rogers in 1996).
This workshop will provide an overview of the subject, an introduction
to some current technical research in logic and model theory that bears
on theories of natural language syntax, and some applications to current
problems of description and explanation in linguistics. (It should be
noted that current construction-oriented versions of HPSG and also the
clearly constraint-based approach of optimality theory are obvious
candidates to explore in this connection.)
The workshop convener, Geoffrey K. Pullum, will provide an introductory
survey lecture, and it is hoped that the other presenters will include
Patrick Blackburn, Marcus Kracht, Christopher Potts, and James Rogers.
Workshop on Cognition: Formal Models and Experimental Results
Organizer: John Perry (Stanford)
Description: Cognition is an area where issues of logic, language and
information meet with the real mechanisms of human activity,
as studied by psychologists and neurobiologists. NASSLLI's
concluding cognition workshop will feature back-to-back talks
by leading researchers exploring topics at this interface,
including neural nets, grammar models, perception, and context.
Speakers are Paul Smolensky (Johns Hopkins), Brian Wandell
(Stanford), Reinhard Blutner (Amsterdam), Alan Shillcock
(Edinburgh), Varol Akamn (Bilkent), and Ken Taylor (Stanford).
The workshop is intended to explore shared research concerns
across the cognitive sciences, ranging from symbolic
representation to embodied cognition. In particular, there will
be a final roundtable discussion on 'Approaching Cognition'.