Locality of order-invariant first-order formulas

1 July 2000

journal article
Published by Association for Computing Machinery (ACM) in ACM Transactions on Computational Logic

Vol. 1 (1) , 112-130
https://doi.org/10.1145/343369.343386

Abstract

A query is local if the decision of whether a tuple in a structure satisfies this query only depends on a small neighborhood of the tuple. We prove that all queries expressible by order-invariant first-order formulas are local.

Keywords

STRUCTURE
ORDER INVARIANT
ORDER FORMULAS
SATISFIES
FORMULAS A QUERY
LOCAL
TUPLE

This publication has 5 references indexed in Scilit:

Logics with counting and local properties
ACM Transactions on Computational Logic, 2000
Notions of locality and their logical characterizations over finite models
The Journal of Symbolic Logic, 1999
On winning Ehrenfeucht games and monadic NP
Annals of Pure and Applied Logic, 1996
Finite Model Theory
Published by Springer Nature ,1995
Mathematical Logic
Published by Springer Nature ,1994