[pl-seminar] Michael Benedikt visiting

["Thomas Reps" <reps@xxxxxxxxxxx>]

Michael Benedikt from Lucent is giving a talk in the Math department
at 3:30 PM in 901 Van Vleck Hall; Jack Lutz gives a talk immediately
after

Benedikt's talk: Decision problems for regular tree languages and the
model theory of trees

Surprisingly, the model theory of first-order logic when restricted to
many "well-behaved" classes of finite models - such as finite trees - is
not at all well-understood. As an example consider the problem of
"characterizing first-order definability on trees" - determining whether
a regular tree language (equivalently, tree automaton) is defined by
some first-order logic sentence. First-order here means either
first-order over the vocabulary including only node labels and the child
relation, or in the vocabulary including also the descendant relation.
The decidability of first-order definability in the latter sense remains
open after two decades; in this talk I outline our proof that
first-order definability in the first sense is decidable. In the case of
strings rather than trees, the analogous problem is that of deciding
whether a regular string language is "locally threshold testable". This
was shown to be decidable by Beauquier and Pin, who characterized
first-order definability via identities satisfied in the monoid
associated with a regular language. Our characterization and decision
procedure for first-order logic on trees uses an approach that combines
the algebraic approach with locality arguments. We show how the
characterization of definability gives a new "semigroup-free" proof of
Beauquier and Pin's theorem, and how it can be useful in resolving other
questions in the finite model theory of trees, in particular recovering
consequences of the interpolation theorem for trees.
This is joint work with Luc Segoufin.

Lutz's talk: New dimensions in the theory of computing

Recent developments in the theory of computing give a canonical way of
assigning a dimension to each point of n-dimensional Euclidean space.
Computable points have dimension 0, random points have dimension n, and
every real number in [0,n] is the dimension of uncountably many points.
If X is a reasonably simple subset of n-dimensional Euclidean space (a
union of computably closed sets), then the classical Hausdorff dimension
of X is just the supremum of the dimensions of the points in X. In this
talk I will discuss the meaning of these developments, their
implications for both the theory of computing and fractal geometry, and
directions for future research. 


http://www.math.wisc.edu/~lempp/conf/swlc.html