Notions of locality and their logical characterizations over finite models

Journal of Symbolic Logic 64 (4):1751-1773 (1999)
  Copy   BIBTEX

Abstract

Many known tools for proving expressibility bounds for first-order logic are based on one of several locality properties. In this paper we characterize the relationship between those notions of locality. We note that Gaifman's locality theorem gives rise to two notions: one deals with sentences and one with open formulae. We prove that the former implies Hanf's notion of locality, which in turn implies Gaifman's locality for open formulae. Each of these implies the bounded degree property, which is one of the easiest tools for proving expressibility bounds. These results apply beyond the first-order case. We use them to derive expressibility bounds for first-order logic with unary quantifiers and counting. We also characterize the notions of locality on structures of small degree

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 90,616

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

Jarrett's Locality Condition and Causal Paradox.Allen Stairs - 1988 - PSA: Proceedings of the Biennial Meeting of the Philosophy of Science Association 1988:318 - 325.
Logical independence in quantum logic.Miklós Rédei - 1995 - Foundations of Physics 25 (3):411-422.
Correlations and Physical Locality.Arthur Fine - 1980 - PSA: Proceedings of the Biennial Meeting of the Philosophy of Science Association 1980:535 - 562.

Analytics

Added to PP
2009-01-28

Downloads
212 (#87,062)

6 months
5 (#247,092)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

An existential locality theorem.Martin Grohe & Stefan Wöhrle - 2004 - Annals of Pure and Applied Logic 129 (1-3):131-148.
Game-based notions of locality over finite models.Marcelo Arenas, Pablo Barceló & Leonid Libkin - 2008 - Annals of Pure and Applied Logic 152 (1-3):3-30.

Add more citations

References found in this work

Finite Model Theory.Heinz-Dieter Ebbinghaus & Jörg Flum - 2001 - Studia Logica 69 (3):449-449.
On winning Ehrenfeucht games and monadic NP.Thomas Schwentick - 1996 - Annals of Pure and Applied Logic 79 (1):61-92.

Add more references