6533b86efe1ef96bd12cc71e
RESEARCH PRODUCT
Locality of order-invariant first-order formulas
Thomas SchwentickMartin Grohesubject
Discrete mathematicsGeneral Computer ScienceLogicLocalityStructure (category theory)InformationSystems_DATABASEMANAGEMENTFirst orderTheoretical Computer ScienceFirst-order logicCombinatoricsComputational MathematicsOrder (group theory)TupleInvariant (mathematics)Mathematicsdescription
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.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2000-07-01 | ACM Transactions on Computational Logic |