Fixpoint logic vs. infinitary logic in finite-model theory
- 2 January 2003
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
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.<>Keywords
This publication has 28 references indexed in Scilit:
- On the Expressive Power of Datalog: Tools and a Case StudyJournal of Computer and System Sciences, 1995
- The invariant problem for binary string structures and the parallel complexity theory of queriesJournal of Computer and System Sciences, 1992
- When is arithmetic possible?Annals of Pure and Applied Logic, 1990
- Data independent recursion in deductive databasesJournal of Computer and System Sciences, 1989
- Inductive pebble games and the expressive power of datalogPublished by Association for Computing Machinery (ACM) ,1989
- Theory of database queriesPublished by Association for Computing Machinery (ACM) ,1988
- Decidable optimization problems for database logic programsPublished by Association for Computing Machinery (ACM) ,1988
- Second-order and Inductive Definability on Finite StructuresMathematical Logic Quarterly, 1987
- Structure and complexity of relational queriesJournal of Computer and System Sciences, 1982
- Monadic generalized spectraMathematical Logic Quarterly, 1975