## 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).