Locality of Queries Definable in Invariant First-Order Logic with Arbitrary Built-in Predicates
type: Item
instance of: scholarly article
title: Locality of Queries Definable in Invariant First-Order Logic with Arbitrary Built-in Predicates
zbMATH Open document ID: 1333.68129
DOI: 10.1007/978-3-642-22012-8_29
published in: Automata, Languages and Programming
publication date: 2011-07-07T00:00:00Z
Mathematics Subject Classification ID: 68Q19
Mathematics Subject Classification ID: 03C13
Mathematics Subject Classification ID: 68Q15
zbMATH DE Number: 5918159
MaRDI profile type: Publication
full work available at URL: 978-3-642-22012-8 29
OpenAlex ID: W2255083403
cites work: \(\Sigma_ 1^ 1\)-formulae on finite structures
cites work: Towards a characterization of order-invariant queries over tame graphs
cites work: Parity, circuits, and the polynomial-time hierarchy
cites work: Fixed-Point Definability and Polynomial Time
cites work: Locality of order-invariant first-order formulas
cites work: Relational queries computable in polynomial time
cites work: Languages that Capture Complexity Classes
cites work: Elements of finite model theory.
cites work: Constant depth circuits, Fourier transform, and learnability
cites work: Q4263795
Recommended article: Locality of order-invariant first-order formulas
Recommended article: Q4218118
Recommended article: Q2958533
Recommended article: On the locality of arb-invariant first-order formulas with modulo counting quantifiers
Recommended article: Notions of locality and their logical characterizations over finite models
Recommended article: Local Reasoning for Global Invariants, Part I
Recommended article: Verifying local stratifiability of logic programs and databases
Recommended article: Local properties of query languages
Recommended article: Declarative local search for predicate logic
description: scientific article