Fixpoint logic vs. infinitary logic in finite-model theory

The relationship between fixpoint logic and the infinitary logic L/sub infinity omega //sup omega / with a finite number of variables is studied. It is observed that the equivalence of two finite structures with respect to L/sub infinity omega //sup omega / is expressible in fixpoint logic. As a fir...

Full description

Saved in:
Bibliographic Details
Main Authors: Kolaitis, P.G., Vardi, M.Y.
Format: Conference Proceeding
Language:English
Subjects:
Application software
Combinatorial mathematics
Complexity theory
Computer science
Game theory
Logic
Power generation
Spatial databases
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The relationship between fixpoint logic and the infinitary logic L/sub infinity omega //sup omega / with a finite number of variables is studied. It is observed that the equivalence of two finite structures with respect to L/sub infinity omega //sup omega / is expressible in fixpoint logic. As a first application of this, a normal-form theorem for L infinity /sub omega //sup omega / on finite structures is obtained. The relative expressive power of first-order logic, fixpoint logic, and L/sub infinity omega //sup omega / on arbitrary classes of finite structures is examined. A characterization of when L/sub infinity omega //sup omega / collapses to first-order logic on an arbitrary class of finite structures is given.< >
DOI:10.1109/LICS.1992.185518