Fixed-Point Definability and Polynomial Time

DOI10.1007/978-3-642-04027-6_4MaRDI QIDQ3644737zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• Definability by constant-depth polynomial-size circuits
• Fixed-point definability and polynomial time on graphs with excluded minors
• Definable Subsets of Polynomial-Time Algebraic Structures
• scientific article; zbMATH DE number 1948415
• Fixed-parameter tractability, definability, and model-checking
• Arithmetical definability and computational complexity
• Fixed-point definability and polynomial time on chordal graphs and line graphs
• scientific article; zbMATH DE number 1342210
• The complexity of Tarski's fixed point theorem
• Definability of Cai-Fürer-Immerman Problems in Choiceless Polynomial Time

Cites work

• A logic for PTIME and a parameterized halting problem
• Almost Everywhere Equivalence of Logics in Finite Model Theory
• An optimal lower bound on the number of variables for graph identification
• Bisimulation-invariant PTIME and higher-dimensional \(\mu\)-calculus
• Choiceless polynomial time
• Database Theory - ICDT 2005
• Definability hierarchies of generalized quantifiers
• Finite model theory and its applications.
• Generalized Quantifiers and Logical Reducibilities
• scientific article; zbMATH DE number 3474957 (Why is no real title available?)
• scientific article; zbMATH DE number 1392292 (Why is no real title available?)
• On polynomial time computation over unordered structures
• Structure and complexity of relational queries
• Upper and lower bounds for first order expressibility

Cited in

(5)

• Locality of Queries Definable in Invariant First-Order Logic with Arbitrary Built-in Predicates
• scientific article; zbMATH DE number 5622695 (Why is no real title available?)
• Strong extension axioms and Shelah's zero-one law for choiceless polynomial time
• Definability of Cai-Fürer-Immerman Problems in Choiceless Polynomial Time
• Definability of Cai-Fürer-Immerman Problems in Choiceless Polynomial Time

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

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