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

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
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.1016/0168-0072(95)00021-6
Options
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 55,909
Through your library

References found in this work BETA

Finite Partially-Ordered Quantification.Wilbur John Walkoe Jr - 1970 - Journal of Symbolic Logic 35 (4):535-555.
Henkin Quantifiers and Complete Problems.Andreas Blass & Yuri Gurevich - 1986 - Annals of Pure and Applied Logic 32:1--16.
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.

View all 12 references / Add more references

Citations of this work BETA

Some Aspects of Model Theory and Finite Structures.Eric Rosen - 2002 - Bulletin of Symbolic Logic 8 (3):380-403.
Yet Another Hierarchy Theorem.Max Kubierschky - 2000 - Journal of Symbolic Logic 65 (2):627-640.

Add more citations

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 (1):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 index
2014-01-16

Total views
18 ( #558,099 of 2,402,088 )

Recent downloads (6 months)
1 ( #552,323 of 2,402,088 )

How can I increase my downloads?

Downloads

My notes