Locality of Queries Definable in Invariant First-Order Logic with Arbitrary Built-in Predicates

DOI10.1007/978-3-642-22012-8_29zbMath1333.68129OpenAlexW2255083403MaRDI QIDQ3012933

No author found.

Publication date: 7 July 2011

Published in: Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-22012-8_29

Mathematics Subject Classification ID

Model theory of finite structures (03C13) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Descriptive complexity and finite models (68Q19)

Cites Work

• Unnamed Item
• Elements of finite model theory.
• \(\Sigma_ 1^ 1\)-formulae on finite structures
• Constant depth circuits, Fourier transform, and learnability
• Parity, circuits, and the polynomial-time hierarchy
• Towards a characterization of order-invariant queries over tame graphs
• Fixed-Point Definability and Polynomial Time
• Relational queries computable in polynomial time
• Languages that Capture Complexity Classes
• Locality of order-invariant first-order formulas

This page was built for publication: Locality of Queries Definable in Invariant First-Order Logic with Arbitrary Built-in Predicates