## 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} }