Yet another hierarchy theorem

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


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



    Upload a copy of this work     Papers currently archived: 86,168

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

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.


Added to PP

67 (#207,422)

6 months
2 (#517,597)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations

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