Locality of order-invariant first-order formulas

DOI10.1145/343369.343386zbMath1365.68204OpenAlexW2100006909MaRDI QIDQ5738900

Martin Grohe, Thomas Schwentick

Publication date: 13 June 2017

Published in: ACM Transactions on Computational Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/343369.343386

zbMATH Keywords

logicsfirst-order logiclocalityordered structures

Mathematics Subject Classification ID

Database theory (68P15) Classical first-order logic (03B10) Model theory of finite structures (03C13)

Related Items (9)

A logical approach to locality in pictures languages ⋮ Expressive power of SQL. ⋮ Incremental recomputation in local languages. ⋮ Successor-Invariant First-Order Logic on Classes of Bounded Degree ⋮ Locality of Queries Definable in Invariant First-Order Logic with Arbitrary Built-in Predicates ⋮ Unnamed Item ⋮ Consistent query answering for primary keys in Datalog ⋮ Towards a characterization of order-invariant queries over tame graphs ⋮ On the expressive power of monadic least fixed point logic

This page was built for publication: Locality of order-invariant first-order formulas