Volume 7: January - December 1997

Issue 2: 1997


Existential least fixed-point logic and its relatives

  • Existential least fixed-point logic and its relatives
  • M. Grohe

    Abteilung fur mathematische Logik, Albertstr. 23b, 791-4 Freiburg, Germany. E-mail: grohe@sun1.mathematik.uni-freiburg.de


    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.

    Pages: 205 - 228

    Part of the OUP Journal of Logic and Computation WWW service

    General Information

    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.