Hierarchies in transitive closure logic, stratified Datalog and infinitary logic

Annals of Pure and Applied Logic 77 (2):169-199 (1996)
  Copy   BIBTEX

Abstract

We establish a general hierarchy theorem for quantifier classes in the infinitary logic L∞ωωon finite structures. In particular, it is shown that no infinitary formula with bounded number of universal quantifiers can express the negation of a transitive closure.This implies the solution of several open problems in finite model theory: On finite structures, positive transitive closure logic is not closed under negation. More generally the hierarchy defined by interleaving negation and transitive closure operators is strict. This proves a conjecture of Immerman.We also separate the expressive power of several extensions of Datalog, giving new insight in the fine structure of stratified Datalog

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 92,038

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

A double arity hierarchy theorem for transitive closure logic.Martin Grohe & Lauri Hella - 1996 - Archive for Mathematical Logic 35 (3):157-171.
The dimension of the negation of transitive closure.Gregory L. McColm - 1995 - Journal of Symbolic Logic 60 (2):392-414.
Antifoundation and Transitive Closure in the System of Zermelo.Olivier Esser & Roland Hinnion - 1999 - Notre Dame Journal of Formal Logic 40 (2):197-205.
Infinitary Modal Logic and Generalized Kripke Semantics.Pierluigi Minari - 2011 - Annali Del Dipartimento di Filosofia 17:135-166.
Supervenience and infinitary property-forming operations.Ralf M. Bader - 2012 - Philosophical Studies 160 (3):415-423.
Dimension Versus Number of Variables, and Connectivity, too.Gregory L. McColm - 1995 - Mathematical Logic Quarterly 41 (1):111-134.
The Price of Universality.Edith Hemaspaandra - 1996 - Notre Dame Journal of Formal Logic 37 (2):174-203.
Infinitary S5‐Epistemic Logic.Aviad Heifetz - 1997 - Mathematical Logic Quarterly 43 (3):333-342.
On transitive subrelations of binary relations.Christopher S. Hardin - 2011 - Journal of Symbolic Logic 76 (4):1429-1440.
From finitary to infinitary second‐order logic.George Weaver & Irena Penev - 2005 - Mathematical Logic Quarterly 51 (5):499-506.
Stratified languages.A. Pétry - 1992 - Journal of Symbolic Logic 57 (4):1366-1376.

Analytics

Added to PP
2014-01-16

Downloads
25 (#634,233)

6 months
4 (#792,963)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Some aspects of model theory and finite structures.Eric Rosen - 2002 - Bulletin of Symbolic Logic 8 (3):380-403.
On the First-Order Prefix Hierarchy.Eric Rosen - 2005 - Notre Dame Journal of Formal Logic 46 (2):147-164.
Yet another hierarchy theorem.Max Kubierschky - 2000 - Journal of Symbolic Logic 65 (2):627-640.
Guarded quantification in least fixed point logic.Gregory McColm - 2004 - Journal of Logic, Language and Information 13 (1):61-110.

Add more citations

References found in this work

Finite partially-ordered quantification.Wilbur John Walkoe Jr - 1970 - Journal of Symbolic Logic 35 (4):535-555.
Finite partially-ordered quantification.Wilbur John Walkoe - 1970 - Journal of Symbolic Logic 35 (4):535-555.
Monadic generalized spectra.Ronald Fagin - 1975 - Mathematical Logic Quarterly 21 (1):89-96.
Fixed-point extensions of first-order logic.Yuri Gurevich & Saharon Shelah - 1986 - Annals of Pure and Applied Logic 32:265-280.
On Moschovakis closure ordinals.Jon Barwise - 1977 - Journal of Symbolic Logic 42 (2):292-296.

View all 11 references / Add more references