On fixed-point logic with counting

DOI10.2307/2586569MaRDI QIDQ4508261zbMATH OpenOpenAlexFDO

Authors 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

finite model theoryfixed-pointpolynomial timedescriptive 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)

Recommendations

• scientific article; zbMATH DE number 515737
• On polynomial time computation over unordered structures
• The Power of Counting Logics on Restricted Classes of Finite Structures
• The two-variable fragment with counting and equivalence
• Fixed-point logics and computation
• Fixed-point definability and polynomial time on chordal graphs and line graphs
• Logics with counting and equivalence
• Complexity of the two-variable fragment with counting quantifiers
• Logical hierarchies in PTIME
• Tree canonization and transitive closure

Cites work

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

Cited in

(18)

• Choiceless polynomial time, counting and the Cai-Fürer-Immerman graphs
• First order logic, fixed point logic and linear order
• Rank logic is dead, long live rank logic!
• scientific article; zbMATH DE number 4041901 (Why is no real title available?)
• Fixed-point logics and computation
• On polynomial time computation over unordered structures
• Enhancing fixed point logic with cardinality quantifiers
• Maximum matching and linear programming in fixed-point logic with counting
• Tree canonization and transitive closure
• A logical characterization of the counting hierarchy
• The Power of Counting Logics on Restricted Classes of Finite Structures
• On the Descriptive Complexity of Linear Algebra
• Gaifman normal forms for counting extensions of first-order logic
• An analysis of fixed-point queries on binary trees
• scientific article; zbMATH DE number 515737 (Why is no real title available?)
• scientific article; zbMATH DE number 1670476 (Why is no real title available?)
• Arrow logic and infinite counting
• scientific article; zbMATH DE number 4008383 (Why is no real title available?)

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

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