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

**Phokion G. Kolaitis Moshe Y. Vardi**

### 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 = {Phokion G. Kolaitis and Moshe Y. Vardi}, title = {Fixpoint logic vs. infinitary logic in finite-model theory}, booktitle = {Proceedings of the Seventh Annual IEEE Symposium on Logic in Computer Science (LICS 1992)}, year = {1992}, month = {June}, pages = {46--57}, location = {Santa Cruz, CA, USA}, publisher = {IEEE Computer Society Press} }