Yet another hierarchy theorem

Journal of Symbolic Logic 65 (2):627-640 (2000)

Abstract

n + 1 nested k-ary fixed point operators are more expressive than n. This holds on finite structures for all sublogics of partial fixed point logic PFP that can express conjunction, existential quantification and deterministic transitive closure of binary relations using at most k-ary fixed point operators and that are closed against subformulas. Among those are a lot of popular fixed point logics

Download options

PhilArchive



    Upload a copy of this work     Papers currently archived: 72,855

External links

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

Through your library

Analytics

Added to PP
2009-01-28

Downloads
65 (#180,050)

6 months
1 (#386,001)

Historical graph of downloads
How can I increase my downloads?

References found in this work

Finite Model Theory.Heinz-Dieter Ebbinghaus & Jörg Flum - 2001 - Studia Logica 69 (3):449-449.
Arity Hierarchies.Martin Grohe - 1996 - Annals of Pure and Applied Logic 82 (2):103-163.

Add more references

Citations of this work

No citations found.

Add more citations

Similar books and articles

Iterative and Fixed Point Common Belief.Aviad Heifetz - 1999 - Journal of Philosophical Logic 28 (1):61-79.
The Expressive Power of Fixed-Point Logic with Counting.Martin Otto - 1996 - Journal of Symbolic Logic 61 (1):147-176.
Guarded Quantification in Least Fixed Point Logic.Gregory McColm - 2004 - Journal of Logic, Language and Information 13 (1):61-110.
Tarskian and Kripkean Truth.Volker Halbach - 1997 - Journal of Philosophical Logic 26 (1):69-80.
Some Unifying Fixed Point Principles.Raymond M. Smullyan - 1991 - Studia Logica 50 (1):129 - 141.
Fixed Point Logics.Anuj Dawar & Yuri Gurevich - 2002 - Bulletin of Symbolic Logic 8 (1):65-88.