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.