M. Grohe Abteilung fur mathematische Logik, Albertstr. 23b, 791-4 Freiburg, Germany. E-mail: firstname.lastname@example.org
The main objects of our interest are the existential fragment [exist]LFP of least fixed-point logic, stratified fixed point logic SFP, which is the smallest regular logic containing [exist]LFP, and transitive closure logic TC. The main result of the first part of this paper is a normal form for [exist]LFP, which transfers to SFP to a certain extent. We study some of the consequences of this normal form and show that TC can be seen as a natural fragment of SFP. The second part of the paper is concerned with separating the logics under consideration. Furthermore, it shows that the existential preservation theorem fails for TC and SFP (both on finite and arbitrary structures). The method used to show this also yields a negative answer to a question posed by Rosen and Weinstein concerning first-order sentences preserved under extensions of finite structures.
Part of the OUP Journal of Logic and Computation WWW service
Click here to register with OUP.
This page is maintained by OUP admin
Part of the OUP Journals World Wide Web service.
Last modification: 22 Jul 1997
Copyright© Oxford University Press, 1997.