Seventh Annual IEEE Symposium on

Logic in Computer Science (LICS 1992)

Paper: Fixpoint logic vs. infinitary logic in finite-model theory (at LICS 1992)

Authors: Kolaitis, P.G. Vardi, M.Y.


The relationship between fixpoint logic and the infinitary logic L∞ωω with a finite number of variables is studied. It is observed that the equivalence of two finite structures with respect to L∞ωω is expressible in fixpoint logic. As a first application of this, a normal-form theorem for L∞ωω on finite structures is obtained. The relative expressive power of first-order logic, fixpoint logic, and L∞ωω on arbitrary classes of finite structures is examined. A characterization of when L∞ωω collapses to first-order logic on an arbitrary class of finite structures is given


    author = 	 {Kolaitis, P.G. and Vardi, M.Y.},
    title = 	 {Fixpoint logic vs. infinitary logic in finite-model theory},
    booktitle =  {Proceedings of the Seventh Annual IEEE Symp. on Logic in Computer Science, {LICS} 1992},
    year =	 1992,
    editor =	 {Andre Scedrov},
    month =	 {June}, 
    pages =      {46--57},
    location =   {Santa Cruz, CA, USA}, 
    publisher =	 {IEEE Computer Society Press}