## Anuj Dawar

## University of Wales, Swansea

## Implicit Definability and Infinitary Logic

- DIMACS Center - Room 431
- Busch Campus
- Piscataway, New Jersey
- November 29, 1995 at 4:30 pm

### Abstract:

The expressive power of first order logic on finite models is known to
be very weak. This has led to the study of a variety of extensions of
first order logic, such as the fixpoint logics, which have been used
to characterize computational complexity classes on finite structures.
Abother extension of the expressive power of first order logic is
obtained by considering implicit definitions. In this talk, I will
relate implicit definability to fixpoint logics by looking at implicit
definability in effective fragments of the infinitary logic with
finitely many variables. While we are able to resolve many of the
containment relations between these fragments, other questions turn
out to be equivalent to outstanding open problems in complexity
theory.
This talk presents joint work with Lauri Hella and Phokion Kolaitis.