Martin Grohe

University of Freiburg

Existential Least Fixed-Point Logic and its Relatives

DIMACS Center - Room 431

Busch Campus

Piscataway, New Jersey

October 18, 1995 at 4:30 PM

Abstract:

The existential fragment ELFP of least fixed-point logic has turned out to be intersting both from the computer scientist's and the model theorist's point of view. We give a normal form for this logic which basically shows that ELFP-formulas speak about the existence of certain binary trees. Consequences of this normal form are not only several known results due to Blass and Gurevich, but also, for example, an Ehrenfeucht-Fraisse like characterization of the logic. To a certain extent, this normal form can be transfered to the stronger stratified fixed-point logic SFP, with similar consequences for this logic.

We will see that transitive closure logic is a natural fragment of SFP and turn to questions concerning the expressive power of these logics. This finally leads us to the result that the existential (or substructure) preservation theorem fails for transitive closure logic and for least fixed-point logic (both on finite and on arbitrary structures).