An existential locality theorem

&
Annals of Pure and Applied Logic 129 (1-3):131-148 (2004)
  Copy   BIBTEX

Abstract

We prove an existential version of Gaifman's locality theorem and show how it can be applied algorithmically to evaluate existential first-order sentences in finite structures

Categories

Keywords

Reprint years

DOI

10.1016/j.apal.2004.01.005

Other Versions

No versions found

Links

PhilArchive



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

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

Notions of locality and their logical characterizations over finite models.Lauri Hella, Leonid Libkin & Juha Nurmonen - 1999 - Journal of Symbolic Logic 64 (4):1751-1773.
Normal forms for second-order logic over finite structures, and classification of NP optimization problems.Thomas Eiter, Georg Gottlob & Yuri Gurevich - 1996 - Annals of Pure and Applied Logic 78 (1-3):111-125.
On Preservation Theorems for Two-Variable Logic.Erich Gradel & Eric Rosen - 1999 - Mathematical Logic Quarterly 45 (3):315-325.
Existential instantiation and normalization in sequent natural deduction.Carlo Cellucci - 1992 - Annals of Pure and Applied Logic 58 (2):111-148.
Minimal first-order structures.Predrag Tanović - 2011 - Annals of Pure and Applied Logic 162 (11):948-957.
Axiomatizing first-order consequences in dependence logic.Juha Kontinen & Jouko Väänänen - 2013 - Annals of Pure and Applied Logic 164 (11):1101-1117.
Algorithmic uses of the Feferman–Vaught Theorem.J. A. Makowsky - 2004 - Annals of Pure and Applied Logic 126 (1-3):159-213.
Nonstandard methods for finite structures.Akito Tsuboi - 2020 - Mathematical Logic Quarterly 66 (3):367-372.
Cantor theorem and friends, in logical form.Silvio Valentini - 2013 - Annals of Pure and Applied Logic 164 (4):502-508.
Positive logics.Saharon Shelah & Jouko Väänänen - 2023 - Archive for Mathematical Logic 62 (1):207-223.

Analytics

Added to PP
2014-01-16

Downloads
33 (#689,874)

6 months
11 (#356,365)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

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

Add more references