Yet another hierarchy theorem

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

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

Categories

Keywords

Reprint years

DOI

10.2307/2586558

Other Versions

No versions found

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 101,105

External links

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

Through your library

My notes

Similar books and articles

A double arity hierarchy theorem for transitive closure logic.Martin Grohe & Lauri Hella - 1996 - Archive for Mathematical Logic 35 (3):157-171.
Fixed point logics.Anuj Dawar & Yuri Gurevich - 2002 - Bulletin of Symbolic Logic 8 (1):65-88.
The expressive power of fixed-point logic with counting.Martin Otto - 1996 - Journal of Symbolic Logic 61 (1):147-176.
Outline of an Intensional Theory of Truth.Roy T. Cook - 2022 - Notre Dame Journal of Formal Logic 63 (1):81-108.
Expressive equivalence of least and inflationary fixed-point logic.Stephan Kreutzer - 2004 - Annals of Pure and Applied Logic 130 (1-3):61-78.
Remarks on the Gupta-Belnap fixed-point property for k-valued clones.José Martínez-Fernández - 2014 - Journal of Applied Non-Classical Logics 24 (1-2):118-131.
Incompleteness and Fixed Points.Lorenzo Sacchetti - 2002 - Mathematical Logic Quarterly 48 (1):15-28.
The fixed point and the Craig interpolation properties for sublogics of $$\textbf{IL}$$.Sohei Iwata, Taishi Kurahashi & Yuya Okawa - 2024 - Archive for Mathematical Logic 63 (1):1-37.
On the λY calculus.Rick Statman - 2004 - Annals of Pure and Applied Logic 130 (1-3):325-337.
Definable fixed points in modal and temporal logics — a survey.Sergey Mardaev - 2007 - Journal of Applied Non-Classical Logics 17 (3):317-346.

Analytics

Added to PP
2009-01-28

Downloads
84 (#242,755)

6 months
5 (#1,012,292)

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