Fixed-Point Definability and Polynomial Time

DOI10.1007/978-3-642-04027-6_4zbMath1257.68069OpenAlexW1504704680MaRDI QIDQ3644737

Martin Grohe

Publication date: 12 November 2009

Published in: Computer Science Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-04027-6_4

Mathematics Subject Classification ID

Logic in computer science (03B70) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Descriptive complexity and finite models (68Q19)

Related Items (1)

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

Cites Work

• Unnamed Item
• Unnamed Item
• Finite model theory and its applications.
• Choiceless polynomial time
• Upper and lower bounds for first order expressibility
• An optimal lower bound on the number of variables for graph identification
• Definability hierarchies of generalized quantifiers
• Structure and complexity of relational queries
• Bisimulation-invariant PTIME and higher-dimensional \(\mu\)-calculus
• Almost Everywhere Equivalence of Logics in Finite Model Theory
• A Logic for PTIME and a Parameterized Halting Problem
• Generalized Quantifiers and Logical Reducibilities
• On polynomial time computation over unordered structures
• Database Theory - ICDT 2005

This page was built for publication: Fixed-Point Definability and Polynomial Time