Fixed point logics

Bulletin of Symbolic Logic 8 (1):65-88 (2002)
  Copy   BIBTEX

Abstract

We consider fixed point logics, i.e., extensions of first order predicate logic with operators defining fixed points. A number of such operators, generalizing inductive definitions, have been studied in the context of finite model theory, including nondeterministic and alternating operators. We review results established in finite model theory, and also consider the expressive power of the resulting logics on infinite structures. In particular, we establish the relationship between inflationary and nondeterministic fixed point logics and second order logic, and we consider questions related to the determinacy of games associated with alternating fixed points

Other Versions

No versions found

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 99,362

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Supervaluation fixed-point logics of truth.Philip Kremer & Alasdair Urquhart - 2008 - Journal of Philosophical Logic 37 (5):407-440.
Complete problems for fixed-point logics.Martin Grohe - 1995 - Journal of Symbolic Logic 60 (2):517-527.
Yet another hierarchy theorem.Max Kubierschky - 2000 - Journal of Symbolic Logic 65 (2):627-640.
Expressive equivalence of least and inflationary fixed-point logic.Stephan Kreutzer - 2004 - Annals of Pure and Applied Logic 130 (1-3):61-78.
Definable fixed points in modal and temporal logics — a survey.Sergey Mardaev - 2007 - Journal of Applied Non-Classical Logics 17 (3):317-346.
Arity hierarchies.Martin Grohe - 1996 - Annals of Pure and Applied Logic 82 (2):103-163.
Descriptive complexity theories.Joerg Flum - 2003 - Theoria 18 (1):47-58.
Finite variable logics in descriptive complexity theory.Martin Grohe - 1998 - Bulletin of Symbolic Logic 4 (4):345-398.
The expressive power of fixed-point logic with counting.Martin Otto - 1996 - Journal of Symbolic Logic 61 (1):147-176.

Analytics

Added to PP
2009-01-28

Downloads
56 (#314,084)

6 months
7 (#553,680)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Expressive equivalence of least and inflationary fixed-point logic.Stephan Kreutzer - 2004 - Annals of Pure and Applied Logic 130 (1-3):61-78.
ŁΠ logic with fixed points.Luca Spada - 2008 - Archive for Mathematical Logic 47 (7-8):741-763.
Symbioses between mathematical logic and computer science.Andreas Blass - 2016 - Annals of Pure and Applied Logic 167 (10):868-878.

Add more citations

References found in this work

Elementary Induction on Abstract Structures.Wayne Richter - 1979 - Journal of Symbolic Logic 44 (1):124-125.
Fixed-point extensions of first-order logic.Yuri Gurevich & Saharon Shelah - 1986 - Annals of Pure and Applied Logic 32:265-280.
Descriptive Set Theory.Yiannis Nicholas Moschovakis - 1982 - Studia Logica 41 (4):429-430.
Finite Model Theory.Heinz-Dieter Ebbinghaus & Jörg Flum - 2001 - Studia Logica 69 (3):449-449.

Add more references