Locality of order-invariant first-order formulas

DOI10.1007/BFB0055793MaRDI QIDQ4218118zbMATH OpenFDO

Authors Martin Grohe, Thomas Schwentick

Publication date 11 November 1998

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BFB0055793

zbMATH Keywords

local queryorder-invariant first-order formulas

Mathematics Subject Classification ID

Classical first-order logic (03B10) Other applications of logic (03B80) Model theory of finite structures (03C13) Database theory (68P15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• Locality of order-invariant first-order formulas
• Locality of Queries Definable in Invariant First-Order Logic with Arbitrary Built-in Predicates
• Notions of locality and their logical characterizations over finite models
• Locality from circuit lower bounds
• On the locality of arb-invariant first-order formulas with modulo counting quantifiers

Cited in

(7)

• Axiomatization of local-global principles for pp-formulas in spaces of orderings
• Lower bounds for invariant queries in logics with counting.
• On the expressiveness of \textsc{Lara}: a proposal for unifying linear and relational algebra
• scientific article; zbMATH DE number 6680147 (Why is no real title available?)
• On the locality of arb-invariant first-order formulas with modulo counting quantifiers
• Locality of Queries Definable in Invariant First-Order Logic with Arbitrary Built-in Predicates
• Locality of order-invariant first-order formulas

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4218118)