An existential locality theorem

DOI10.1016/j.apal.2004.01.005zbMath1056.03017OpenAlexW1983533869MaRDI QIDQ1887659

Martin Grohe, Stefan Wöhrle

Publication date: 22 November 2004

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.apal.2004.01.005

zbMATH Keywords

Finite model theoryDescriptive complexityLocalityExistential first-order logic

Mathematics Subject Classification ID

Model theory of finite structures (03C13) Descriptive complexity and finite models (68Q19)

Related Items (3)

Subshifts as models for MSO logic ⋮ Game-based notions of locality over finite models ⋮ The parameterized complexity of \(k\)-edge induced subgraphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Graph minors. III. Planar tree-width
• Local properties of query languages
• Diameter and treewidth in minor-closed graph families
• On the computational power of pushdown automata
• Deciding first-order properties of locally tree-decomposable structures
• Query evaluation via tree-decompositions
• Notions of locality and their logical characterizations over finite models
• Logics with aggregate operators
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Logics with counting and local properties

This page was built for publication: An existential locality theorem