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.

Abstract

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

BibTeX

  @InProceedings{KolaitisVardi-Fixpointlogicvsinfi,
    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}
  }