On fixed-point logic with counting

DOI10.2307/2586569zbMath0960.03025OpenAlexW2092961415MaRDI QIDQ4508261

Jörg Flum, Martin Grohe

Publication date: 14 January 2001

Published in: Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.2307/2586569

zbMATH Keywords

fixed-pointpolynomial timefinite model theorydescriptive complexitycounting logicinflationary fixed-point logic

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Model theory of finite structures (03C13) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Descriptive complexity and finite models (68Q19)

Related Items (1)

Choiceless polynomial time, counting and the Cai-Fürer-Immerman graphs

Cites Work

• Fixed-point extensions of first-order logic
• An optimal lower bound on the number of variables for graph identification
• Infinitary logic and inductive definability over finite structures
• Relational queries computable in polynomial time
• Generalized Quantifiers and Logical Reducibilities
• The expressive power of fixed-point logic with counting

This page was built for publication: On fixed-point logic with counting